Would the simulation of D be infinitely nested unless simulating partial halt decider H terminated its simulation of D? (HTML)

[olcott]

Would the simulation of D be infinitely nested unless simulating partial halt decider H terminated its simulation of D?

I spent two years creating the x86utm operating system to concretely address the halting problem using a halt decider written in C. Partial halt decider H bases is halting decision on simulating its input.

The partial halt decider H invokes an x86 emulator to execute its input D in debug step mode. The input is the machine address of the input x86 function cast to a 32-bit unsigned integer. H examines the complete execution trace of D immediately after each x86 instruction of D is simulated.

#define machine_address uint32_t 

int D(u32 P)
{
  if ( H(P, P) )
    return 0;
  return 1;
}

int main()
{  
  u32 Input_Would_Halt = H((u32)D, (u32)D);
  Output("H(D,D) Would_Halt = ", Input_Would_Halt );
}

_D()
[00000cfc](01)  55                      push ebp
[00000cfd](02)  8bec                    mov ebp,esp
[00000cff](03)  8b4508                  mov eax,[ebp+08]
[00000d02](01)  50                      push eax
[00000d03](03)  8b4d08                  mov ecx,[ebp+08]
[00000d06](01)  51                      push ecx
[00000d07](05)  e800feffff              call 00000b0c
[00000d0c](03)  83c408                  add esp,+08
[00000d0f](02)  85c0                    test eax,eax
[00000d11](02)  7404                    jz 00000d17
[00000d13](02)  33c0                    xor eax,eax
[00000d15](02)  eb05                    jmp 00000d1c
[00000d17](05)  b801000000              mov eax,00000001
[00000d1c](01)  5d                      pop ebp
[00000d1d](01)  c3                      ret
Size in bytes:(0034) [00000d1d]

_main()
[00000d2c](01)  55                      push ebp
[00000d2d](02)  8bec                    mov ebp,esp
[00000d2f](01)  51                      push ecx
[00000d30](05)  68fc0c0000              push 00000cfc
[00000d35](05)  68fc0c0000              push 00000cfc
[00000d3a](05)  e8cdfdffff              call 00000b0c
[00000d3f](03)  83c408                  add esp,+08
[00000d42](03)  8945fc                  mov [ebp-04],eax
[00000d45](03)  8b45fc                  mov eax,[ebp-04]
[00000d48](01)  50                      push eax
[00000d49](05)  68c7030000              push 000003c7
[00000d4e](05)  e8a9f6ffff              call 000003fc
[00000d53](03)  83c408                  add esp,+08
[00000d56](02)  33c0                    xor eax,eax
[00000d58](02)  8be5                    mov esp,ebp
[00000d5a](01)  5d                      pop ebp
[00000d5b](01)  c3                      ret
Size in bytes:(0048) [00000d5b]

Columns
(1) Execution trace sequence number
(2) Machine address of instruction
(3) Machine address of top of stack
(4) Value of top of stack after instruction executed
(5) Number of bytes of machine code
(6) Machine language bytes
(7) Assembly language text
===============================
...[00000d2c][00101799][00000000](01)  55                      push ebp
...[00000d2d][00101799][00000000](02)  8bec                    mov ebp,esp
...[00000d2f][00101795][00000000](01)  51                      push ecx
...[00000d30][00101791][00000cfc](05)  68fc0c0000              push 00000cfc
...[00000d35][0010178d][00000cfc](05)  68fc0c0000              push 00000cfc
...[00000d3a][00101789][00000d3f](05)  e8cdfdffff              call 00000b0c
Begin Local Halt Decider Simulation at Machine Address:cfc
...[00000cfc][00211839][0021183d](01)  55                      push ebp
...[00000cfd][00211839][0021183d](02)  8bec                    mov ebp,esp
...[00000cff][00211839][0021183d](03)  8b4508                  mov eax,[ebp+08]
...[00000d02][00211835][00000cfc](01)  50                      push eax
...[00000d03][00211835][00000cfc](03)  8b4d08                  mov ecx,[ebp+08]
...[00000d06][00211831][00000cfc](01)  51                      push ecx
...[00000d07][0021182d][00000d0c](05)  e800feffff              call 00000b0c
...[00000cfc][0025c261][0025c265](01)  55                      push ebp
...[00000cfd][0025c261][0025c265](02)  8bec                    mov ebp,esp
...[00000cff][0025c261][0025c265](03)  8b4508                  mov eax,[ebp+08]
...[00000d02][0025c25d][00000cfc](01)  50                      push eax
...[00000d03][0025c25d][00000cfc](03)  8b4d08                  mov ecx,[ebp+08]
...[00000d06][0025c259][00000cfc](01)  51                      push ecx
...[00000d07][0025c255][00000d0c](05)  e800feffff              call 00000b0c
Local Halt Decider: Infinitely Nested Simulation Detected Simulation Stopped
...[00000d3f][00101795][00000000](03)  83c408                  add esp,+08
...[00000d42][00101795][00000000](03)  8945fc                  mov [ebp-04],eax
...[00000d45][00101795][00000000](03)  8b45fc                  mov eax,[ebp-04]
...[00000d48][00101791][00000000](01)  50                      push eax
...[00000d49][0010178d][000003c7](05)  68c7030000              push 000003c7
---[00000d4e][0010178d][000003c7](05)  e8a9f6ffff              call 000003fc
H(D,D) Would_Halt = 0
...[00000d53][00101795][00000000](03)  83c408                  add esp,+08
...[00000d56][00101795][00000000](02)  33c0                    xor eax,eax
...[00000d58][00101799][00000000](02)  8be5                    mov esp,ebp
...[00000d5a][0010179d][00100000](01)  5d                      pop ebp
...[00000d5b][001017a1][00000078](01)  c3                      ret
Number_of_User_Instructions(31)
Number of Instructions Executed(23833)

[infinitely_nested_simulation] non-halting behavior pattern for H(D, D)
(a) Partial halt decider H called twice in sequence from the same machine address of D.
    The calls to the partial halt decider are on lines 13 and 20.
    The same block of code from 07 to 13 immediately repeats from 14 to 20.

(b) With the same machine address parameters of D to H.
    It can be verified that both calls to H send the machine address of D as input to H.
    The call to H at 13 is preceded by a pair of push instructions at 10,12.
    The call to H at 20 is preceded by a pair of push instructions at 17,19.
    That this is the machine address of D is verified by column(4) of lines (10,12,17,19)

(c) With no conditional branch or indexed jump instructions in D.
    No conditional branch or indexed jump instructions on execution trace lines 07 to 20.

Is the return value of 0 from H to Input_Would_Halt in main() correct?

This question can be answered on the basis of whether or not the above criteria is sufficiently complete and correct and correctly applied to the provided complete execution trace of D.

-- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein