XPost: comp.theory, comp.lang.c, comp.lang.c++

The x86utm operating system was created so that every single detail of
the halting problem could be completely examined at the high level of abstraction of C/x86.

void Infinite_Loop()
{
HERE: goto HERE;
}

int main()
{
Output("Input_Halts = ", H0(Infinite_Loop));
}

_Infinite_Loop()
[00001342](01) 55 push ebp
[00001343](02) 8bec mov ebp,esp
[00001345](02) ebfe jmp 00001345
[00001347](01) 5d pop ebp
[00001348](01) c3 ret
Size in bytes:(0007) [00001348]

Begin Local Halt Decider Simulation
[00001342][00212333][00212337] 55 push ebp [00001343][00212333][00212337] 8bec mov ebp,esp [00001345][00212333][00212337] ebfe jmp 00001345 [00001345][00212333][00212337] ebfe jmp 00001345
Local Halt Decider: Infinite Loop Detected Simulation Stopped

It is clear that H0(Infinite_Loop) does correctly determine that its
input would never halt.

For any program H that might determine if programs halt, a
"pathological" program P, called with some input, can pass its own
source and its input to H and then specifically do the opposite of what
H predicts P will do. No H can exist that handles this case. https://en.wikipedia.org/wiki/Halting_problem

The relationship between the C functions H and P shown below were
defined to exactly match the above halting problem relationship.

H determines the halt status of its input by watching the behavior of
this input when it is correctly simulated by H using an x86 emulator.
When H correctly matches an infinite behavior pattern it aborts the
emulation of this input and returns 0.

#include <stdint.h>
#define u32 uint32_t

void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
return;
}

int main()
{
Output("Input_Halts = ", H((u32)P, (u32)P));
}

_P()
[00001352](01) 55 push ebp
[00001353](02) 8bec mov ebp,esp
[00001355](03) 8b4508 mov eax,[ebp+08]
[00001358](01) 50 push eax // push P
[00001359](03) 8b4d08 mov ecx,[ebp+08]
[0000135c](01) 51 push ecx // push P
[0000135d](05) e840feffff call 000011a2 // call H
[00001362](03) 83c408 add esp,+08
[00001365](02) 85c0 test eax,eax
[00001367](02) 7402 jz 0000136b
[00001369](02) ebfe jmp 00001369
[0000136b](01) 5d pop ebp
[0000136c](01) c3 ret
Size in bytes:(0027) [0000136c]

It is completely obvious that when H(P,P) correctly emulates its input
that it must emulate the first seven instructions of P. Because the
seventh instruction repeats this process we can know with complete
certainty that the emulated P never reaches its final “ret” instruction, thus never halts.

Halting problem undecidability and infinitely nested simulation (V5)

https://www.researchgate.net/publication/359984584_Halting_problem_undecidability_and_infinitely_nested_simulation_V5



--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.theory, comp.lang.c, comp.lang.c++

On 6/4/22 2:03 PM, olcott wrote:

The x86utm operating system was created so that every single detail of
the halting problem could be completely examined at the high level of abstraction of C/x86.

void Infinite_Loop()
{
  HERE: goto HERE;
}

int main()
{
  Output("Input_Halts = ", H0(Infinite_Loop));
}

_Infinite_Loop()
[00001342](01)  55              push ebp
[00001343](02)  8bec            mov ebp,esp
[00001345](02)  ebfe            jmp 00001345
[00001347](01)  5d              pop ebp
[00001348](01)  c3              ret
Size in bytes:(0007) [00001348]

Begin Local Halt Decider Simulation
[00001342][00212333][00212337] 55         push ebp [00001343][00212333][00212337] 8bec       mov ebp,esp [00001345][00212333][00212337] ebfe       jmp 00001345 [00001345][00212333][00212337] ebfe       jmp 00001345
Local Halt Decider: Infinite Loop Detected Simulation Stopped

It is clear that H0(Infinite_Loop) does correctly determine that its
input would never halt.

For any program H that might determine if programs halt, a
"pathological" program P, called with some input, can pass its own
source and its input to H and then specifically do the opposite of what
H predicts P will do. No H can exist that handles this case. https://en.wikipedia.org/wiki/Halting_problem

The relationship between the C functions H and P shown below were
defined to exactly match the above halting problem relationship.

H determines the halt status of its input by watching the behavior of
this input when it is correctly simulated by H using an x86 emulator.
When H correctly matches an infinite behavior pattern it aborts the
emulation of this input and returns 0.

And what pattern do you claim to be a CORRECT infinite behavior pattern
that actually occurs in the simulation of P(P) that, when is programmed
in H (since if it isn't, H can't detect it and give the answer) results
in the actual execution/ CORRECT SIMULATION of this to not halt.

Remember, if H detects it and H(P,P) returns 0, then the H(P,P) called
by P(P) will also receive that answer, and thus halt.

Remember also, the DEFINITION of the Halting Problem is DEFINED to be
based on the HALTING of the ACTUAL MACHINE the input represents, so that
is what we get to look at.

