Is the proof of the following theorem correct?
newberryxy at gmail.com
Sat Jul 24 02:04:13 EDT 2021
Yes, C_s() diverges everywhere, but A() does not "know" it.
I think the proof is already fairly trivial.
On Wed, Jul 21, 2021 at 1:54 AM Mario Carneiro <di.gama at gmail.com> wrote:
> 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 gmail.com>
>> 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
*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...
More information about the FOM