Existem provas da indecidibilidade do problema de parada que não depende de auto-referência ou diagonalização?

40

Esta é uma pergunta relacionada a esta . Colocando novamente de uma forma muito mais simples, depois de muita discussão lá, parecia uma pergunta totalmente diferente.

A prova clássica da indecidibilidade do problema da parada depende de demonstrar uma contradição ao tentar aplicar a si próprio um hipotético decisor HALT. Eu acho que isso está apenas denotando a impossibilidade de ter um decisor HALT que decida se ele irá parar ou não, mas não fornece nenhuma informação além disso sobre a decisão de interromper qualquer outro caso.

Então a questão é

Existe uma prova de que o problema da parada é indecidível que não depende de mostrar que o HALT não pode decidir a si mesmo, nem depende do argumento da diagonalização?

Edição pequena: vou me comprometer com o fraseado original da pergunta, que está pedindo uma prova que não dependa de diagonlização (em vez de apenas exigir que não dependa de diagonalização que depende de HALT).

M. Alaggan
fonte
Você está procurando um que não dependa de um argumento de diagonalização ou apenas um que não diagonalize usando o HALT diretamente? Não tenho certeza se a prova que Bjørn propõe satisfaz a primeira.
Re: Reitblatt #
@ Mark: Não tenho certeza de fato. Se o argumento da diagonalização não corresponder à auto-referência, mas a outros aspectos, como incompatibilidade de cardinalidade, eu realmente esperaria que ele desse alguma idéia sobre por que o término do HALT (Q) (onde Q! = HALT) é indecidível .
M. Alaggan
1
Bem, nesse caso, posso dar um argumento mais simples. Comece com a observação de que existem problemas indecidíveis (argumento simples da cardinalidade) e, além disso, que há um problema indecidível P que possui uma TM M que reconhece seus membros (mas pode não terminar com não membros). Agora, resolver HALT (M) fornece uma decisão para P. Primeiro, verificamos se M pára em x. Se isso acontecer, executamos e retornamos o mesmo que M. Caso contrário, rejeitamos, pois M pára em todos os membros de P. Isso agora é uma contradição, pois assumimos que P era uma linguagem sem decisão.
Re: Reitblatt #
Esse argumento é realmente uma prova de que o HALT é RE-completo.
Re: Reitblatt #
1
Entendi. Se todas as TMs decidiram, o HALT é trivial. Se a parada não é trivial (existem reconhecedores), então (por contra-positivo) a existência de um HALT não trivial faz com que os decisores das TMs reconhecedoras, o que significa que o HALT é trivial, contraditório. Portanto, esse HALT não pode existir para todos os reconhecedores. Isso é brilhante, obrigado pelo seu maravilhoso comentário; você pode querer re-publicá-la como uma resposta :)
M. Alaggan

Respostas:

31

Sim, existem tais provas na teoria da computabilidade (também conhecida como teoria da recursão).

Você pode primeiro mostrar que o problema de parada (o conjunto ) pode ser usado para calcular um conjunto que é 1-genérico, o que significa que, em certo sentido, cada fato sobre é decidido por um processo finito. prefixo de . Então é fácil provar que esse conjunto não pode ser computável (isto é, decidível). G N Σ 0 1 G G G0GNΣ10GGG

Poderíamos substituir 1- genérico aqui por 1 aleatório, isto é, Martin-Löf aleatório , para o mesmo efeito. Isso usa o teorema de base baixa de Jockusch-Soare .

(Aviso: pode-se considerar apenas mostrar que calcula Chaitin , que é 1 aleatório, mas aqui temos que ter cuidado para saber se a prova de que é 1 aleatória depende do problema de parada ser indecidível! Portanto, é mais seguro usar o Teorema da Base Baixa).Ω Ω0ΩΩ

Bjørn Kjos-Hanssen
fonte
Muito interessante! Você pode me fornecer uma referência ou um conjunto de palavras-chave a serem pesquisadas para entender melhor? Muito obrigado!
M. Alaggan
6
@M. Alaggan: A melhor referência pode ser o livro recente de André Nies, Computability and Randomness , Oxford Logic Guides, Oxford University Press, 2009. Há também um artigo da Wikipedia sobre o Teorema da Base Baixa e um artigo da Scholarpedia sobre Aleatoriedade Algorítmica: scholarpedia.org / article / Algorithmic_randomness
Bjørn Kjos-Hanssen
@M. Alaggan, Depende de você, mas os votos sugerem que essa deve ser a resposta aceita.
Mohammad Al-Turkistany 11/11
Eu perguntei no meta (verifique meta.cstheory.stackexchange.com/questions/642/when-is-it-adequ-to-change-the-accepted-answer). Eu sei que essa resposta é realmente ótima e muito útil também. Aceitei o outro, no entanto, porque era muito mais fácil para mim entender com uma abordagem mais intuitiva. No entanto, parece haver uma discussão acima sobre sua correção (!). Portanto, se estiver incorreto, mudarei para esta resposta. Surgiu a confusão de eu não ser específico na pergunta original de que eu queria evitar a diagonalização usando HALT, em vez de todas as diagonalizações.
M. Alaggan
Estou extremamente confuso sobre qual deles devo aceitar, até o momento, pois estou escolhendo entre uma excelente resposta excelente e uma resposta fácil / intuitiva (minha formação não é muito sólida / madura). Então, por favor, sem ressentimentos :) Podemos discutir e chegar a uma decisão satisfatória para todos. Obrigado.
M. Alaggan
5

Republicado do meu comentário conforme solicitação:

Comece com a observação de que existem problemas indecidíveis (argumento simples da cardinalidade) e, além disso, que há um problema indecidível P que possui uma TM M que reconhece seus membros (mas pode não terminar com não membros). Agora, resolver HALT (M) fornece uma decisão para P. Verificamos primeiro se M pára em x. Se isso acontecer, executamos e retornamos o mesmo que M. Caso contrário, rejeitamos, já que M pára em todos os membros de P. Isso agora é uma contradição, pois assumimos que P era indecidível.

Nota: Ele esclareceu que estava procurando um argumento que evitasse a diagonalização usando o HALT diretamente, não um argumento que evitasse completamente a diagonalização.

Edição: Este argumento está preso. Você pode mostrar diretamente que o RE - REC não está vazio, além de mostrar que o HALT está lá?

Mark Reitblatt
fonte
O argumento de contabilização usa uma diagonalização muito semelhante (apenas um pouco mais simples) do que a prova padrão para o problema de parada. (Isto é, para mostrar que a cardinalidade de idiomas é maior do que a da TMS usos diagonalization.) :)
Joshua Grochow
@ Josué Leia os comentários. Perguntei se ele estava procurando uma prova que evitasse a diagonalização ou uma que apenas evitasse a diagonalização usando o HALT. Ele está procurando pelo último.
Re: Reitblatt #
@ Mark: Ah, eu senti falta disso. Obrigado. +1
Joshua Grochow 11/11
4
@ Mark: Você poderia esclarecer alguma coisa, por favor? Você começa observando que há um problema indecidível P que é reconhecível e, em seguida, observa que, se o HALT fosse decidível, poderíamos construir uma decisão para P. No entanto, nos textos que li, as coisas são provadas na outra ordem: a indecidibilidade do HALT é usada para demonstrar a existência de tais problemas P. Você pode mostrar a existência de problemas indecidíveis, mas reconhecíveis, sem usar a indecidibilidade do HALT?
Kurt
2
O fato de existir um problema reconhecível, mas indecidível, talvez seja mais facilmente provado, mostrando que o problema de parada é um problema, e nesse caso você está de volta ao ponto em que começou. Existem apenas muitos idiomas reconhecíveis.
Bjørn Kjos-Hanssen
2

Outro pôster aludiu a isso (referindo-se a Chaitin), mas você pode usar o paradoxo de Berry para provar que o problema da parada é indecidível. Aqui está um breve esboço da prova:

Seja o HALT uma máquina que decide se alguma máquina M pára na entrada I. Demonstraremos que o próprio HALT não é interrompido em uma entrada específica, o que mostra que não é possível decidir o idioma.

Considere a seguinte função f:

f (M, n) = a, onde a é o menor número inteiro positivo não computável pela máquina M em qualquer entrada I com | I | <n

Supondo que HALT é uma função computável, f também é uma função computável; simule simplesmente HALT (M, I) para cada máquina M e a string de entrada I com o comprimento de I menor que n. Se a simulação parar, simule M (I) e registre qual é a saída e encontre a menor saída a que não é emitida por nenhum dos pares M, n.

Agora, mostramos que f não é computável: considere f (f, 10000000 * | f | +10000000). Qualquer que seja a saída, deve ser um número inteiro (positivo) que não seja computável pela máquina que calcula f na entrada I com comprimento menor que o especificado ... e, no entanto, acabamos de produzir esse número inteiro com f e muito mais breve entrada.

Portanto, f não é computável e, portanto, nossa suposição de que o HALT era computável é falsa. Não acredito que essa prova faça uso da diagonalização.

Philip White
fonte
Whatever it outputs, it ought to be an integer that is not computable by the machine computing f on input I with length less than that given.>nn
5
Não estou tentando ser rude, mas sua objeção não faz sentido. A função f é definida como uma função que gera um número inteiro que não pode ser calculado por M em qualquer entrada com comprimento menor que n. Assim, apelos absurdos à aritmética modular à parte, será difícil mostrar que a frase que você destacou é inválida.
Philip White
@ johne concordo com Philip. Não há suposição sobre os limites da representação da máquina. Esta é uma TM.
Mark Reitblatt
@ Phillip Minor correção técnica: você deve alterar o número inteiro para natural ou positivo.
Re: Reitblatt
1
ff
0

{We}e=1feWe=Wf(e)0fe0We0eWe(0)Wf(e)(0)


fonte
6
Esta é a prova de diagonalização padrão.
Yuval Filmus