Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Can D simulated by H terminate normally?

Skip to first unread message


May 19, 2023, 11:52:58 AM5/19/23
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 }
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*

H(D,D) fully operational in x86utm operating system:

Source-code of several different partial halt deciders and their sample

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*

*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
0 new messages