Welcome to Code Forum!

Join a community that supports you and your coding journey from day one. We strive to be a friendly, supportive community that empowers everyone to be better developers. By registering with us, you'll be able to discuss, share and private message with other members of our community.

SignUp Now!
  • Guest, before posting your code please take these rules into consideration:
    • It is required to use our BBCode feature to display your code. While within the editor click < / > or >_ and place your code within the BB Code prompt. This helps others with finding a solution by making it easier to read and easier to copy.
    • You can also use markdown to share your code. When using markdown your code will be automatically converted to BBCode. For help with markdown check out the markdown guide.
    • Don't share a wall of code. All we want is the problem area, the code related to your issue.

    GIF shows where to locate </> in the thread and or post editor toolbar.
    To learn more about how to use our BBCode feature, review our "How to post your code into threads" here.

    Thank you, Code Forum.

Can D simulated by H terminate normally?

P

polcott

Active Coder
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.

Code: 
// 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   D(D);
15 }

Execution Trace
Line 14: main() invokes 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 its own line 09.

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?
 
Sort by date Sort by votes
I think that can be a good introduction to the halting problem.
  • a: line 12: main() calls D(D)
  • b: line 04: D(D) is called
  • c: line 05: D enters its code
  • d: line 06: D calls H(D,D) that calls D(D) in simulation mode
  • e: line 04: D(D) is called (in simulation mode)
  • f: line 05: D enters its code (in simulation mode)
  • g: line 06: D calls H(D,D) (in simulation mode) that calls D(D) in simulation mode
  • goto e:
So, lines 07,08,09 are never reached.
Then, one can try to imagine a H function that always returns true or false.
 
Upvote 1 Downvote
cli345 said:
I think that can be a good introduction to the halting problem.
  • a: line 12: main() calls D(D)
  • b: line 04: D(D) is called
  • c: line 05: D enters its code
  • d: line 06: D calls H(D,D) that calls D(D) in simulation mode
  • e: line 04: D(D) is called (in simulation mode)
  • f: line 05: D enters its code (in simulation mode)
  • g: line 06: D calls H(D,D) (in simulation mode) that calls D(D) in simulation mode
  • goto e:
So, lines 07,08,09 are never reached.
Then, one can try to imagine a H function that always returns true or false.
Click to expand...
Yes that is exactly the
cli345 said:
I think that can be a good introduction to the halting problem.
  • a: line 12: main() calls D(D)
  • b: line 04: D(D) is called
  • c: line 05: D enters its code
  • d: line 06: D calls H(D,D) that calls D(D) in simulation mode
  • e: line 04: D(D) is called (in simulation mode)
  • f: line 05: D enters its code (in simulation mode)
  • g: line 06: D calls H(D,D) (in simulation mode) that calls D(D) in simulation mode
  • goto e:
So, lines 07,08,09 are never reached.
Then, one can try to imagine a H function that always returns true or false.
Click to expand...
Yes that is very good. If H is watching the steps of its simulated input H could recognize a dynamic behavior pattern that is similar to infinite recursion. On this basis H could abort its simulation of D and reject this input as non halting (never terminating normally).
 
Upvote 1 Downvote
Good idea! It's transformed to:
  • a: line 12: main() calls D(D)
  • b: line 04: D(D) is called
  • c: line 05: D enters its code
  • d: line 06: D calls H(D,D) that calls D(D) in simulation mode
  • e: line 04: D(D) is called (in simulation mode)
  • f: line 05: D enters its code (in simulation mode)
  • g: line 06: D calls H(D,D) (in simulation mode) that calls D(D) in simulation mode
  • h: line 04: D(D) is called (in simulation mode)
  • i: line 06: The simulator returns false (because it has detected a cycle)
  • j: line 09: D returns false
  • k: line 14: D(D) has returned false (but D(D) has halted)
 
Upvote 1 Downvote
Play Snayk 3+, higher dimensional snake game?
cli345 said:
Good idea! It's transformed to:
  • a: line 12: main() calls D(D)
  • b: line 04: D(D) is called
  • c: line 05: D enters its code
  • d: line 06: D calls H(D,D) that calls D(D) in simulation mode
  • e: line 04: D(D) is called (in simulation mode)
  • f: line 05: D enters its code (in simulation mode)
  • g: line 06: D calls H(D,D) (in simulation mode) that calls D(D) in simulation mode
  • h: line 04: D(D) is called (in simulation mode)
  • i: line 06: The simulator returns false (because it has detected a cycle)
  • j: line 09: D returns false
  • k: line 14: D(D) has returned false (but D(D) has halted)
