How do we know H(P,P)==0 is the correct halt status for the input to H? (HTML for fixed width font)
olcott
the Turing machine halting problem. Simply stated,
the problem
is: given the description of a Turing machine M and an input w,
does M, when started in the initial configuration q0w, perform
a
computation that eventually halts? (Linz:1990:317).
In computability theory, the halting problem is the
problem of
determining, from a description of an arbitrary computer
program
and an input, whether the program will finish running, or
continue
to run forever. https://en.wikipedia.org/wiki/Halting_problem
A Turing machine is said to halt whenever it reaches a
configuration
for which δ is not defined; this is possible because δ is a
partial
function. In fact, we will assume that no transitions are
defined for
any final state, so the Turing machine will halt whenever it
enters a
final state. (Linz:1990:234)
Halting computation is any computation
that eventually reaches its own final state. This criteria divides
computations that halt from those that merely stop running because
their simulation was aborted.
This exact same analysis always applies to the input to H(P,P) no
matter how it is called including this example:
int main()
{
P((u32)P);
}
Because the halting problem only requires that the (at least
partial) halt decider decide its input correctly the fact that the
direct invocation of P(P) is not an input to H, means that it is
not relevant to the halting problem.
The P(P) of main() only halts because H(P,P) correctly decides
that its input never halts. This cause-and-effect relationship
between the simulated P and the executed P proves that the
simulated P and the executed P are distinctly different
computations.
Because they are different computations the fact that the executed
P halts does not contradict the fact that the simulated P never
halts.
While H remains in pure simulation mode simulating the input to
H(P,P) this simulated input never halts thus conclusively proving
that H decides this input correctly.
Because H only acts as a pure simulator of its input until after
its halt status decision has been made it has no behavior that can
possibly effect the behavior of its input. Because of this H
screens out its own address range in every execution trace that it
examines. This is why we never see any instructions of H in any
execution trace after an input calls H.
// Simplified Linz Ĥ (Linz:1990:319)
// Strachey(1965) CPL translated to C
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}
int main()
{
Output("Input_Halts = ", H((u32)P, (u32)P));
}
_P()
[00000c36](01) 55 push ebp
[00000c37](02) 8bec mov ebp,esp
[00000c39](03) 8b4508 mov eax,[ebp+08] // 2nd Param
[00000c3c](01) 50 push eax
[00000c3d](03) 8b4d08 mov ecx,[ebp+08] // 1st Param
[00000c40](01) 51 push ecx
[00000c41](05) e820fdffff call 00000966 // call H
[00000c46](03) 83c408 add esp,+08
[00000c49](02) 85c0 test eax,eax
[00000c4b](02) 7402 jz 00000c4f
[00000c4d](02) ebfe jmp 00000c4d
[00000c4f](01) 5d pop ebp
[00000c50](01) c3 ret
Size in bytes:(0027) [00000c50]
_main()
[00000c56](01) 55 push ebp
[00000c57](02) 8bec mov ebp,esp
[00000c59](05) 68360c0000 push 00000c36 // push P
[00000c5e](05) 68360c0000 push 00000c36 // push P
[00000c63](05) e8fefcffff call 00000966 // call H(P,P)
[00000c68](03) 83c408 add esp,+08
[00000c6b](01) 50 push eax
[00000c6c](05) 6857030000 push 00000357
[00000c71](05) e810f7ffff call 00000386
[00000c76](03) 83c408 add esp,+08
[00000c79](02) 33c0 xor eax,eax
[00000c7b](01) 5d pop ebp
[00000c7c](01) c3 ret
Size in bytes:(0039) [00000c7c]
machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
[00000c56][0010172a][00000000] 55 push ebp
[00000c57][0010172a][00000000] 8bec mov ebp,esp
[00000c59][00101726][00000c36] 68360c0000 push 00000c36 // push
P
[00000c5e][00101722][00000c36] 68360c0000 push 00000c36 // push
P
[00000c63][0010171e][00000c68] e8fefcffff call 00000966 // call
H(P,P)
Begin Local Halt Decider Simulation at Machine
Address:c36
[00000c36][002117ca][002117ce] 55 push ebp
[00000c37][002117ca][002117ce] 8bec mov ebp,esp
[00000c39][002117ca][002117ce] 8b4508 mov eax,[ebp+08]
[00000c3c][002117c6][00000c36] 50 push eax //
push P
[00000c3d][002117c6][00000c36] 8b4d08 mov ecx,[ebp+08]
[00000c40][002117c2][00000c36] 51 push ecx //
push P
[00000c41][002117be][00000c46] e820fdffff call 00000966 //
call H(P,P)
We can see that the first seven lines of P repeat. P calls
H(P,P) that simulates P(P) that calls H(P,P) in a cycle the never
stops unless H stops simulating its input. When H does stop
simulating its input P never reaches its final state of [00000c50]
therefore never halts even though it stops running.
[00000c36][0025c1f2][0025c1f6] 55 push ebp
[00000c37][0025c1f2][0025c1f6] 8bec mov ebp,esp
[00000c39][0025c1f2][0025c1f6] 8b4508 mov eax,[ebp+08]
[00000c3c][0025c1ee][00000c36] 50 push eax //
push P
[00000c3d][0025c1ee][00000c36] 8b4d08 mov ecx,[ebp+08]
[00000c40][0025c1ea][00000c36] 51 push ecx //
push P
[00000c41][0025c1e6][00000c46] e820fdffff call 00000966 //
call H(P,P)
Local Halt Decider: Infinite Recursion Detected
Simulation Stopped
[00000c68][0010172a][00000000] 83c408 add esp,+08
[00000c6b][00101726][00000000] 50 push eax
[00000c6c][00101722][00000357] 6857030000 push 00000357
[00000c71][00101722][00000357] e810f7ffff call 00000386
Input_Halts = 0
[00000c76][0010172a][00000000] 83c408 add esp,+08
[00000c79][0010172a][00000000] 33c0 xor eax,eax
[00000c7b][0010172e][00100000] 5d pop ebp
[00000c7c][00101732][00000068] c3 ret
Number_of_User_Instructions(27)
Number of Instructions Executed(23721)
Strachey, C 1965. An impossible program The Computer
Journal, Volume 7, Issue 4, January 1965, Page 313, https://doi.org/10.1093/comjnl/7.4.313
Linz, Peter 1990. An Introduction to Formal Languages and
Automata. Lexington/Toronto: D. C. Heath and Company.
--
Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
olcott
>> the Turing machine halting problem. Simply stated, the problem
>> is: given the description of a Turing machine M and an input w,
>> does M, when started in the initial configuration q0w, perform a
>> computation that eventually halts? (Linz:1990:317).
>
> is that there does not exist a Turing Machine which, given the
> description of another Turing Machine, can determine whether
> or not the second Turing Machine halts. The proof is that if such
> a first Turing Machine were to exist we can construction a
> second machine for which the first machine determines halting
> incorrectly.
// Simplified Linz Ĥ (Linz:1990:319)
// Strachey(1965) CPL translated to C
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}
proofs is to show how H correctly decides that its input H(P,P) never
halts.
I have done that, yet people deliberately make sure that to never
examine the actual analysis of the halt status decision of the actual
input to H. Instead they always dishonestly change the subject to
another computation that is not the input to H.