XPost: comp.theory, sci.logic, sci.math
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
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)