Click to expand...
So it seems like you agree that D correctly simulated by H never halts, thus when H is reporting on the behavior of its input then H is correct.
 
Upvote 0 Downvote
cli345 said:
I think you're right in a sense: H is correct on what D would be if H only simulate D.
Click to expand...
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. Decision problem - Wikipedia

The simulated input is before H has aborted its simulation of D and the directly executed input is after H has aborted its simulation of D, thus just like you are hungry before dinner you are no longer hungry after dinner. This makes the behavior of D entirely different between simulated: H(D,D) and directly executed: D(D).

So if it is construed as the job of H to report on the behavior specified by its inputs (In technical terms H computes the mapping from its input finite strings to an accept or reject state on the basis of the actual behavior specified by these inputs) then H is correct to report that its input does not halt even though the directly executed D(D) does halt?
 
Last edited:
Upvote 0 Downvote
Good idea(But we go a little away from the classical halting problem)! It might be assumed that H must report (possibly by aborting the simulation) on the behavior specified by its inputs and by the assumption that H never aborts a simulation.
 
Upvote 1 Downvote
cli345 said:
Good idea(But we go a little away from the classical halting problem)! It might be assumed that H must report (possibly by aborting the simulation) on the behavior specified by its inputs and by the assumption that H never aborts a simulation.
Click to expand...
I came up with the idea of a simulating halt decider more than six years ago. It seems that no one else has ever fully explored this idea. H must always abort the simulation of non-terminating inputs even as simple as a trivial infinite loop because a halt decider must always terminate.

The code above is executed in the x86utm operating system that I created for that purpose. Just today I figured out how to totally encode the Peter Linz proof and directly refute it. In this case Linz: H correctly determines the halt status of Linz: Ĥ. Unlike the above example Linz: H correctly reports on the behavior of the directly executed Linz: Ĥ. https://www.liarparadox.org/Linz_Proof.pdf
 
Upvote 0 Downvote
Hello polcott, interesting discussion.

Can you clarify something about the first post in the thread?

"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?"

D can not reach line 07.

D is coded like the halting problem, but even if it were coded like a Hello World program (after line 06), it still would not reach line 07.

H is causing the infinite loop, by using simulation. Is that valid?
 
Upvote 0 Downvote
Play Snayk 3+, higher dimensional snake game?
BlackCube said:
Hello polcott, interesting discussion.

Can you clarify something about the first post in the thread?

"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?"

D can not reach line 07.

D is coded like the halting problem, but even if it were coded like a Hello World program (after line 06), it still would not reach line 07.

H is causing the infinite loop, by using simulation. Is that valid?
Click to expand...

You are correct that D can never reach its own line 07.
H is a simulating (partial) halt decider (I came up with this idea 6 more than years ago) or in software engineering terms H is a termination analyzer. It is the pathological relationship that D defines relative to H that prevents D from terminating.
 
Upvote 0 Downvote
Consider program X.

X does not call H. X is an ordinary program with no cunning self reference.

Function H is given X's code and input data.

H simulates X, and by watching the registers and memory, H tries to detect an infinite loop. Is this the idea?

The memory is finite, the registers are finite, so the simulation has a finite number of states.

So there is no doubt that H could detect a loop. (in theory)

In practice, it would be very easy to write X such that H could not give an answer in a reasonable amount of time.
 
Upvote 0 Downvote
BlackCube said:
Consider program X.

X does not call H. X is an ordinary program with no cunning self reference.

Function H is given X's code and input data.

H simulates X, and by watching the registers and memory, H tries to detect an infinite loop. Is this the idea?

The memory is finite, the registers are finite, so the simulation has a finite number of states.

So there is no doubt that H could detect a loop. (in theory)

In practice, it would be very easy to write X such that H could not give an answer in a reasonable amount of time.
Click to expand...
I have simple programs that halt and simple examples of Infinite_Loop() and Infinite_Recursion() that H gets correctly. The key aspect of my work is that H can always recognize and reject every instance of the halting problem's pathological input. I don't think that anyone has ever done that before.
 
