Existem teoria algorítmica dos grafos / teoria dos números / combinatória / teoria da informação / teoria dos jogos. Existe análise matemática algorítmica? Segundo o wiki, a análise matemática inclui as teorias de diferenciação, integração, medida, limites, séries infinitas e funções...
Alguém conhece um conjunto de problemas que variam uniformemente e abrangem uma das hierarquias "interessantes" de complexidade e computabilidade? Por interessante, quero dizer, por exemplo, a Hierarquia Polinomial, a Hierarquia Aritmética ou a Hierarquia Analítica. Ou talvez (N) P, (N) EXP, 2 (N)...
Pergunta : A previsão (conforme definida abaixo) de seqüências computáveis é tão difícil quanto o problema de parada? Elaboração : "Predizer" significa prever com sucesso, o que significa cometer apenas erros finitos na tarefa de tentar prever o n-ésimo bit da sequência com acesso aos n-1 bits...
Harvey Friedman mostrou que há um resultado puro de ponto fixo que não pode ser provado no ZFC (a teoria dos conjuntos de Zermelo-Frankel usual com o Axiom of Choice). Muitas lógicas modernas são construídas sobre operadores de ponto fixo, então eu me perguntava: existem consequências conhecidas do...
Considere o seguinte jogo para 2 jogadores: A natureza escolhe aleatoriamente um programa Cada jogador toca um número em [0, infinito], inclusive em resposta ao movimento da natureza Pegue o mínimo dos números dos jogadores e execute o programa por (até) muitas etapas (a menos que ambos os...
Ouvi muitas vezes dizer que você não pode escrever um programa para detectar bugs em um navegador da Web, processador de texto ou sistema operacional, por causa do Teorema de Rice: qualquer propriedade semântica para uma linguagem completa de Turing é indecidível. No entanto, não sei até que...
Vamos HALTnHALTnHALT_n denotar a cadeia de comprimento 2n2n2^n correspondente à tabela verdade do problema de parada para entradas de comprimento nnn . Se a sequência das complexidades de Kolmogorov K(HALTn)K(HALTn)K(HALT_n) fosse O(1)O(1)O(1) , uma das sequências de aconselhamento seria usada...
Existe uma noção de computabilidade em conjuntos diferentes dos números naturais? Por uma questão de argumento, vamos dizer em conjuntos SSS que biject com NN\mathbb{N} . É tentador dizer "sim, eles são aquelas funções da forma , onde g é qualquer bijection N → S e f é qualquer função computável N...
Esta pergunta é sobre se existem tarpits reversíveis conhecidos de Turing, onde "reversível" significa no sentido de Axelsen e Glück , e "tarpit" é um conceito muito mais informal (e pode não ser uma escolha muito boa de palavra), mas farei o possível para explicar o que quero dizer com isso. O...
Os problemas foram classificados como um todo graças à complexidade computacional. Mas, em equações diferenciais, é possível classificar equações diferenciais dependendo de sua estrutura computacional? Por exemplo, se uma equação não homogênea de primeira ordem é comparativamente difícil de...
Fechadas. Esta questão está fora de tópico . No momento, não está aceitando respostas. Deseja melhorar esta pergunta? Atualize a pergunta para que ela esteja no tópico do Theoretical Computer Science Stack Exchange. Fechado há 3 anos . Existe uma...
Segue-se do teorema de Rice que você não pode determinar se duas máquinas de Turing decidem ou não o mesmo idioma. Minha pergunta é: Isso também se aplica a configurações descritivas de complexidade, principalmente quando se trata de testar um par de consultas SO-Horn para ver se elas descrevem o...
Exemplos bem conhecidos de computação inspirados em fenômenos naturais são computadores quânticos e computadores de DNA. O que se sabe sobre o potencial e / ou limitações da computação com as leis ou a gravidade de Maxwell? Ou seja, incorporar as soluções "rápidas" da natureza às equações de...
Tenho uma pergunta, cuja resposta provavelmente é bem conhecida, mas não consigo encontrar nada significativo depois de algumas pesquisas, por isso gostaria de receber alguma ajuda. Minha pergunta é se é sabido que decidir se um número é transcendental é indecidível. Possivelmente, assume-se...
Suponha que não conheçamos o resultado de Joe B. Wells, de 1994, de que tanto a tipabilidade quanto a verificação de tipos são indecidíveis no Sistema F (AKA ). No cálculo lambda de Barendregt com tipos (1992), encontrei uma prova, devido a Malecki 1989, de que a verificação de tipo implica...
Intrigado com a interessante pergunta de Chris Pressey sobre funções elementares-recursivas , eu estava explorando mais e não consegui encontrar uma resposta para essa pergunta na web. As funções recursivas elementares correspondem muito bem à hierarquia exponencial,
Encontrei a seguinte pergunta, que é um exercício fácil (spoiler abaixo). Recebemos instâncias do problema de interrupção (ou seja, TMs ) e precisamos decidir exatamente quais delas serão interrompidas no . Ou seja, precisamos . Recebemos um oráculo para o problema de parada, mas temos que usá-lo...
Existem problemas que são decidíveis, outros são indecidíveis, há semidecidibilidade etc. Nesse caso, pergunto-me se um problema pode ser meta-indecidível. Isso significa (pelo menos na minha cabeça) que não podemos dizer se é decidível ou não. Talvez seja sabido que a decidibilidade é...
Existe algum sistema semelhante ao cálculo lambda com forte normalização, sem a necessidade de adicionar um sistema de tipos sobre
O feto, se você nunca ouviu falar, pode ser lido aqui . Ele usa um sistema de 'matrizes de chamada' e 'gráficos de chamada' para encontrar todos os 'comportamentos de recursão' de chamadas recursivas em uma função. Para mostrar que uma função termina, mostra que todos os comportamentos de recursão...