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) Here is an example of work in this same field: (shows termination analysis is an active field) Termination Analysis of C Programs Using Compiler Intermediate Languages Two people with masters degrees in computer science have agreed that D correctly simulated by H would never terminate normally. Anyone with a bachelors degree in computer science can easily verify that this is correct. MIT Professor Michael Sipser1 agreed that the following verbatim paragraph is correct: (he gave me permission to quote him on this) 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. 1 author of the best selling book on the theory of computation Introduction to the Theory of Computation 3rd Edition
-
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) Here is an example of work in this same field: (shows termination analysis is an active field) Termination Analysis of C Programs Using Compiler Intermediate Languages Two people with masters degrees in computer science have agreed that D correctly simulated by H would never terminate normally. Anyone with a bachelors degree in computer science can easily verify that this is correct. MIT Professor Michael Sipser1 agreed that the following verbatim paragraph is correct: (he gave me permission to quote him on this) 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. 1 author of the best selling book on the theory of computation Introduction to the Theory of Computation 3rd Edition
-
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) Here is an example of work in this same field: (shows termination analysis is an active field) Termination Analysis of C Programs Using Compiler Intermediate Languages Two people with masters degrees in computer science have agreed that D correctly simulated by H would never terminate normally. Anyone with a bachelors degree in computer science can easily verify that this is correct. MIT Professor Michael Sipser1 agreed that the following verbatim paragraph is correct: (he gave me permission to quote him on this) 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. 1 author of the best selling book on the theory of computation Introduction to the Theory of Computation 3rd Edition
-
It doesn't matter. There is no consequential difference here between simulating the code in an emulator or running it directly, except perhaps by making it less obvious what's going to happen so you can fool yourself for longer.
-
So you can't tell whether or not D correctly simulated by H will ever terminate normally for the above code under the stated assumptions?
Are you trying to trick me into doing your homework? E: oh I see now, it's worse than that. You already wrote papers about this.. Apparently you're some sort of crank scientist then. You cannot disprove the undecidability of the halting problem, *especially* not with simple things like "just emulate the code LMAO". The interesting part about the famous undecidability proof is that it doesn't matter how H works, if you take that away you just get something that doesn't work for mundane reasons.
-
Are you trying to trick me into doing your homework? E: oh I see now, it's worse than that. You already wrote papers about this.. Apparently you're some sort of crank scientist then. You cannot disprove the undecidability of the halting problem, *especially* not with simple things like "just emulate the code LMAO". The interesting part about the famous undecidability proof is that it doesn't matter how H works, if you take that away you just get something that doesn't work for mundane reasons.
-
Are you trying to trick me into doing your homework? E: oh I see now, it's worse than that. You already wrote papers about this.. Apparently you're some sort of crank scientist then. You cannot disprove the undecidability of the halting problem, *especially* not with simple things like "just emulate the code LMAO". The interesting part about the famous undecidability proof is that it doesn't matter how H works, if you take that away you just get something that doesn't work for mundane reasons.
-
Are you trying to trick me into doing your homework? E: oh I see now, it's worse than that. You already wrote papers about this.. Apparently you're some sort of crank scientist then. You cannot disprove the undecidability of the halting problem, *especially* not with simple things like "just emulate the code LMAO". The interesting part about the famous undecidability proof is that it doesn't matter how H works, if you take that away you just get something that doesn't work for mundane reasons.
So you can see that D does not terminate normally. fully operational sample code
-
Are you trying to trick me into doing your homework? E: oh I see now, it's worse than that. You already wrote papers about this.. Apparently you're some sort of crank scientist then. You cannot disprove the undecidability of the halting problem, *especially* not with simple things like "just emulate the code LMAO". The interesting part about the famous undecidability proof is that it doesn't matter how H works, if you take that away you just get something that doesn't work for mundane reasons.
This is a tautology: When 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 is necessarily correct to abort its simulation and reject this input as non-halting.
-
Are you trying to trick me into doing your homework? E: oh I see now, it's worse than that. You already wrote papers about this.. Apparently you're some sort of crank scientist then. You cannot disprove the undecidability of the halting problem, *especially* not with simple things like "just emulate the code LMAO". The interesting part about the famous undecidability proof is that it doesn't matter how H works, if you take that away you just get something that doesn't work for mundane reasons.
Any competent software engineer should be able to tell that D correctly simulated by H cannot possibly terminate normally because D remains stuck in recursive simulation. If these software engineers can see this then it is plausible that H can see this too. The full source-code for H is provided in a link above. In this source-code we can see that H simply recognizes a non-halting behavior pattern having the same form as infinite recursion. These same ideas are applied to the Peter Linz Turing Machine based Halting Problem proof with the same effect. When the conventional halting problem counter-example is presented to a simulating (partial) halt decider this correctly simulated input cannot possibly terminate normally and reach its own final state (the definition of halting) It remains stuck in recursive simulation.
-
Are you trying to trick me into doing your homework? E: oh I see now, it's worse than that. You already wrote papers about this.. Apparently you're some sort of crank scientist then. You cannot disprove the undecidability of the halting problem, *especially* not with simple things like "just emulate the code LMAO". The interesting part about the famous undecidability proof is that it doesn't matter how H works, if you take that away you just get something that doesn't work for mundane reasons.
-
Any competent software engineer should be able to tell that D correctly simulated by H cannot possibly terminate normally because D remains stuck in recursive simulation. If these software engineers can see this then it is plausible that H can see this too. The full source-code for H is provided in a link above. In this source-code we can see that H simply recognizes a non-halting behavior pattern having the same form as infinite recursion. These same ideas are applied to the Peter Linz Turing Machine based Halting Problem proof with the same effect. When the conventional halting problem counter-example is presented to a simulating (partial) halt decider this correctly simulated input cannot possibly terminate normally and reach its own final state (the definition of halting) It remains stuck in recursive simulation.
polcott wrote:
Any competent software engineer...
Any competent civil engineer can design a bridge that doesn't fall down. Yet they do. You said in the OP "Will D ever reach its own.." Ever means just that. In no situation in no time period. Any competent engineer (of any discipline) understands that there is a big difference between one single case and all cases for all time. The problem that you are looking at has been proven to be impossible. Any compentent engineer then understands that they must then do the following to achieve what you want. 1. Invalidate the original proof 2. Provide a new proof that it can fail. This by itself might provide the first. That is mathematics and not software.
-
harold aptroot wrote:
You already wrote papers about this..
Ah...well then that makes some of the rest more clear then.
I also posted a link to the fully operational code. I had to create the x86utm operating system based on an excellent x86 emulator. This system allows one C function to monitor the behavior of another C function in debug step mode. It is an easily verified fact that H does correctly determine that D correctly simulated by H would never terminate normally by reaching its own "return instruction" final state. D remains stuck in recursive simulation until H aborts its simulation of D. Many people have thought that this is an artifact of using C instead of Turing machines. This is refuted by the application of the same notion of a simulating (partial) halt decider to the Peter Linz Turing machine based Halting Problem proof.
-
polcott wrote:
Any competent software engineer...
Any competent civil engineer can design a bridge that doesn't fall down. Yet they do. You said in the OP "Will D ever reach its own.." Ever means just that. In no situation in no time period. Any competent engineer (of any discipline) understands that there is a big difference between one single case and all cases for all time. The problem that you are looking at has been proven to be impossible. Any compentent engineer then understands that they must then do the following to achieve what you want. 1. Invalidate the original proof 2. Provide a new proof that it can fail. This by itself might provide the first. That is mathematics and not software.
When you actually objectively review my work you will see that H does correctly determine that D correctly simulated by H will never reach its own "return instruction" and halt. Also this is a tautology (thus impossibly false): When 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 is necessarily correct to abort its simulation and reject this input as non-halting.
-
Are you trying to trick me into doing your homework? E: oh I see now, it's worse than that. You already wrote papers about this.. Apparently you're some sort of crank scientist then. You cannot disprove the undecidability of the halting problem, *especially* not with simple things like "just emulate the code LMAO". The interesting part about the famous undecidability proof is that it doesn't matter how H works, if you take that away you just get something that doesn't work for mundane reasons.
One can easily verify that D correctly simulated by H would never terminate normally because D would remain stuck in recursive simulation. Because recursive simulation demonstrates the same dynamic behavior pattern as infinite recursion it can also be understood that this behavior pattern can be recognized by an algorithm. From this we can see that from a software engineering perspective (at least) that H can correctly report that its simulated input would never terminate normally. Whether or not these insights apply to the actual halting problem is a next level review that must be done by a qualified computer scientist. The key issue here is Turing computability.
-
One can easily verify that D correctly simulated by H would never terminate normally because D would remain stuck in recursive simulation. Because recursive simulation demonstrates the same dynamic behavior pattern as infinite recursion it can also be understood that this behavior pattern can be recognized by an algorithm. From this we can see that from a software engineering perspective (at least) that H can correctly report that its simulated input would never terminate normally. Whether or not these insights apply to the actual halting problem is a next level review that must be done by a qualified computer scientist. The key issue here is Turing computability.
polcott wrote:
Whether or not these insights apply to the actual halting problem is a next level review that must be done by a qualified computer scientist.
The code you have provided is a demonstration of something that has already been demonstrated mathematically. Doesn't matter how you phrase your posts that remains true. Lets say you create a interpreter which changes the context in which the problem runs. For example it halts every single time a specific instruction is called. Certainly provable that it halts then. But that is a different problem than the one you posted. So your choices are 1. Find your own problem and prove anything you want about it. You must fully define the problem space. 2. Find a way to invalidate the existing Turing proof using the context in which it was presented. You do not get to change that context - if you want to change the context then see item #1. Note that step #1 even being fully correct will say nothing about the Turing proof.
-
polcott wrote:
Whether or not these insights apply to the actual halting problem is a next level review that must be done by a qualified computer scientist.
The code you have provided is a demonstration of something that has already been demonstrated mathematically. Doesn't matter how you phrase your posts that remains true. Lets say you create a interpreter which changes the context in which the problem runs. For example it halts every single time a specific instruction is called. Certainly provable that it halts then. But that is a different problem than the one you posted. So your choices are 1. Find your own problem and prove anything you want about it. You must fully define the problem space. 2. Find a way to invalidate the existing Turing proof using the context in which it was presented. You do not get to change that context - if you want to change the context then see item #1. Note that step #1 even being fully correct will say nothing about the Turing proof.
Thanks for answering. It is an easily verified fact that the H/D pair is isomorphic to the Halting Problem's pathological input. 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. Wikipedia:Halting problem It is equally an easily verified fact that D correctly simulated by H cannot possibly terminate normally. (D remains stuck in recursive simulation) This would seem to indicate: (a) When H correctly determines the halt status of D this is not Turing computable. (still possibly useful for termination analysis) (b) The original halting problem proofs never considered a simulating halt decider as an option, thus have a key gap in their reasoning.
-
polcott wrote:
Any competent software engineer...
Any competent civil engineer can design a bridge that doesn't fall down. Yet they do. You said in the OP "Will D ever reach its own.." Ever means just that. In no situation in no time period. Any competent engineer (of any discipline) understands that there is a big difference between one single case and all cases for all time. The problem that you are looking at has been proven to be impossible. Any compentent engineer then understands that they must then do the following to achieve what you want. 1. Invalidate the original proof 2. Provide a new proof that it can fail. This by itself might provide the first. That is mathematics and not software.
When the original proof relies on a single counter-example template as its input to prove undecidability all that is needed to refute this proof is to show how to determine the halt status of this otherwise undecidable input. Anyone with a BSCS can easily verify the software engineering aspect of my work. D correctly simulated by H remains stuck in recursive simulation, thus cannot possibly terminate normally. Once this is understood and accepted then looking at my actual code for H shows that it does correctly recognize a non-halting behavior pattern having the same form as infinite recursion. Summing this all up although there is a universal consensus of subjective opinion that I am wrong the objectively verified facts conclusively prove that my software engineering is correct.