On 3/15/2024 11:20 AM, olcott wrote:
Best selling author of Theory of Computation textbooks:
*Introduction To The Theory Of Computation 3RD, by sipser*
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295/ >>
Date 10/13/2022 11:29:23 AM
*MIT Professor Michael Sipser agreed this verbatim paragraph is correct*
(He has neither reviewed nor agreed to anything else in this paper)
(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.
*When we apply the abort criteria* (elaborated above)
Will you halt if you never abort your simulation?
*Then H(D,D) is proven to meet this criteria*
*Proof that H(D,D) meets its abort criteria*
int D(int (*x)())
{
int Halt_Status = H(x, x);
if (Halt_Status)
HERE: goto HERE;
return Halt_Status;
}
int main()
{
Output("Input_Halts = ", H(D,D));
}
machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
[00001d22][00102fc9][00000000] 55 push ebp ; begin main()
[00001d23][00102fc9][00000000] 8bec mov ebp,esp
[00001d25][00102fc5][00001cf2] 68f21c0000 push 00001cf2 ; push DD
[00001d2a][00102fc1][00001cf2] 68f21c0000 push 00001cf2 ; push D
[00001d2f][00102fbd][00001d34] e8eef7ffff call 00001522 ; call H(D,D)
H: Begin Simulation Execution Trace Stored at:113075
Address_of_H:1522
[00001cf2][00113061][00113065] 55 push ebp ; enter D(D)
[00001cf3][00113061][00113065] 8bec mov ebp,esp
[00001cf5][0011305d][00103031] 51 push ecx
[00001cf6][0011305d][00103031] 8b4508 mov eax,[ebp+08]
[00001cf9][00113059][00001cf2] 50 push eax ; push D
[00001cfa][00113059][00001cf2] 8b4d08 mov ecx,[ebp+08]
[00001cfd][00113055][00001cf2] 51 push ecx ; push D
[00001cfe][00113051][00001d03] e81ff8ffff call 00001522 ; call H(D,D)
H: Recursive Simulation Detected Simulation Stopped
H(D,D) returns 0 to main()
*That was proof that H(D,D) meets its abort criteria*
H(D,D) correctly determines that itself is being called with its same
inputs and there are no conditional branch instructions between the
invocation of D(D) and its call to H(D,D).
On 3/15/2024 12:44 PM, Richard Damon wrote:
On 3/15/24 10:11 AM, olcott wrote:
D(D) specifies an infinite chain of H(D,D) unless D(D) is
aborted at some point. The outermost H(D,D) always has
seen a longer execution trace than any of the inner ones.
Right, *AT SOME POINT* but not nessesarily HERE.
No, the outermose has seen more execution trace then
the innerones have at the point that H aborts their
simulation.
(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
It seems like you are agreeing with me that H(D,D)==0
is correct for the above criteria.
On 3/15/2024 8:33 PM, Richard Damon wrote:
On 3/15/24 11:05 AM, olcott wrote:
On 3/15/2024 11:20 AM, olcott wrote:
Best selling author of Theory of Computation textbooks:
*Introduction To The Theory Of Computation 3RD, by sipser*
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295/
Date 10/13/2022 11:29:23 AM
*MIT Professor Michael Sipser agreed this verbatim paragraph is
correct*
(He has neither reviewed nor agreed to anything else in this paper)
(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.
*When we apply the abort criteria* (elaborated above)
Will you halt if you never abort your simulation?
*Then H(D,D) is proven to meet this criteria*
*Proof that H(D,D) meets its abort criteria*
int D(int (*x)())
{
int Halt_Status = H(x, x);
if (Halt_Status)
HERE: goto HERE;
return Halt_Status;
}
int main()
{
Output("Input_Halts = ", H(D,D));
}
machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
[00001d22][00102fc9][00000000] 55 push ebp ; begin main()
[00001d23][00102fc9][00000000] 8bec mov ebp,esp
[00001d25][00102fc5][00001cf2] 68f21c0000 push 00001cf2 ; push DD
[00001d2a][00102fc1][00001cf2] 68f21c0000 push 00001cf2 ; push D
[00001d2f][00102fbd][00001d34] e8eef7ffff call 00001522 ; call H(D,D)
H: Begin Simulation Execution Trace Stored at:113075
Address_of_H:1522
[00001cf2][00113061][00113065] 55 push ebp ; enter D(D)
[00001cf3][00113061][00113065] 8bec mov ebp,esp
[00001cf5][0011305d][00103031] 51 push ecx
[00001cf6][0011305d][00103031] 8b4508 mov eax,[ebp+08]
[00001cf9][00113059][00001cf2] 50 push eax ; push D
[00001cfa][00113059][00001cf2] 8b4d08 mov ecx,[ebp+08]
[00001cfd][00113055][00001cf2] 51 push ecx ; push D
[00001cfe][00113051][00001d03] e81ff8ffff call 00001522 ; call H(D,D) >>>> H: Recursive Simulation Detected Simulation Stopped
H(D,D) returns 0 to main()
*That was proof that H(D,D) meets its abort criteria*
H(D,D) correctly determines that itself is being called with its
same inputs and there are no conditional branch instructions between
the invocation of D(D) and its call to H(D,D).
<snip>
On 3/15/2024 3:43 PM, Richard Damon wrote:
On 3/15/24 1:37 PM, olcott wrote:
It is a fact that the behavior of D(D) after it aborts
its simulation cannot be used as abort status criteria or
no H(D,D) would ever abort its simulation.
Yes, that is a correct computational argument, but doesn't prove the criteria used is correct.
(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
It seems like you are agreeing with me that H(D,D)==0
is correct for the above criteria.
Nope.
It may be the best it can do, but since D(D) halts, then the CORRECT
SIMULATION of D(D) will reach and end...
*That statement entails this one*
You are saying that H(D,D) is incorrect to abort its simulation
because it does not need to do this after it has already aborted
its simulation. *Thus disagreeing with yourself as quoted above*
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 307 |
Nodes: | 16 (2 / 14) |
Uptime: | 100:17:10 |
Calls: | 6,850 |
Calls today: | 1 |
Files: | 12,354 |
Messages: | 5,415,286 |