Actual debug trace of Sipser H() deciding halting Sipser D()

[olcott]

I spent about 3000 hours creating the x86utm operating system that
executes x86 based virtual machines using a very excellent x86 emulator.
It simulates the execution of the COFF object file output of the
Microsoft C compiler using x86 emulation.

x86 language ≡ von Neumann architecture ≡ UTM ≡ RASP Machine
It is common knowledge that all x86 based programs are computationally
equivalent to UTMs for every computation that does not require more
memory than they have.

Here is D (computational equivalent to the Sipser D) being correctly
decided by H() (computational equivalent to the Sipser H).

http://www.liarparadox.org/sipser_165.pdf

Sipser, Michael 1997. Introduction to the Theory of Computation. Boston:
PWS Publishing Company (165-167)

u32 D(u32 P)
{
u32 Input_Halts = H(P, P);
if (Input_Halts)
return 0; // Indicating not halting
else
return 1; // Indicating halting
}


#define HALT __asm hlt

int main()
{
H((u32)D, (u32)D);
HALT;
}


_D()
[0000066c](01) 55 push ebp
[0000066d](02) 8bec mov ebp,esp
[0000066f](01) 51 push ecx
[00000670](03) 8b4508 mov eax,[ebp+08]
[00000673](01) 50 push eax
[00000674](03) 8b4d08 mov ecx,[ebp+08]
[00000677](01) 51 push ecx
[00000678](05) e8cffdffff call 0000044c
[0000067d](03) 83c408 add esp,+08
[00000680](03) 8945fc mov [ebp-04],eax
[00000683](04) 837dfc00 cmp dword [ebp-04],+00
[00000687](02) 7406 jz 0000068f
[00000689](02) 33c0 xor eax,eax
[0000068b](02) eb07 jmp 00000694
[0000068d](02) eb05 jmp 00000694
[0000068f](05) b801000000 mov eax,00000001
[00000694](02) 8be5 mov esp,ebp
[00000696](01) 5d pop ebp
[00000697](01) c3 ret

_main()
[0000069c](01) 55 push ebp
[0000069d](02) 8bec mov ebp,esp
[0000069f](05) 686c060000 push 0000066c
[000006a4](05) 686c060000 push 0000066c
[000006a9](05) e89efdffff call 0000044c
[000006ae](03) 83c408 add esp,+08
[000006b1](01) f4 hlt
[000006b2](01) 5d pop ebp
[000006b3](01) c3 ret

Output_Debug_Trace() Trace_List.size(20)
[0000069c](01) 55 push ebp
[0000069d](02) 8bec mov ebp,esp
[0000069f](05) 686c060000 push 0000066c
[000006a4](05) 686c060000 push 0000066c
[000006a9](05) e89efdffff call 0000044c // CALL H() from main()
[0000066c](01) 55 push ebp
[0000066d](02) 8bec mov ebp,esp
[0000066f](01) 51 push ecx
[00000670](03) 8b4508 mov eax,[ebp+08]
[00000673](01) 50 push eax
[00000674](03) 8b4d08 mov ecx,[ebp+08]
[00000677](01) 51 push ecx
[00000678](05) e8cffdffff call 0000044c // CALL H() from D()
[0000066c](01) 55 push ebp
[0000066d](02) 8bec mov ebp,esp
[0000066f](01) 51 push ecx
[00000670](03) 8b4508 mov eax,[ebp+08]
[00000673](01) 50 push eax
[00000674](03) 8b4d08 mov ecx,[ebp+08]
[00000677](01) 51 push ecx
[00000678](05) e8cffdffff call 0000044c // CALL H() from D()
The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:

A second call to the same function from the same machine address without
any control flow instructions in-between** is always a case of infinite
recursion: recursion with no escape from recursion.

** A simplification of the original criteria to make the proof easier to
understand.

The halt decider uses this criteria to decide that an input expresses
non-halting behavior:

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
> A computation that would not halt if its simulation were not
> halted is indeed a non-halting computation.

On Saturday, November 28, 2020 at 2:00:28 PM UTC-8, olcott wrote:
> Every computation that would not halt if its simulation
> were not halted is by logical necessity a non-halting computation.


--
Copyright 2020 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein

[Mr Flibble]

On 08/12/2020 18:10, olcott wrote:
> I spent about 3000 hours creating the x86utm operating system that executes x86 based virtual machines using a very excellent x86 emulator. It simulates the execution of the COFF object file output of the Microsoft C compiler using x86 emulation.
>
> x86 language ≡ von Neumann architecture ≡ UTM ≡ RASP Machine
> It is common knowledge that all x86 based programs are computationally equivalent to UTMs for every computation that does not require more memory than they have.
>
> Here is D (computational equivalent to the Sipser D) being correctly decided by H() (computational equivalent to the Sipser H).
>

[snip]

In troll theory, the olcott problem is the problem of determining, from a number of arbitrary Usenet posts, whether an olcott will stop trolling, or continue to troll forever. Alan Turing proved in 1936 that a general algorithm to solve the olcott problem for all possible olcott instances cannot exist.

For any troll decider, d, that might determine if olcotts stop trolling, a "pathological" olcott, o, stimulated by a reply to one of its Usenet posts, will respond with a delusional reply indistinguishable from genuine troll. A key part of the proof is a variation on Poe's law, an adage of Internet culture stating that, without a clear indicator of the author's intent, it is impossible to differentiate trolling with the output of the mentally ill and can be mistaken by some readers for a sincere expression of the argument being presented. It is one of the first cases of decision problems proven to be unsolvable. This proof is significant to practical computing efforts, as it warns that much time can be wasted engaging with an olcott.

/Flibble

--
😎