**Does H correctly decide that P never halts?**

(The C/x86 source-code for P is provided below)

The only thing that we need to know about H is that it continues to simulate its input with an x86 emulator until the behavior of this input matches a non-halting behavior pattern. If a non-halting behavior pattern is matched H aborts its input and returns 0 for non-halting input. Otherwise H remains a pure x86 emulator and returns 1 for halting when its input terminates.

The x86utm operating system was created so that the halting problem could be examined concretely in the high level language of C. UTM tape elements are 32-bit unsigned integers. H is a function written in C that analyzes the x86 machine language of other functions written in C. H is able to recognize simple cases of infinite recursion and infinite loops.

```
// Simplified Linz Ĥ (Linz:1990:319)
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}
int main()
{
Output("Input_Halts = ", H((u32)P, (u32)P));
}
```

H acts as a pure x86 simulator until its input demonstrates non-halting behavior. It is common knowledge that when-so-ever the pure simulation of the machine description of a machine never halts on its input that this logically entails that this machine never halts on its input. This proves that H uses the same halting criteria as the halting problem.

Because H acts as a pure simulator of its input until after it makes its halt status decision we know that the behavior of H cannot possibly have any effect on the behavior of P thus the behavior of H can be totally ignored in any halt status decision.

Using the above reasoning we can know that when the x86 execution trace of P on input P shows that there is no code in P that escapes the infinitely nested simulation of P on input P, then we know that P on input P meets the definition of a computation that never halts: (a pure simulation that never halts).

```
_P()
(00000c36)(01) 55 push ebp
(00000c37)(02) 8bec mov ebp,esp
(00000c39)(03) 8b4508 mov eax,(ebp+08)
(00000c3c)(01) 50 push eax
(00000c3d)(03) 8b4d08 mov ecx,(ebp+08)
(00000c40)(01) 51 push ecx
(00000c41)(05) e820fdffff call 00000966
(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
(00000c5e)(05) 68360c0000 push 00000c36
(00000c63)(05) e8fefcffff call 00000966
(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)
```

**Execution Trace of H(P,P)**

```
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
(00000c5e)(00101722)(00000c36) 68360c0000 push 00000c36
(00000c63)(0010171e)(00000c68) e8fefcffff call 00000966
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
(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
Local Halt Decider: Infinite Recursion Detected Simulation Stopped
```

In the above 14 instructions of the simulation of P(P) we can see that the first 7 instructions of P are repeated. The end of this sequence of 7 instructions P calls H with its own machine address as the parameters to H: H(P,P). Because H only examines the behavior of its inputs and ignores its own behavior when H(P,P) is called we only see the first instruction of P being simulated.

Anyone knowing the x86 language well enough can see that none of these 7 simulated instructions of P have any escape from their infinitely repeating behavior pattern. When H recognizes this infinitely repeating pattern it aborts its simulation of P(P) and reports that its input: (P,P) would never halt on its input.

```
(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)
```

**I have provided:**

(a) the assembly language source-code for P,

(b) the x86 execution trace of P,

(c) stated that H only acts as a pure x86 emulator until after its makes its halt status decision.

It should be clear from the execution trace of P that P is stuck in infinitely nested simulation. The same 8 instructions are repeated and these instructions have no escape from their infinite repetition.

To eliminate the pathological self-reference(polcott 2004) from the halting problem such that there is no feedback loop between what the halt decider decides and how the input behaves the simulating halt decider simply watches what the input does without interfering at all.

As soon as the simulating halt decider determines that the simulation of the input on its input would never halt (the conventional definition of non-halting) it aborts the simulation of its inputs and reports that its input does not halt.