Can D simulated by H terminate normally?
The following code is executed in 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.
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
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
This paper shows how that same idea is applied to the Peter Linz Turing
machine based Halting Problem Proofs.
*Simulating (partial) Halt Deciders Defeat the Halting Problem Proofs*
https://www.researchgate.net/publication/369971402_Simulating_partial_Halt_Deciders_Defeat_the_Halting_Problem_Proofs
*At 10/13/2022 11:29 AM in an email*
MIT Professor Michael Sipser has agreed that the following verbatim
paragraph is correct (he has not agreed to anything else):
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.
It is clear that H does determine the halt status of D precisely
according to that criteria.
--
Copyright 2023 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)