Is the proof of the following theorem correct?

Mario Carneiro di.gama at
Tue Jul 20 21:54:25 EDT 2021

Without commenting on the proof, there is an odd consequence of the
statement: Condition 3 says that A(k,s) halts, so condition 1 says that
C_k(s) diverges, so the second part of condition 2 asserts that C_s
diverges everywhere. That's not an error as far as I can tell, but it does
suggest that some part of the proof might be unexpectedly trivialized.

Mario Carneiro

On Tue, Jul 20, 2021 at 8:33 PM X.Y. Newberry <newberryxy at> wrote:

> For FOM:
> Is the proof of the following theorem correct?
> 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.
> --
> X.Y. Newberry
> *There are two ways to be fooled. One is to believe what isn't true; the
> other is to refuse to believe what is true.*
> ― Søren Kierkegaard
> <>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20210720/1718cfa0/attachment-0001.html>

More information about the FOM mailing list