Can D simulated by H terminate normally? (update)

[polcott]

Can D correctly 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 typedef int (*ptr)(); // pointer to int function
02 int H(ptr x, ptr y)   // uses x86 emulator to simulate its input
03
04 int D(ptr x)
05 {
06   int Halt_Status = H(x, x);
07   if (Halt_Status)
08     HERE: goto HERE;
09   return Halt_Status;
10 }
11
12 void main()
13 {
14   H(D,D);
15 }

Execution Trace
Line 14: main() invokes H(D,D);

keeps repeating (unless aborted)
Line 06: simulated D(D) invokes simulated H(D,D) that simulates D(D)

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

Is it dead obvious to everyone here when examining the execution
trace of lines 14 and 06 above that D correctly simulated by H cannot
possibly terminate normally by reaching its own line 09?

Termination Analyzer H is Not Fooled by Pathological Input D

https://www.researchgate.net/publication/369971402_Termination_Analyzer_H_is_Not_Fooled_by_Pathological_Input_D

 

[polcott]

cli345 already answered the original question: "So, lines 07,08,09 are never reached."
The update to this question is the link to my paper that explains the rest
of the software engineering and computer science details.
Pages 2 and 3 apply the exact same idea to the Peter Linz halting Problem proof.

 

[polcott]

When it is understood that D correctly simulated by H is the behavior
that H must report on then the halting problem's otherwise impossible
input is correctly determined to be non-halting.

We can know that D correctly simulated by H must have different behavior
than D(D) directly executed in main() because we can see (in its
execution trace shown above) exactly how the pathological relationship
between D and H changes the behavior of D relative to H.

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.
Halting problem - Wikipedia

"A decision problem is a yes-or-no question on an infinite set of
inputs" Decision problem - Wikipedia

When the halting problem is construed as requiring a correct yes/no
answer to a contradictory question it cannot be solved. The halting
problem question is only contradictory when a halt decider must divide
arbitrary finite string pairs (including non-inputs) into those that
halt on their input and those that do not. When we exclude non-inputs
then the contradiction is unreachable by D correctly simulated by H thus
has no effect.

 

[polcott]

MIT Professor Michael Sipser has agreed that the following verbatim paragraph is correct (he has not agreed to anything else in this paper)------> "If simulating halt decider H correctly simulates its input D until H correctly determines that its simulated D would never stop running unless aborted then H can abort its simulation of D and correctly report that D specifies a non-halting sequence of configurations."

 

[polcott]

https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X

 

[polcott]

ADDENDUM

(1) The source-code of H and D conclusively proves that D correctly
simulated by H cannot possibly terminate normally.

(2) The correct simulation of D by H must include the fact that
D would continue to call H until stack overflow crash unless H
aborts its simulation of D.

(3) (2) Means that D is correctly simulated by H and this correctly
simulated D is non-halting.

(4) "A decision problem is a yes-or-no question on an infinite set
of inputs" Decision problem - Wikipedia
This means that the behavior of non-inputs is not allowed to be
considered.