XPost: comp.theory, sci.logic, sci.math

A simulating halt decider computes the mapping from its inputs to its
own final states on the basis of the behavior of its correctly simulated
input.

All of the conventional halting problem counter-example inputs are
simply rejected by a simulating halt decider as non-halting because they
fail to meet the Linz definition of halting:

computation that halts … the Turing machine will halt whenever it enters
a final state. (Linz:1990:234)

USENET comp.theory: On 4/11/2022 3:19 PM, Malcolm McLean wrote:

PO's idea is to have a simulator with an infinite cycle detector.
You would achieve this by modifying a UTM, so describing it as
a "modified UTM", or "acts like a UTM until it detects an infinite
cycle", is reasonable. And such a machine is a fairly powerful
halt decider. Even if the infinite cycle detector isn't very
sophisticated, it will still catch a large subset of non-halting
machines.

The following simplifies the syntax for the definition of the Linz
Turing machine Ĥ.

There is no need for the infinite loop after H.qy because it is never
reached.

Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy
If the correctly simulated input ⟨Ĥ⟩ ⟨Ĥ⟩ to H would reach its own final
state.

Ĥ.q0 ⟨Ĥ⟩ ⊢* H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
If the correctly simulated input ⟨Ĥ⟩ ⟨Ĥ⟩ to H would never reach its own
final state.

When Ĥ is applied to ⟨Ĥ⟩
Ĥ copies its input ⟨Ĥ0⟩ to ⟨Ĥ1⟩ then H simulates ⟨Ĥ0⟩ ⟨Ĥ1⟩

Then these steps would keep repeating: (unless their simulation is aborted)
Ĥ0 copies its input ⟨Ĥ1⟩ to ⟨Ĥ2⟩ then H0 simulates ⟨Ĥ1⟩ ⟨Ĥ2⟩
Ĥ1 copies its input ⟨Ĥ2⟩ to ⟨Ĥ3⟩ then H1 simulates ⟨Ĥ2⟩ ⟨Ĥ3⟩
Ĥ2 copies its input ⟨Ĥ3⟩ to ⟨Ĥ4⟩ then H2 simulates ⟨Ĥ3⟩ ⟨Ĥ4⟩...

Since we can see that the simulated input: ⟨Ĥ0⟩ to H would never reach
its own final state of ⟨Ĥ0.qy⟩ or ⟨Ĥ0.qn⟩ we know that it is non-halting.


Here is the same thing that has all of the missing Linz ⊢* wildcard
state transitions filled in by fully operational code. H uses an x86
emulator to simulate its input one x86 instruction at a time.

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

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

_P()
[000009d6](01) 55 push ebp
[000009d7](02) 8bec mov ebp,esp
[000009d9](03) 8b4508 mov eax,[ebp+08]
[000009dc](01) 50 push eax // push P
[000009dd](03) 8b4d08 mov ecx,[ebp+08]
[000009e0](01) 51 push ecx // push P
[000009e1](05) e840feffff call 00000826 // call H
[000009e6](03) 83c408 add esp,+08
[000009e9](02) 85c0 test eax,eax
[000009eb](02) 7402 jz 000009ef
[000009ed](02) ebfe jmp 000009ed
[000009ef](01) 5d pop ebp
[000009f0](01) c3 ret // Final state
Size in bytes:(0027) [000009f0]

Begin Local Halt Decider Simulation
...[000009d6][00211368][0021136c] 55 push ebp // enter P ...[000009d7][00211368][0021136c] 8bec mov ebp,esp ...[000009d9][00211368][0021136c] 8b4508 mov eax,[ebp+08] ...[000009dc][00211364][000009d6] 50 push eax // Push P ...[000009dd][00211364][000009d6] 8b4d08 mov ecx,[ebp+08] ...[000009e0][00211360][000009d6] 51 push ecx // Push P ...[000009e1][0021135c][000009e6] e840feffff call 00000826 // Call H ...[000009d6][0025bd90][0025bd94] 55 push ebp // enter P ...[000009d7][0025bd90][0025bd94] 8bec mov ebp,esp ...[000009d9][0025bd90][0025bd94] 8b4508 mov eax,[ebp+08] ...[000009dc][0025bd8c][000009d6] 50 push eax // Push P ...[000009dd][0025bd8c][000009d6] 8b4d08 mov ecx,[ebp+08] ...[000009e0][0025bd88][000009d6] 51 push ecx // Push P ...[000009e1][0025bd84][000009e6] e840feffff call 00000826 // Call H
Local Halt Decider: Infinite Recursion Detected Simulation Stopped

Because the correctly simulated input to H(P,P) cannot possibly reach
its own final state at [000009f0] it is necessarily correct for H to
reject this input as non-halting.

As long as the correctly simulated input to H(P,P) would never halt then
we know it is non-halting.

Anyone that disagrees with this is a liar by definition.
Anyone that disagrees with this is a liar by definition.
Anyone that disagrees with this is a liar by definition.




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)