Problema de parada, conjuntos incontestáveis: prova matemática comum?

29

Sabe-se que com um conjunto contável de algoritmos (caracterizado por um número de Gödel), não podemos computar (construir um algoritmo binário que verifique a pertença) todos os subconjuntos de N.

Uma prova poderia ser resumida como: se pudéssemos, então o conjunto de todos os subconjuntos de N seria contável (poderíamos associar a cada subconjunto o número de Gödel do algoritmo que o computa). Como isso é falso, prova o resultado.

Esta é uma prova de que gosto, pois mostra que o problema é equivalente aos subconjuntos de N que não são contáveis.

Agora eu gostaria de provar que o problema de parada não é solucionável usando apenas esse mesmo resultado (incontabilidade de subconjuntos de N), porque acho que esses são problemas muito próximos. É possível provar dessa maneira?

computability halting-problem Weier
fonte
Claramente, ambos os resultados podem ser comprovados usando a mesma técnica (diagonalização). No entanto, não creio que seja possível provar a indecidibilidade do problema de parada apenas usando a incontabilidade da família de subconjuntos de ℕ, porque o primeiro é sobre a comparação entre ER e R , que são famílias contáveis ​​de subconjuntos de ℕ.
Tsuyoshi Ito
Existem apenas muitos programas com acesso ao oráculo de parada, novamente caracterizado por um número de Godel. No entanto, o problema de parada está entre esse conjunto contável.
11133 David Harris

Respostas:

42

O teorema da parada, o teorema de Cantor (o não isomorfismo de um conjunto e seu conjunto de potências) e o teorema da incompletude de Goedel são todas instâncias do teorema de ponto fixo de Lawvere, que diz que para qualquer categoria fechada cartesiana, se houver um mapa epimórfico então todo tem um ponto fixo.e:A→(A⇒B)f:B→B

Para uma boa introdução a essas idéias, consulte este post de Andrej Bauer .

Neel Krishnaswami
fonte
7
isso é muito legal. Não percebi que havia um argumento formal real que os unifica.
Suresh Venkat
8
Aprendi agora a suspeitar que, se parece e cheira a mesmo, há um argumento categórico sobre o sentido em que é o mesmo.
precisa
2
Na IMO, as duas coisas realmente interessantes sobre o teorema de Lawvere são: (a) é uma afirmação positiva, e não negativa; e (b) a prova são meia dúzia de linhas de cálculos simples de cálculo lambda.
Neel Krishnaswami
6
Ao ler a pergunta, pensei comigo mesmo que alguém deveria mencionar o teorema do ponto fixo de Lawvere. Imagine a minha alegria quando eu li a resposta :-)
Andrej Bauer
11
Ser epimórfico não é a condição certa. Você precisa de pontos-supositividade, que não implica nem é implícita pela condição de ser epimórfica. Veja Observação 2.3 ncatlab.org/nlab/show/Lawvere%27s+fixed+point+theorem
fhyve