Existe uma TM que pare em todas as entradas, mas essa propriedade não é comprovável?

17

Existe uma máquina de Turing que para em todas as entradas, mas essa propriedade não é comprovável por algum motivo?

Gostaria de saber se esta questão foi estudada. Observe que "improvável" pode significar um sistema de prova "limitado" (que no sentido fraco acha que a resposta deve ser sim). Naturalmente, estou interessado na resposta mais forte possível, isto é, que não é provável que seja interrompida em todas as entradas da teoria dos conjuntos do ZFC, seja o que for.

Ocorreu-me que isso poderia ser verdade com a função Ackermann, mas estou confuso com os detalhes. Não parece que a Wikipedia descreva esse aspecto claramente.

vzn
fonte
3
A aritmética Peano é suficiente para provar que a função de Ackermann é total: este é o exercício 17 das notas de Introdução às PA de Jaap van Oosten .
David Richerby
total computável fn defn wikipedia. Nota Esta questão foi em parte motivado por olhando para o fn Collatz onde é uma questão aberta longa relacionados ...
vzn
2
Esta é uma observação parvo, mas nota que para cada máquina de Turing M que termina sobre toda a entrada, a teoria é uma teoria consistente. Mas, usando o teorema de Gödels, podemos mostrar que não existe uma teoria recursiva única que possa provar o término de todas essas máquinas. PA+"M terminates on all input"
Cody

Respostas:

12

Sim. A máquina de Turing que calcula a sequência Goodstein iniciando em sua entrada e finalizando quando a sequência atinge zero. Sempre termina, mas isso não pode ser provado na aritmética Peano. Tenho certeza de que existem coisas equivalentes para o ZFC ou qualquer outro sistema que você possa escolher.


Editar Para a ZF, Hartmanis e Hopcroft mostram que existe uma máquina de Turing que rejeita todas as entradas, mas que isso não pode ser provado na ZF. Não tenho certeza se ZF pode provar que M sempre pára, mas certamente não pode provar que a máquina M ( x ) = "Se M aceita x, então loop para sempre, senão para" sempre pára, mesmo que isso aconteça. Isso ainda deixa o ZFC aberto, mas o ZF é mais poderoso que o PA.MMM(x) =Mx

Veja a seção 3 da pesquisa de Scott Aaronson sobre a independência de P = NP para uma exposição do resultado de Hartmanis – Hopcroft e citações em seus artigos originais.

David Richerby
fonte
Sobre como adicionar o axioma de escolha: O ZFC não pode fazer melhor que o ZF para instruções "simples" como um problema de parada (neste caso, se não me engano). Isso ocorre porque o ZF e o ZFC provam exatamente as mesmas declarações Π 0 2 . Π20Π20
Cody
6

Tome uma teoria que seja pelo menos tão forte quanto a aritmética "básica" e que seja recursivamente enumerável (é possível enumerar todos os teoremas de T ).TT

Construa a seguinte máquina , que se comporta da seguinte forma na entrada n :Mn

If there is no proof of 0 = 1 in less than n steps in T, ACCEPT
Otherwise, LOOP.

É muito fácil mostrar, usando o segundo teorema da incompletude, que não pode provar que M termina em todas as entradas (se for consistente).TM

Isto, obviamente, funciona para , T = P A , T = P Um ² , ..., desde que eles sejam compatíveis.T=ZFCT=PAT=PA²

cody
fonte
5

Alguns não comprováveis ​​no PA, mas verdadeiros teoremas podem ser convertidos em máquinas de Turing. Por exemplo, existe uma (versão fortalecida) do teorema de Ramsey , que é improvável no PA, e podemos construir uma máquina que apenas procuraria o certo .N

Daniil
fonte