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.

computability reference-request turing-machines halting-problem 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.

P A + " M terminates on all input"

$\mathrm{PA}+\mbox{"$M$ terminates on all input"}$

Cody

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 sempre pára, mas certamente não pode provar que a máquina "Se aceita 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. $M$ $M$ $M'(x)$ $=$ $M$ $x$

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

.

Π_{2}^{0}

$\Pi^0_2$

Π_{2}^{0}

$\Pi^0_2$

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 ). ${\cal T}$ ${\cal T}$

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

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 termina em todas as entradas (se for consistente). ${\cal T}$ $M$

Isto, obviamente, funciona para , , , ..., desde que eles sejam compatíveis. ${\cal T}=\mathrm{ZFC}$ ${\cal T}=\mathrm{PA}$ ${\cal T}=\mathrm{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

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

Respostas: