Prova de indecidibilidade, não por redução do problema da parada

13

A maneira usual de provar indecidibilidade é através da redução de um problema de RE completo, como o problema de parada, validade na lógica de primeira ordem, satisfação das equações diofantinas, etc.

Sabe-se que existem problemas recursivamente enumeráveis, mas indecidíveis, que não são RE-completos, mas essas são construções artificiais (ou seja, conjuntos que foram definidos apenas para mostrar esse resultado de "densidade").

Como lidar com a comprovação de indecidibilidade sem redução de um problema de RE-completo? Diagonalização?

David Monniaux
fonte
4
Talvez a pergunta certa seja: "quais são os diferentes métodos diretos para provar indecidibilidade"?
Suresh Venkat
o teorema da incompletude de Godel é visto como um "caminho diferente" ... outra prova de diagonalização depende de que o número de programas / pares de entradas é contável, mas as línguas são incontáveis ​​e, portanto, é semelhante à incomensurabilidade dos reais com os números inteiros. ver também esta Q / A re Lawvere fixo ponto teorema
vzn
6
@vzn: Eu acho que de Godel incompletude como essencialmente a mesma prova ...
Joshua Grochow
Apenas por curiosidade, por que tipo de problema ou idioma você está tentando provar indecidibilidade? Eu acho que existem muitos problemas indecidíveis conhecidos (veja, por exemplo, uma pequena lista na Wikipedia) que você pode reduzir, então estou me perguntando se pelo menos um deles é semelhante ao seu ou se é um problema completamente novo.
Marzio De Biasi

Respostas:

10

Pode-se mostrar diretamente que a complexidade de Kolmogorov não é computável; veja, por exemplo, Sipser, 3ª edição, problema 6.23.

Bjørn Kjos-Hanssen
fonte
Isso também deve seguir diretamente o teorema da incompletude de Chaitin , cuja prova é bastante semelhante.
Yonatan N
Parece-me, pelos problemas anteriores, que Sipser pretende que os alunos usem a indecidibilidade do problema de parada para esta prova, portanto, talvez valha a pena esboçar a prova direta de desconformidade na resposta.
usul
Na verdade, comparar com os exercícios 6.24 e 6.25 também ajuda.
Bjørn Kjos-Hanssen
2
Eu pensei que poderia valer a pena ressaltar - dado que o OQ perguntou especificamente sobre diagonalização - que a prova de que K é incontestável também é essencialmente diagonalização. (De fato, é basicamente a mesma diagonalização simples de baunilha usada para provar HALT incontestável, que é a mesma prova original de Cantor sobre cardinalidades, que é a mesma que as provas da incompletude de Godel e Chaitin, que são todos os teoremas justos. versões do paradoxo de Russell ...
Joshua Grochow
10

Considere o que eu gosto de chamar de problema de GUESSING CONSISTENTE.

M

  • M

  • M

  • M

(É claro que isso não é exatamente uma linguagem, mas mais como um análogo de computabilidade de um problema de promessa.)

Agora, com uma modificação da prova original de Turing, é muito fácil mostrar que a SUGESTÃO CONSISTENTE é indecidível (deixarei isso como um exercício para você).

UMAUMA

Scott Aaronson
fonte
Obrigado, mas ... novamente, uma prova de diagonalização. ;-) Meu problema é que tenho algo que considero indecidível (basicamente, há mais de 35 anos, as pessoas sempre procuraram algoritmos heurísticos ou válidos para subclasses para resolvê-lo), mas para os quais parece não haver "óbvio" reduções de re nem algum argumento legal diagonalization ...
David Monniaux
Observe que não há problemas "naturais" que são conhecidos por serem indecidíveis, mas que não têm uma redução de Turing (conhecida) no problema de parada. Em particular, a única "recomendado" abordagem para mostrar que algo é indecidível é reduzi-lo a um outro problema indecidível (por exemplo semi-unificação ou acessibilidade matriz )
Cody
cody: Era o que eu pensava também. Mas se você estiver disposto a considerar tarefas mais gerais do que decidir um idioma, então, GUESSING CONSISTENTE é um contra-exemplo bastante natural! (Aliás, eu suponho que você quis dizer, reduzindo os problemas indecidíveis conhecidos para o seu problema, ao invés do contrário.)
Scott Aaronson
5

Se o que você está procurando é uma prova que não seja a) redução de um problema completo conhecido, nem b) diagonalização direta (que seus vários comentários indicam que você é), então, tanto quanto eu sei, você está sem sorte. Todas as provas de que tenho conhecimento não são por redução - incluindo as de outras excelentes respostas dadas aqui por Aaronson e Kjos-Hanssen - procedem por uma diagonalização direta.

E todas essas diagonalizações são essencialmente a mesma prova . Algumas delas são pequenas variantes na prova que produzem declarações um pouco mais fortes / fracas, mas as próprias provas são tipicamente apenas variações muito pequenas. (E todas essas provas são essencialmente as mesmas que as originais de Cantor sobre as cardinalidades, que são as mesmas da incompletude de Godel e Chaitin, que são todas as versões apenas do teorema do paradoxo de Russell ... Tanto é que de uma só vez Perguntei-me se seria possível formalizar, de algum modo da matemática reversa, um teorema que dizia que havia essencialmente apenas uma dessas provas.)

Pode valer a pena ressaltar, no entanto, que existem provas de outras afirmações - tipicamente de sabor diferente - que são diagonalizações que são realmente, verdadeiramente, comprovadamente diferentes da diagonalização usada para provar, por exemplo, a indecidibilidade do problema de parada.

Joshua Grochow
fonte
5
Não conheço muito esse tópico, mas o teorema do ponto fixo de Lawvere não é uma generalização comum de quase todos eles?
Sasho Nikolov