Remember also, the PROGRAM P includes all the code that it executes,
which include its copy of H (so its emulation trace needs to show that).

#include <stdint.h>
#define u32 uint32_t

void P(u32 x)
{
  if (H(x, x))
    HERE: goto HERE;
  return;
}

int main()
{
  Output("Input_Halts = ", H((u32)P, (u32)P));
}

_P()
[00001352](01)  55              push ebp
[00001353](02)  8bec            mov ebp,esp
[00001355](03)  8b4508          mov eax,[ebp+08]
[00001358](01)  50              push eax      // push P [00001359](03)  8b4d08          mov ecx,[ebp+08]
[0000135c](01)  51              push ecx      // push P [0000135d](05)  e840feffff      call 000011a2 // call H [00001362](03)  83c408          add esp,+08
[00001365](02)  85c0            test eax,eax
[00001367](02)  7402            jz 0000136b
[00001369](02)  ebfe            jmp 00001369
[0000136b](01)  5d              pop ebp
[0000136c](01)  c3              ret
Size in bytes:(0027) [0000136c]

It is completely obvious that when H(P,P) correctly emulates its input
that it must emulate the first seven instructions of P. Because the
seventh instruction repeats this process we can know with complete
certainty that the emulated P never reaches its final “ret” instruction, thus never halts.

Nope. The CORRECT emulation of this input is the first seven
instructions of P, followed by the emulation of the instructions in H
emulating the instructions in P, not just the emulations of the
instructions of P again. That acts like H just immediately called P,
which is NOT its correct behavior.

You are looking at the wrong stuff.

Halting problem undecidability and infinitely nested simulation (V5)

https://www.researchgate.net/publication/359984584_Halting_problem_undecidability_and_infinitely_nested_simulation_V5

You are just showing how little you understand how Computers work.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.theory, comp.lang.c, comp.lang.c++

On Sat, 4 Jun 2022 13:03:54 -0500
olcott <NoOne@NoWhere.com> wrote:

The x86utm operating system was created so that every single detail
of the halting problem could be completely examined at the high level
of abstraction of C/x86.

void Infinite_Loop()
{
HERE: goto HERE;
}

int main()
{
Output("Input_Halts = ", H0(Infinite_Loop));
}

_Infinite_Loop()
[00001342](01) 55 push ebp
[00001343](02) 8bec mov ebp,esp
[00001345](02) ebfe jmp 00001345
[00001347](01) 5d pop ebp
[00001348](01) c3 ret
Size in bytes:(0007) [00001348]

Begin Local Halt Decider Simulation
[00001342][00212333][00212337] 55 push ebp [00001343][00212333][00212337] 8bec mov ebp,esp [00001345][00212333][00212337] ebfe jmp 00001345 [00001345][00212333][00212337] ebfe jmp 00001345
Local Halt Decider: Infinite Loop Detected Simulation Stopped

It is clear that H0(Infinite_Loop) does correctly determine that its
input would never halt.

For any program H that might determine if programs halt, a
"pathological" program P, called with some input, can pass its own
source and its input to H and then specifically do the opposite of
what H predicts P will do. No H can exist that handles this case. https://en.wikipedia.org/wiki/Halting_problem

The relationship between the C functions H and P shown below were
defined to exactly match the above halting problem relationship.

H determines the halt status of its input by watching the behavior of
this input when it is correctly simulated by H using an x86 emulator.
When H correctly matches an infinite behavior pattern it aborts the emulation of this input and returns 0.

#include <stdint.h>
#define u32 uint32_t

void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
return;
}

int main()
{
Output("Input_Halts = ", H((u32)P, (u32)P));
}

_P()
[00001352](01) 55 push ebp
[00001353](02) 8bec mov ebp,esp
[00001355](03) 8b4508 mov eax,[ebp+08]
[00001358](01) 50 push eax // push P
[00001359](03) 8b4d08 mov ecx,[ebp+08]
[0000135c](01) 51 push ecx // push P
[0000135d](05) e840feffff call 000011a2 // call H
[00001362](03) 83c408 add esp,+08
[00001365](02) 85c0 test eax,eax
[00001367](02) 7402 jz 0000136b
[00001369](02) ebfe jmp 00001369
[0000136b](01) 5d pop ebp
[0000136c](01) c3 ret
Size in bytes:(0027) [0000136c]

It is completely obvious that when H(P,P) correctly emulates its
input that it must emulate the first seven instructions of P. Because
the seventh instruction repeats this process we can know with
complete certainty that the emulated P never reaches its final “ret” instruction, thus never halts.

Halting problem undecidability and infinitely nested simulation (V5)

https://www.researchgate.net/publication/359984584_Halting_problem_undecidability_and_infinitely_nested_simulation_V5

Your logic that decides rather to execute the infinite loop is
predicated on you detecting an infinitely recursive call of the decider
however the proofs you are attempting to refute do not do this so
whatever you are trying to achieve has nothing to do with the Halting
Problem.

/Flibble

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)