Seja A = {x ∈ N|Φx(x)↓ e Φx(x)>x}. Mostre, por diagonalização, que A não é recursivo.

Resposta:

Vamos separar as propriedades de A em dois conjuntos, A’ e A” de forma que A = A¹ ∪ A².

A¹ = {x ∈ N|Φx(x)↓}
A² = {x ∈ N|Φx(x)>x}

A² ⊂ A¹. Portanto provando que A² é recursivo, provamos que A¹ também é recursivo. Para tanto provaremos que o teste de convergência de Φx(x) não é computável.

Por contradição vamos supor que Φx(y)↓ é computável, logo podemos escrever um programa ρ:

A = Φx(x)↓
[L] IF A==TRUE GOTO L

Seja #ρ = P (a codificação de P), então:

ΦP(x)↓ ↔ ~ΦP(x)↓

Em particular essa equivalência é válida para P:

ΦP(P)↓ ↔ ~ΦP(P)↓

Ou seja, ΦP(P)↓ vai parar se ΦP(P) não parar, o que é absurdo. Como todas as construções que fizemos até agora foram válidas, nossa suposição de que Φx(y)↓ é computável é falsa.