Upvote 0 Downvote
cli345 said:
Good idea(But we go a little away from the classical halting problem)! It might be assumed that H must report (possibly by aborting the simulation) on the behavior specified by its inputs and by the assumption that H never aborts a simulation.
Click to expand...
H(D,D) reports on the basis of whether or not it must abort the simulation of its input to prevent the infinite simulation of this input. In other words H reports on whether or not D correctly simulated by H terminates normally.

For all inputs besides pathological inputs the behavior of the correctly simulated input matches the behavior of the directly executed input. Because of this divergence many people have said that H(D,D) returns an incorrect value because D(D) halts. It has taken me two years to fully address this issue.

Because H(D,D) does separately match pathological inputs (recursive simulation) from other non terminating inputs such as (infinite loop) and (infinite recursion) the return value of 0 can be interpreted as meaning: (a) non halting or (b) pathological input. H1 is identical to H except D has not defined a pathological relationship to H1. H1(D,D) returns 1.

When we construe H as a Denial of Service Attack Detector then returning 0 for (a) non-halting (b) pathological input makes perfect sense. In this case the H is matching the semantic property of its input: BAD_INPUT that construes inputs trying to fool the detector as malevolent.
 
Last edited:
Upvote 0 Downvote
Play Snayk 3+, higher dimensional snake game?
cli345 said:
Good idea(But we go a little away from the classical halting problem)! It might be assumed that H must report (possibly by aborting the simulation) on the behavior specified by its inputs and by the assumption that H never aborts a simulation.
Click to expand...
When H has three return values:
0=Input has pathological relationship to H
1=Input halts
2=Input does not halt
Then H becomes a halting decidability decider
I have testing this in an adapted version of my code and it works consistently.
H recognizes every combination of simple pathological inputs.
 
Upvote 0 Downvote
cli345 said:
Good idea! It's transformed to:
  • a: line 12: main() calls D(D)
  • b: line 04: D(D) is called
  • c: line 05: D enters its code
  • d: line 06: D calls H(D,D) that calls D(D) in simulation mode
  • e: line 04: D(D) is called (in simulation mode)
  • f: line 05: D enters its code (in simulation mode)
  • g: line 06: D calls H(D,D) (in simulation mode) that calls D(D) in simulation mode
  • h: line 04: D(D) is called (in simulation mode)
  • i: line 06: The simulator returns false (because it has detected a cycle)
  • j: line 09: D returns false
  • k: line 14: D(D) has returned false (but D(D) has halted)
Click to expand...

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

When it is understood that D correctly simulated by H
(a) Is the behavior that H must report on and
(b) Cannot possibly terminate normally
then it is understood that D 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.
 
Upvote 0 Downvote
polcott said:
When H has three return values:
0=Input has pathological relationship to H
1=Input halts
2=Input does not halt
Then H becomes a halting decidability decider
I have testing this in an adapted version of my code and it works consistently.
H recognizes every combination of simple pathological inputs.
Click to expand...
I have reversed this position, H now only returns 1 and 0.
and works according to my prior comment.
 
Upvote 0 Downvote
BlackCube said:
Consider program X.

X does not call H. X is an ordinary program with no cunning self reference.

Function H is given X's code and input data.

H simulates X, and by watching the registers and memory, H tries to detect an infinite loop. Is this the idea?

The memory is finite, the registers are finite, so the simulation has a finite number of states.

So there is no doubt that H could detect a loop. (in theory)

In practice, it would be very easy to write X such that H could not give an answer in a reasonable amount of time.
Click to expand...
I am not solving the halting problem. I am refuting the conventional proof
having an input that does the opposite of whatever Boolean value that H returns.
H correctly reports that D correctly simulated by H cannot possibly terminate normally.
 
Upvote 0 Downvote

New Threads

Latest posts

Share this page

Buy us a coffee!

Buy me a coffee.
DataCamp Advertisement
Code Academy Advertisement

About Us

Code Forum is a community platform where coding enthusiasts can connect with other developers, engage in discussions, ask for help, and share their knowledge with a supportive community. It's a perfect place to improve your coding skills and to find a community of like-minded individuals who share your passion for coding.

Site links

Stay Connected

Back
Top Bottom