Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

Man will never fly. Space travel is merely a dream. All aspirin is alike.


computers / comp.ai.philosophy / H(D,D)==0 is proven to be correct [V7]

SubjectAuthor
o H(D,D)==0 is proven to be correct [V7]olcott

1
H(D,D)==0 is proven to be correct [V7]

<tu60b5$46u3$1@dont-email.me>

  copy mid

https://www.novabbs.com/computers/article-flat.php?id=10713&group=comp.ai.philosophy#10713

  copy link   Newsgroups: comp.theory sci.logic comp.ai.philosophy sci.math
Followup: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: polco...@gmail.com (olcott)
Newsgroups: comp.theory,sci.logic,comp.ai.philosophy,sci.math
Subject: H(D,D)==0 is proven to be correct [V7]
Followup-To: comp.theory
Date: Mon, 6 Mar 2023 18:26:12 -0600
Organization: A noiseless patient Spider
Lines: 48
Message-ID: <tu60b5$46u3$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 7 Mar 2023 00:26:13 -0000 (UTC)
Injection-Info: reader01.eternal-september.org; posting-host="1f34d3149e3ac520c44e8cb1c2956290";
logging-data="138179"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18nTLBEuxVCrhj3lr4Z7VIL"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101
Thunderbird/102.8.0
Cancel-Lock: sha1:+ahVuRkkv7ZcHMZw4qDSI+Uw7N4=
Content-Language: en-US
 by: olcott - Tue, 7 Mar 2023 00:26 UTC

https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X

MIT Professor Michael Sipser has agreed that this verbatim paragraph is
correct (he has neither reviewed nor agreed to anything else):

(a) If simulating halt decider H correctly simulates its input D until H
correctly determines that its simulated D would never stop running
unless aborted then (b) H can abort its simulation of D and correctly
report that D specifies a non-halting sequence of configurations.

To the best of my understanding (a) proves (b) is simply a tautology.
(proven true entirely on the basis of the meaning of its words)

01 int D(int (*x)())
02 {
03 int Halt_Status = H(x, x);
04 if (Halt_Status)
05 HERE: goto HERE;
06 return Halt_Status;
07 }
08
09 void main()
10 {
11 D(D);
12 }

Here is the sequence when H never aborts it simulation
main() calls D(D) at line 11
that calls H(D,D) that simulates D(D) at line 03
that calls H(D,D) that simulates D(D) at line 03
that calls H(D,D) that simulates D(D) ... repeating ...

Because it is an easily verified fact that D(D) would never stop running
unless H aborts its simulation of D, H is necessarily correct to return
0 indicating this verified fact.

This is every aspect of my whole proof

(a) (proven above)
(a) proves (b) (tautology)
---------------------------------
∴ H(D,D)==0 is correct

--
Copyright 2023 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer

1
server_pubkey.txt

rocksolid light 0.9.8
clearnet tor