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

Halting problem undecidability and infinitely nested simulation (V5)

This is an explanation of a key new insight into the halting problem
provided in the language of software engineering. Technical computer
science terms are explained using software engineering terms.

To fully understand this paper a software engineer must be an expert in:
the C programming language, the x86 programming language, exactly how C translates into x86 and what an x86 processor emulator is. No knowledge
of the halting problem is required.

The computer science term “halting” means that a Turing Machine
terminated normally reaching its last instruction known as its “final state”. This is the same idea as when a function returns to its caller
as opposed to and contrast with getting stuck in an infinite loop or
infinite recursion.

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. Alan
Turing proved
in 1936 that a general algorithm to solve the halting problem for
all possible
program-input pairs cannot exist.

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

Technically a halt decider is a program that computes the mapping from a
pair of input finite strings to its own accept or reject state based on
the actual behavior specified by these finite strings. In other words
it determines whether or not its input would halt and returns 0 or 1 accordingly.

Computable functions are the basic objects of study in
computability theory.
Computable functions are the formalized analogue of the intuitive
notion of
algorithms, in the sense that a function is computable if there
exists an algorithm
that can do the job of the function, i.e. given an input of the
function domain it
can return the corresponding output.
https://en.wikipedia.org/wiki/Computable_function

The most definitive way to determine the actual behavior of the actual
input is to simply simulate this input and watch its behavior. This is
the ultimate measure of the actual behavior of the input. A simulating
halt decider (SHD) simulates its input and determines the halt status of
this input on the basis of the behavior of this correctly simulated of
its input.

The x86utm operating system was created so that all of the details of
the the halting problem counter-example could be examined at the much
higher level of abstraction of the C/x86 computer languages. It is based
on a very powerful x86 emulator.
The function named P was defined to do the opposite of whatever H
reports that it will do. If H(P,P) reports that its input halts, P
invokes an infinite loop. If H(P,P) reports that its input is
non-halting, P immediately halts.

The technical computer science term "halt" means that a program will
reach its last instruction technically called its final state. For P
this would be its machine address [0000136c].

H simulates its input one x86 instruction at a time using an x86
emulator. As soon as H(P,P) detects the same infinitely repeating
pattern (that we can all see), it aborts its simulation and rejects its
input.

Anyone that is an expert in the C programming language, the x86
programming language, exactly how C translates into x86 and what an x86 processor emulator is can easily verify that the correctly simulated
input to H(P,P) by H specifies a non-halting sequence of configurations.

Software engineering experts can reverse-engineer what the correct x86 emulation of the input to H(P,P) would be for one emulation and one
nested emulation thus confirming that the provided execution trace is
correct. They can do this entirely on the basis of the x86 source-code
for P with no need to see the source-code or execution trace of H.

The function named H continues to simulate its input using an x86
emulator until this input either halts on its own or H detects that it
would never halt. If its input halts H returns 1. If H detects that its
input would never halt H 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]

_main()
[00001372](01) 55 push ebp
[00001373](02) 8bec mov ebp,esp
[00001375](05) 6852130000 push 00001352 // push P
[0000137a](05) 6852130000 push 00001352 // push P
[0000137f](05) e81efeffff call 000011a2 // call H
[00001384](03) 83c408 add esp,+08
[00001387](01) 50 push eax
[00001388](05) 6823040000 push 00000423 // "Input_Halts = " [0000138d](05) e8e0f0ffff call 00000472 // call Output
[00001392](03) 83c408 add esp,+08
[00001395](02) 33c0 xor eax,eax
[00001397](01) 5d pop ebp
[00001398](01) c3 ret
Size in bytes:(0039) [00001398]

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= ============= ...[00001372][0010229e][00000000] 55 push ebp ...[00001373][0010229e][00000000] 8bec mov ebp,esp ...[00001375][0010229a][00001352] 6852130000 push 00001352 // push P ...[0000137a][00102296][00001352] 6852130000 push 00001352 // push P ...[0000137f][00102292][00001384] e81efeffff call 000011a2 // call H

Begin Local Halt Decider Simulation Execution Trace Stored at:212352 ...[00001352][0021233e][00212342] 55 push ebp // enter P ...[00001353][0021233e][00212342] 8bec mov ebp,esp ...[00001355][0021233e][00212342] 8b4508 mov eax,[ebp+08] ...[00001358][0021233a][00001352] 50 push eax // push P ...[00001359][0021233a][00001352] 8b4d08 mov ecx,[ebp+08] ...[0000135c][00212336][00001352] 51 push ecx // push P ...[0000135d][00212332][00001362] e840feffff call 000011a2 // call H ...[00001352][0025cd66][0025cd6a] 55 push ebp // enter P ...[00001353][0025cd66][0025cd6a] 8bec mov ebp,esp ...[00001355][0025cd66][0025cd6a] 8b4508 mov eax,[ebp+08] ...[00001358][0025cd62][00001352] 50 push eax // push P ...[00001359][0025cd62][00001352] 8b4d08 mov ecx,[ebp+08] ...[0000135c][0025cd5e][00001352] 51 push ecx // push P ...[0000135d][0025cd5a][00001362] e840feffff call 000011a2 // call H
Local Halt Decider: Infinite Recursion Detected Simulation Stopped

H sees that P is calling the same function from the same machine address
with identical parameters, twice in sequence. This is the infinite
recursion (infinitely nested simulation) non-halting behavior pattern.

...[00001384][0010229e][00000000] 83c408 add esp,+08 ...[00001387][0010229a][00000000] 50 push eax ...[00001388][00102296][00000423] 6823040000 push 00000423 //
"Input_Halts = "
---[0000138d][00102296][00000423] e8e0f0ffff call 00000472 // call Output Input_Halts = 0
...[00001392][0010229e][00000000] 83c408 add esp,+08 ...[00001395][0010229e][00000000] 33c0 xor eax,eax ...[00001397][001022a2][00100000] 5d pop ebp ...[00001398][001022a6][00000004] c3 ret
Number_of_User_Instructions(1)
Number of Instructions Executed(15892) = 237 pages

The correct simulation of the input to H(P,P) and the direct execution
of P(P) are not computationally equivalent thus need not have the same
halting behavior.

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