On 5/21/22 5:48 PM, olcott wrote:
> 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

ERROR IN TRACE.

THE FOLLOWING DOESN'T ACTUALLY HAPPEN, AND IS A LIE>

> ...[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.

No, H is just imagining this, because it is using incorrect logic and
comes up with a wrong answer.

You are just showing YOUR technical incompitence in making your claim.

>
> ...[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.
>

ERROR. You aren't using the correct definition of a Correct Simulation,
because BY DEFINITION a correct simulation of X will exactly emulate the
actual behavior of X.

Thus the simulation that H(P,P) does, must match P(P), or it is BY
DEFINTION not correct.

If you claim that can't be done, then you have just proved the theorem
you are trying to disprove.

Note, the correct simulation CAN occur, it is just that H can't do that
and give an answer in finite time for H(P,P).