| olcott <NoOne@NoWhere.com>: Oct 23 06:31PM -0500 On 10/23/2020 6:17 PM, Mike Terry wrote: > Check out the "stack trace" (sort-of) of the two machines H and H_Hat > running. > Mike. The outermost H_Hat() has its process terminated before: if (Was_Its_Execution_Aborted(M, M)) returns a value to H_Hat(). This is because the DebugTrace() that H() invoked that created the process that H_Hat() resides in is a few steps ahead of what the inner DebugStep() invoked by H_Hat() can see. -- Copyright 2020 Pete Olcott |
| Mike Terry <news.dead.person.stones@darjeeling.plus.com>: Oct 24 12:38AM +0100 On 24/10/2020 00:06, olcott wrote: > The key difference is that if (Was_Its_Execution_Aborted(M, M)) > is true, then its execution has already been aborted so it never reaches > this if statement. No, that's obviously wrong as I explained. All that has been aborted is the /emulation/ of H_Hat that occurs within Was_Its_Execution_Aborted(M, M). Do you really not see the difference between H_Hat running at outer level, and some inner "emulation" of H_Hat that occurs within Was_Its_Execution_Aborted()? Was_Its_Execution_Aborted() can only "abort" the inner emulation [i.e. just decide to stop emulating at some point], not its own running instance! Are you trying to claim that the code for Was_Its_Execution_Aborted() contains a HALT instruction? That's not simply not allowed - Was_Its_Execution_Aborted() MUST actually report back its TERMINATED/ABORTED decision, because it's part of a Halt Decider and the only way a Halt Decider is allowed to terminate is in one of the two decider states. In our template it has been arranged (for good reason!) to occur /only/ in the two alternate HALT instructions in H(). The role of Was_Its_Execution_Aborted() is to enable H and H_Hat to make their correct choices. Mike. |
| olcott <NoOne@NoWhere.com>: Oct 23 06:46PM -0500 On 10/23/2020 6:38 PM, Mike Terry wrote: > Was_Its_Execution_Aborted()? Was_Its_Execution_Aborted() can only > "abort" the inner emulation [i.e. just decide to stop emulating at some > point], not its own running instance! I made a process map to verify this answer: The outermost H_Hat() has its process terminated before: if (Was_Its_Execution_Aborted(M, M)) returns a value to this outermost H_Hat(). This is because the DebugTrace() that H() invoked that created the process that H_Hat() resides in is a few steps ahead of what the inner DebugStep() invoked by H_Hat() can see. When the outermost DebugTrace() aborts the outermost H_Hat() the entire process tree created by this outermost H_hat() is terminated. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 23 06:54PM -0500 On 10/23/2020 6:39 PM, Malcolm McLean wrote: > You're going to have to clarify. > If H is called, DebugTrace emulates the outer instance of H_Hat, and can > abort the emulation without aborting itself. As soon as DebugTrace() returns a value all of its local stack memory is freed and the process that it created only existed in this local stack memory. > If H_Hat is called directly, and not through H, does the outer instance of > H_Hat abort, or does it terminate normally? Whether or not H() or H_Hat() is the outermost process that invokes the outermost DebugTrace() in either case this outermost DebugTrace() aborts the inner H_Hat() before the inner DebugTrace() returns a value to it. -- Copyright 2020 Pete Olcott |
| Mike Terry <news.dead.person.stones@darjeeling.plus.com>: Oct 24 01:06AM +0100 On 24/10/2020 00:31, olcott wrote: > This is because the DebugTrace() that H() invoked that created the > process that H_Hat() resides in is a few steps ahead of what the inner > DebugStep() invoked by H_Hat() can see. OK I can see you're not even going to read the rest of my post, so I'll cut and paste the stack traces of what the two machines H, H_Hat do when they run, adjusting a bit to remove my intermediate DeciderLogic() routine. At least if you disagree with something you can point out where we are diverging! The most relevent one for discussing what H_Hat does is the trace for H_Hat machine: H_Hat starts (main() calls H_Hat(H_Hat)) H_Hat calls Was_Its_Execution_Aborted(H_Hat,H_Hat) Was_Its_Execution_Aborted emulates H_Hat(H_Hat) Was_Its_Execution_Aborted decides the emulation is looping!!! Was_Its_Execution_Aborted stops emulating and returns ABORTED H_Hat does the opposite of HALT/NOT_HALT So... which of these lines are correct/incorrect? And for comparison here is what H does: H starts (main() calls H(H_Hat,H_Hat)) H calls Was_Its_Execution_Aborted(H_Hat,H_Hat) Was_Its_Execution_Aborted emulates H_Hat(H_Hat) Was_Its_Execution_Aborted decides the emulation is looping!!! Was_Its_Execution_Aborted stops emulating and returns ABORTED H_Hat halts indicating HALT/NOT_HALT decision based on rc.. ..from Was_Its_Execution_Aborted() While we're at it you might as well say which of these lines are correct/incorrect too. :) Regards, Mike. |
| olcott <NoOne@NoWhere.com>: Oct 23 07:13PM -0500 On 10/23/2020 6:58 PM, Malcolm McLean wrote: >> the inner H_Hat() before the inner DebugTrace() returns a value to it. > But the when H_Hat is called directly, the outermost H_Hat terminates normally? > Or is it aborted? The outermost H_Hat() terminates normally because the inner one was aborted. // M has address of H_Hat() void H_Hat(u32 M) { if (DebugTrace(M, M)) // M(M) Aborted? MOV_EAX_0 // Execution of M(N) has been aborted else { MOV_EAX_1 // M(N) has halted HERE: goto HERE; } HALT } -- Copyright 2020 Pete Olcott |
| Mike Terry <news.dead.person.stones@darjeeling.plus.com>: Oct 24 01:21AM +0100 On 24/10/2020 00:54, olcott wrote: > Whether or not H() or H_Hat() is the outermost process that invokes the > outermost DebugTrace() in either case this outermost DebugTrace() aborts > the inner H_Hat() before the inner DebugTrace() returns a value to it. Malcolm didn't ask what happens to the /inner/ (emulated) H_Hat. That obviously goes away. He asks what happens to the /outer/ H_Hat that first called DebugTrace(). Mike. |
| olcott <NoOne@NoWhere.com>: Oct 23 07:39PM -0500 On 10/23/2020 7:06 PM, Mike Terry wrote: > OK I can see you're not even going to read the rest of my post, so I'll > cut and paste the stack traces of what the two machines H, H_Hat do when > they run, First of all all of these ideas equally apply to a UTM that executes another UTM in one state transition at-a-time mode, that executes other UTM's in an execution hierarchy. The material is presented in C because presenting it using an adaptation of an existing Turing Machine Description language would be tedious beyond belief. http://www.lns.mit.edu/~dsw/turing/turing.html Who want to mow five acres of grass using only finger nail clippers? main() H() and the first DebugTrace() run in a process with its own stack. The first H_Hat() runs in a separate process with its own separate stack space. It invokes another different DebugTrace() that runs in its process with a separate stack space. This second DebugTrace() created another separate process with its own separate stack space and executes a second instance of H_Hat(). Bottom line here is that when the outermost DebugTrace() terminates the outermost H_Hat() there is no stack unwinding that allows this outermost H_hat() to receive any return value from DebugTrace(). It is like the outermost H_Hat() executed exit(0); > correct/incorrect too. :) > Regards, > Mike. You got the above wrong because you did not even bother to get the execution order correctly: main() calls H() which calls DebugTrace() which creates a whole new process and invokes H_Hat() in this process -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 23 07:52PM -0500 On 10/23/2020 7:24 PM, Malcolm McLean wrote: > OK, that's crucial. If H_Hat terminates normally when invoked directly, then > H() has to return "Not aborted". But that's impossible. There's an infinite > recursion of DebugTraces. The key thing that everyone has disavowed that really does make a huge difference is the placement order in the process tree. The difference now is that I have a whole operating system to back me up. > Linz hasn;t been refuted. Or you can make a tiny change to H_Hat so that > it is no longer a Turing machine. Then H() and H_Hat() will give consistent > results. Not, not at all, not in the least little bit. My whole x86utm operating system was designed to model UTM's executing other UTM's. The outermost DebugTrace() can see the infinite recursion of H_Hat() sooner that the next inner DebugTrace() can see this because it has already seen more execution steps / state transitions. The outer DebugTrace() has identical code to the Inner DebugTrace() but because it has more data the decision that it makes with this additional data is not the same decision that its inner process would make with less data. -- Copyright 2020 Pete Olcott |
| Richard Damon <Richard@Damon-Family.org>: Oct 23 09:35PM -0400 On 10/23/20 5:58 PM, olcott wrote: > DebugTrace() stops running the outermost H_Hat() in the outermost > DebugTrace() DebugStep() loop. Then the outermost DebugTrace() returns > Aborted_Because_Non_Halting_Behavior_Detected. Graphic picture: First Run: Run H(H_Hat) H call DebugTrace on H_Hat(), which (apparently) detects that it needed to abort H_Hat, so H returns the result, H_Hat does not halt. Next Run H_Hat H_Hat calls the same DebugTrace on H_Hat(), which by necessity, must return the same answer, that it needed to abort H_Hat, So H_Hat halt, Thus showing H, and thus DebugTrace to be wrong. There IS not 'supervisor' above this outer invocation of H_Hat, so nothing will 'abort' it. Now, if instead DebugTrace decided that H_Hat did stop, the the first run, of H() will indicate that H_Hat stops, but on the second run, H_Hat() becomes just an ordinary infinate loop that will never stop, so H() is again proven wrong. |
| olcott <NoOne@NoWhere.com>: Oct 23 08:36PM -0500 On 10/23/2020 8:22 PM, Richard Damon wrote: > Your returning that you aborted H_Hat, is an indication that you > detected that H_Hat(H_Hat) is a forever looping machine/input, but then > the calling H_Hat halts, so your machine gave the wrong answer. Superficially within the indoctrination of the conventional halting problem proofs it would seem that way. H_Hat() decides that that its input would not halt so it aborts its input forcing it to halt. It says it won't halt and then it halts. When the halting problem question is: Do you have to abort your input to force it to halt? H_hat() aborts its input and says YES. Contradiction has been removed ! -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 23 08:45PM -0500 On 10/23/2020 8:35 PM, Richard Damon wrote: > Run H(H_Hat) > H call DebugTrace on H_Hat(), which (apparently) detects that it needed > to abort H_Hat, so H returns the result, H_Hat does not halt. Not quite. H() calls DebugTrace() which executes H_Hat() until it detects infinite recursion. Then DebugTrace() terminates H_Hat() and notifies H() that H_Hat() was terminated. > H_Hat calls the same DebugTrace on H_Hat(), which by necessity, must > return the same answer, that it needed to abort H_Hat, > So H_Hat halt, Thus showing H, and thus DebugTrace to be wrong. Not quite. H_Hat() calls DebugTrace() which executes another separate instance of H_Hat() until it detects infinite recursion on this inner instance. Then DebugTrace() terminates H_Hat() and notifies the outer H_Hat() that the inner H_Hat() was terminated. > There IS not 'supervisor' above this outer invocation of H_Hat, so > nothing will 'abort' it. No need to abort it. It takes the M(M) was aborted path. // M has address of H_Hat() void H_Hat(u32 M) { if (DebugTrace(M, M)) // M(M) Aborted? MOV_EAX_0 // Execution of M(N) has been aborted else { MOV_EAX_1 // M(N) has halted HERE: goto HERE; } HALT } > run, of H() will indicate that H_Hat stops, but on the second run, > H_Hat() becomes just an ordinary infinate loop that will never stop, so > H() is again proven wrong. The second run also gets the correct answer. -- Copyright 2020 Pete Olcott |
| Richard Damon <Richard@Damon-Family.org>: Oct 23 10:22PM -0400 On 10/23/20 12:28 AM, olcott wrote: >> theory, where it seems that, at least for sufficient expressive system, >> that there are some properties that we can not proof whether they are >> true or not. I run your Turing machine equivalent, and provide it the program H_Hat(H_Hat). Per Litz, the first step of this operation is to duplicate its input, and then go into the modified H (modified only in what it does in its final states). You have describe these steps as 'calling Debug Step' This executes the sequences describe by H(H_Hat, H_Hat) and eventually it needs to return a result. This result is then used by H_Hat to decide what it will do. A couple of points: THIS invocation of H_Hat is not 'under' any supervisor, so nothing can abort it, (If something does, then you simulator is not an accurate model of a Turing Machine). DebugStep, given the same input must return the same answer, or it is faulty. In practice, since for this proof, we only ever give it one input. DebugStep MUST give an answer in finite time (this doesn't seem to be an issue with your presentation) Presuming that H is supposed to be a proper Halt Decider, the answer return by Debug Step MUST be an accurate, and reflect what this run of H_Hat will eventually do. For H_Hat to represent the H_Hat in Litz, it WILL go into an infinite loop if H would have indicated that it halted, and will Halt, if H would have indicated that it was non-Halting. It isn't the input program to H that misbehaves, it is the outermost caller of H that misbehaves, BUT, since we also provided it as the input to H, the embedded version of the program needs to behave exactly the same as the outer version of the program, at least until H decides it knows the answer, then it can stop the inner version, but NOT the outer version. You keep on talking about the run of H(H_Hat, H_Hat), but don't look at H_Hat(H_Hat). THAT is where the real rubber hits the road. We do need to compare its behavior to what H says, but since the execution of H_Hat includes as a sub-sequence, the execution of H, we can tell from that run what a run of H(H_Hat, H_Hat) would have said. |
| olcott <NoOne@NoWhere.com>: Oct 23 09:51PM -0500 On 10/23/2020 9:22 PM, Richard Damon wrote: > abort it, (If something does, then you simulator is not an accurate > model of a Turing Machine). > DebugStep, given the same input must return the same answer, It is DebugTrace() not DebugStep() that makes the halting decision. It turns out that the input given to the outer DebugTrace() is more extensive than the input provided to the inner DebugTrace() because the outer DebugTrace() is a few instructions ahead of the inner DebugTrace(). So when the outer DebugTrace() terminates its invocation of H_Hat() the H_Hat() invocation of DebugTrace() never gets a return value from DebugTrace(). > For H_Hat to represent the H_Hat in Litz, it WILL go into an infinite > loop if H would have indicated that it halted, and will Halt, if H would > have indicated that it was non-Halting. Yes that it why I had to redefine the notion of a halt decider so that the halting problem is no lonegr undecidable. The halt decider no longer decides if its input will halt. Instead it executes its input until it detects non-halting behavior and then the first step is to terminate the input and the next step is to indicate that it has already terminated it input. The halting problem proof trick has been neutered. > same as the outer version of the program, at least until H decides it > knows the answer, then it can stop the inner version, but NOT the outer > version. No this is not true. The outer version of the program has more data than the inner version of the program. > compare its behavior to what H says, but since the execution of H_Hat > includes as a sub-sequence, the execution of H, we can tell from that > run what a run of H(H_Hat, H_Hat) would have said. DebugTrace(H_Hat, H_Hat) makes set same decision whether called from H(H_Hat, H_Hat) and H_Hat(H_Hat) because its input is identical. -- Copyright 2020 Pete Olcott |
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Oct 23 07:54PM -0700 On 10/23/2020 6:45 PM, olcott wrote: > Not quite. H_Hat() calls DebugTrace() which executes another separate > instance of H_Hat() until it detects infinite recursion on this inner > instance. [...] Infinite recursion? Are you looking at exhausting the stack on your end? Say the arbitrary function uses some recursion now and then, and never gets close to blowing the stack, yet runs forever. On some inputs, it might run for say, 10,000 years, then self terminate. On others it runs forever. Say it takes no input, and it is as it is. Say, a system booting up in default mode. It runs a server that runs forever, unless its hardware is destroyed. |
| olcott <NoOne@NoWhere.com>: Oct 23 09:55PM -0500 On 10/23/2020 9:32 PM, Richard Damon wrote: >> infinite recursion before it ever gets there. > And H_Hat as defined can't do that if H fulfills its requirements, to be > a universal decider that ALWAYS, for ALL inputs, in FINITE time. The scope of my investigation has always been limited to refuting the conventional self-referential halting problem proofs by showing how their counter-examples can be correctly decided. If my scope was to solve the halting problem I would have to be all knowing and create an omniscient computer program. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 23 10:18PM -0500 On 10/23/2020 9:50 PM, Richard Damon wrote: > The Halting problem is: "Will the given machine, with the given input > halt in finite time, or will it run forever?". (And the answer needs to > be provided in a finite time), I spent 12,000 hours on this since 2004. I just finished one man-year worth of work creating the x86utm operating system for the sole purpose of providing a fully executable UTM equivalent von Neumann architecture machine virtual machine. I found that one key element of the undeciability of the halting problem is how the halting decider was defined. bool Does_It_Halt(u32 P, u32 I) is subject to pathological self-reference(Olcott 2004) and makes the halting problem undecidable. bool Was_Input_Aborted(u32 P, u32 I) is NOT subject to pathological self-reference(Olcott 2004) and makes the halting problem decidable. It answers the exact same question as the original question except that this time it does it in a way that it cannot be fooled. > around the original argument by changing the question does NOT > invalidate that the original argument was still valid for the original > question. No. Not at all. Not in the least little bit. The original proofs asserted that they proved that the halting problem was undecidable. They did not really prove that the halting problem is undecidable at all they merely found one way that doesn't work. > machines/input that need to be processed, or the question being asked, > may well allow a limited halt decider to be created. That is not new. > The proof is SPECIFICALLY about a universal halt decider. With my change to the definition of the halt decider the conventional counter-examples that were presented as proof that halting is undecidable have now been made decidable. I am working on writing the x86utm code to directly show the steps involved for DebugTrace() to decide that H_Hat() is infinitly recursive. Now that I have already provided 99.99% of the solution most any competent programmer could complete these steps. // M has address of H_Hat() void H_Hat(u32 M) { if (DebugTrace(M, M)) // M(M) Aborted? MOV_EAX_0 // Execution of M(N) has been aborted else { MOV_EAX_1 // M(N) has halted HERE: goto HERE; } HALT } // M and N have the address of H_Hat() void H(u32 M, u32 N) { if (DebugTrace(M, N)) // M(N) Aborted? MOV_EAX_0 // Execution of M(N) has been aborted else MOV_EAX_1 // M(N) has halted HALT } int main() { u32 M = (u32)H_Hat; H(M, M); HALT; } In the above case DebugTrace() detects that H_Hat() is infinitely recursive and aborts the outermost instance of H_Hat() and its whole process tree so that the inner DebugTrace() that is invoked by H_Hat() never returns a value to H_Hat(). This makes the standard halting problem trick impossible. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 23 10:22PM -0500 On 10/23/2020 9:54 PM, Chris M. Thomasson wrote: >> instance. > [...] > Infinite recursion? Are you looking at exhausting the stack on your end? Infinite recursion on an actual UTM would never exhaust the stack. The key thing that no one ever noticed for 80 years is that none of the conventional self-referential halting problem proof counter-examples ever reach their undecidable state transitions. -- Copyright 2020 Pete Olcott |
| Mike Terry <news.dead.person.stones@darjeeling.plus.com>: Oct 24 04:27AM +0100 On 24/10/2020 01:39, olcott wrote: > outermost H_Hat() there is no stack unwinding that allows this outermost > H_hat() to receive any return value from DebugTrace(). > It is like the outermost H_Hat() executed exit(0); What you are describing is what I have called the H run, or "what H does" below. (The second of the traces.) The first of the traces is for the "H_Hat machine", i.e. H_Hat is called directly from main(). I totally get that when DebugTrace() emulates the running of H_Hat, it will emulate a new "process" for that run of H_Hat. > execution order correctly: > main() calls H() which calls DebugTrace() which creates a whole new > process and invokes H_Hat() in this process Yeah, you're describing the second "what H does" trace. You're not even bothering to make an effort to properly examine what I wrote, so I don't see why I should be motivated to spend my time on any of this, but I'll have one more go at explaining what should have been perfectly obvious to you: You said: main() calls H() ... and I said: H starts (main() calls H(H_Hat,H_Hat)) Do you see how I /am/ in fact "getting the order right" so far? Then you continued: ... which calls DebugTrace() ... and my next line was: H calls Was_Its_Execution_Aborted(H_Hat,H_Hat) ok, you say DebugTrace, I say Was_Its_Execution_Aborted() which is THE SAME THING. It was *YOU* who suggested we should rename DebugTrace to Was_Its_Execution_Aborted() upthread somewhere, as part of "changing the question". I thought it was all a bit dumb, but went along with it for you. Do you want me to post my traces again, but saying DebugTrace instead of Was_Its_Execution_Aborted()? My point would be that YOU SHOULD RECOGNISE THIS EQUIVALENCE WITHOUT ME NEEDING TO EXPLAIN IT TO YOU, AS YOU INVENTED THE DIFFERENT NAMES. Assuming you can translate your own name change, do you see that I am /still/ getting the order right so far? Then you continued: ... which creates a whole new process and invokes H_Hat() in this process ... and my next line was: Was_Its_Execution_Aborted emulates H_Hat(H_Hat) Well common sense should tell you this is saying the same as you. Emulating H_Hat(H_Hat) in your UTM architecture involves creating a new "virtual process" (or maybe a real OS one, it doesn't matter) and running H_Hat in that process. In fact emulating in any architecture would be the same (new virtual process and so on.) Do you see that I am /still/ getting the order right so far? Um, that's everything you picked up on, and I /in fact/ got every one of those in the right order! Note: 1) I only trace what happens in the "native" machine level. I know full well that the emulated H_Hat() in it's virtual process will do stuff that could be traced, but I am simply not concerned with that level of trace. Pretend that I have set TRACELEVEL = OUTER, LOL. With that in mind you might go back to my SECOND trace and see if it matches your understanding, and if not where it diverges. (With the understanding that my Was_Its_Execution_Aborted() is the same as your DebugTrace(), etc.) 2) As well as the second trace for H running natively, I also provided the first trace, which in similar fashion shows H_Hat running "natively". You could take a look at that one and comment too. And IF your position is that H_Hat never is run natively, you should say that rather than claiming my order is wrong because you are too lazy to look at the right trace. Or if you just want me to go away, post another bunch of crap without bothering to actually try to achieve any mutual understanding - that's OK too. Regards, Mike. |
| olcott <NoOne@NoWhere.com>: Oct 23 10:28PM -0500 On 10/23/2020 9:58 PM, Richard Damon wrote: > that the H() run will indicate that the provide program is non-halting, > BUT in the second run, since DebugTrace indicates that it had to abort > H_Hat(H_Hat), H_Hat will immediate halt. That is why we have to change the question. If the halt decider executes its input in DebugStep() mode, aborts the execution of this input, and reports not halting, then is gets the wrong answer because it decided not halting and it halted. With exact same situation except that the halt decider reports: Aborted_Because_Non_Halting_Behavior_Detected. Now it correctly decided halting AND got the correct answer. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 23 10:40PM -0500 On 10/23/2020 10:27 PM, Mike Terry wrote: > directly from main(). > I totally get that when DebugTrace() emulates the running of H_Hat, it > will emulate a new "process" for that run of H_Hat. When H_Hat(H_Hat) or H(H_Hat, H_Hat) is invoked they both invoke DebugTrace(H_Hat, H_Hat) which returns the same value because it has the same input. > and I said: > H starts (main() calls H(H_Hat,H_Hat)) > Do you see how I /am/ in fact "getting the order right" so far? Yes. I was mistaken about this earlier. > ... which calls DebugTrace() ... > and my next line was: > H calls Was_Its_Execution_Aborted(H_Hat,H_Hat) Yes. > instead of Was_Its_Execution_Aborted()? My point would be that YOU > SHOULD RECOGNISE THIS EQUIVALENCE WITHOUT ME NEEDING TO EXPLAIN IT TO > YOU, AS YOU INVENTED THE DIFFERENT NAMES. Yes agreed. > Assuming you can translate your own name change, do you see that I am > /still/ getting the order right so far? Yes. > Then you continued: > ... which creates a whole new process and invokes H_Hat() in this > process ... Yes. > and my next line was: > Was_Its_Execution_Aborted emulates H_Hat(H_Hat) No. It always takes two params. > "virtual process" (or maybe a real OS one, it doesn't matter) and > running H_Hat in that process. In fact emulating in any architecture > would be the same (new virtual process and so on.) Yes > Do you see that I am /still/ getting the order right so far? Yes. You have always been one of my best reviewers. > Um, that's everything you picked up on, and I /in fact/ got every one of > those in the right order! Yes except the two versus one param thing. > matches your understanding, and if not where it diverges. (With the > understanding that my Was_Its_Execution_Aborted() is the same as your > DebugTrace(), etc.) Two params versus one and CRUCIALLY the second invocation of Was_Its_Execution_Aborted() is terminated before it ever gets any chance to return a value. As soon as the invocation of H_Hat() by the outermost Was_Its_Execution_Aborted() is terminated the whole process tree is terminated. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 23 11:02PM -0500 On 10/23/2020 7:06 PM, Mike Terry wrote: > H_Hat calls Was_Its_Execution_Aborted(H_Hat,H_Hat) > Was_Its_Execution_Aborted emulates H_Hat(H_Hat) > Was_Its_Execution_Aborted decides the emulation is looping!!! Infinitely recursive. > Was_Its_Execution_Aborted stops emulating and returns ABORTED > H_Hat does the opposite of HALT/NOT_HALT No this step is incorrect as you can see by the following code. In this case ABORTED = true causing the outermost H_Hat() to halt. // M has address of H_Hat() void H_Hat(u32 M) { if (DebugTrace(M, M)) // M(M) Aborted? MOV_EAX_0 // Execution of M(N) has been aborted else { MOV_EAX_1 // M(N) has halted HERE: goto HERE; } HALT } It seems really really weird that H_Hat() decides that its input of H_Hat() will not halt and then it goes ahead and halts itself. The reason for this is that the outermost halt decider has more information than the inner halt decider (more traced steps) so we are not getting two different results from the same function for the same input. The inputs are different. Also the key discovery that I made in 2016 is the all of the conventional self-referential halting problem proof counter-examples are infinitely recursive so that none of them ever reach the undecidable state transitions. This key insight necessitates that any halt decider based on a DebugStep() of its input must terminate this input or get stuck in infinite execution. Although it may be possible for it to wait a fixed number of steps to see what its input does before terminating its input it cannot simply wait to see what its input would do. This results in infinite execution. it is best that it terminates its input as soon as it definitely decides that its input must be terminated. This keeps things simple. > H calls Was_Its_Execution_Aborted(H_Hat,H_Hat) > Was_Its_Execution_Aborted emulates H_Hat(H_Hat) > Was_Its_Execution_Aborted decides the emulation is looping!!! Infinitely recursive > correct/incorrect too. :) > Regards, > Mike. These look like they are correct. -- Copyright 2020 Pete Olcott |
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Oct 23 09:03PM -0700 On 10/23/2020 8:28 PM, olcott wrote: > With exact same situation except that the halt decider reports: > Aborted_Because_Non_Halting_Behavior_Detected. > Now it correctly decided halting AND got the correct answer. And how EXACTLY do you get to the Aborted_Because_Non_Halting_Behavior_Detected state? And is it guaranteed to be 100% correct? Scary Sarcasm: I can see it now... There are two possible scenarios. Person A is on a ventilator for 3 months... Your program halts the machine, A dies. Yikes! Now, get this... The same Person A is on a ventilator for 4 months... And recovers to a point where A can breath on its own! Therefore, your crap would have killed A prematurely at 3 months because it incorrectly detected non halting behavior! DAMN! |
| olcott <NoOne@NoWhere.com>: Oct 23 11:13PM -0500 On 10/23/2020 11:03 PM, Chris M. Thomasson wrote: > And how EXACTLY do you get to the > Aborted_Because_Non_Halting_Behavior_Detected > state? And is it guaranteed to be 100% correct? The whole scope of my work is to show that the conventional self-referential halting problem proof counter-examples do not prove that halting is undecidiable. I have already done that. The greatest scope of this whole project involves one more step to show the precise C code steps of actually correctly deciding one of the conventional self-referential halting problem proof counter-examples. I wrote this code in 2018-12-13 and I think that I may use this same simplest possible method. I have much more robust methods too. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 24 01:03AM -0500 On 10/23/2020 5:51 PM, Mike Terry wrote: > rather than Was_Its_Execution_Aborted() which we were discussing. I'll > just take it they're the same thing, and continue saying > Was_Its_Execution_Aborted().] OK good. I like that. Make the function say what it really means. That is good software engineering. > BUT bear in mind that H (as opposed to Was_Its_Execution_Aborted()) > plays the role in all this of a Linz *Halt Decider*, and so is > required to deliver its HD decision *HALT* or *NOT_HALT*. No, not at all. Not in the least little bit. This takes my solution of removing the pathological self-reference from the halting decision and tosses this solution in the trash. If Was_Its_Execution_Aborted() means H_Hat() [did not halt], then when it is aborted and it halts we have the wrong answer. It must mean: Aborted_Because_Non_Halting_Behavior_Detected. This is the exact same cases, except now we have the right answer. > any decision on whether some internal routine made some particular > decision and ceased emulating something or other - all that is beside > the point from the Linz proof perspective.) No. Not at all. Not in the least little bit. To remove the pathological self-reference and make the halting problem decidable we must ask a question that cannot be thwarted. > H_Hat, to convert that return code into its final HALT/NOT_HALT > decision. (Regardless of your new question, H must still deliver the > Halting Decider required output.) No. Not at all. Not in the least little bit. Aborted_Because_Non_Halting_Behavior_Detected means that the input would not halt yet it says it in such a way that it cannot be contradicted. > Originally the reason for extracting the Halt Decider logic into > a separate routine outside of H() was that exactly the same > logic needed to be employed in both H() and H_Hat(). bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) is the same function invoked by both H() and H_Hat(). This function cannot be contradicted. > The role of H in the Linz proof is to make the > Halt Decider decision of either HALT or NOT_HALT, and so if we extract Yet we must be careful to frame the question so that it cannot be contradicted. > return anything other than HALT/NOT_HALT. Given that your > Was_Its_Execution_Aborted() does not return HALT/NOT_HALT then the > thing to do is call it from within the halt decider logic routine. No, not at all. Not in the least. As soon as we redefine the halt decider so that its return value cannot possisbly be contradicted then the halting problem ceases to be undecidable. Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) == true means that the input has infinite execution. Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) == false means that the input DOES NOT HAVE infinite execution. -- Copyright 2020 Pete Olcott |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment