THEOREM 1: There are numbers k and s and a program A(n,m) satisfying the following conditions.

1. If A(n,m) halts, then C_n(m) diverges.

2. For all n, C_k(n) = A(n,n) and C_s(n) = Ck(s).

3. A(k,s) halts and for all n, A(s,n) diverges.

Here C_n(*) is a program with index n in some exhaustive enumeration of all possible programs.

The proof is here.

https://xnewberry.tripod.com/Theorem.pdf

Similar questions and discussions