-9
$\begingroup$

Can D simulated by H terminate normally? The x86utm operating system based on an open source x86 emulator. This system enables one C function to execute another C function in debug step mode. When H simulates D it creates a separate process context for D with its own memory, stack and virtual registers. H is able to simulate D simulating itself, thus the only limit to recursive simulations is RAM.

// The following is written in C
01 int D(int (*x)())  
02 {  
03    int Halt_Status = H(x, x);  
04    if (Halt_Status)  
05      HERE: goto HERE;  
06    return Halt_Status;  
07 }  
08  
09 void main()  
10 {  
11    H(D,D);  
12 }

Execution Trace
main() calls H(D,D) that simulates D(D) at line 11

keeps repeating:
simulated D(D) calls simulated H(D,D) that simulates D(D) at line 03 ...

Is this clear enough to see that D correctly simulated by H can never terminate normally? (because D remains stuck in recursive simulation)

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

The relationship between H and D exactly matches the above specified pathological relationship.

Simulation invariant:
D correctly simulated by H cannot possibly reach its own line 04.

When one applies a simulating (partial) halt decider to the Turing machine based proofs the same non-terminating result is derived as indicated by the exact match with the above criteria.

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – D.W.
    Commented Dec 19, 2021 at 20:41

1 Answer 1

-6
$\begingroup$
// The following is written in C
01 int D(int (*x)())  
02 {  
03    int Halt_Status = H(x, x);  
04    if (Halt_Status)  
05      HERE: goto HERE;  
06    return Halt_Status;  
07 }  
08  
09 void main()  
10 {  
11    H(D,D);  
12 }

Execution Trace
main() calls H(D,D) that simulates D(D) at line 11

keeps repeating:
simulated D(D) calls simulated H(D,D) that simulates D(D) at line 03 ...

D correctly simulated by H can never terminate normally because D remains stuck in recursive simulation.

The fully operational source code of H/D and the x86utm operating system shows that H correctly matches a non-halting behavior pattern that is equivalent to infinite recursion.

H(D,D) fully operational in x86utm operating system: https://github.com/plolcott/x86utm

Source-code of several different partial halt deciders and their sample inputs. https://github.com/plolcott/x86utm/blob/master/Halt7.c

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.