- The key aspects of x86utm are now finally complete [ HP proof refutation has been provided ] - 9 Updates
- The x86utm operating system shows how the halting problem can be made decidable - 2 Updates
- Making the Halting Problem Decidable [ Includes deciding the Peter Linz proof counter-example ] - 1 Update
| olcott <NoOne@NoWhere.com>: Oct 26 02:12PM -0500 On 10/26/2020 11:11 AM, Mike Terry wrote: > detects non-halting behaviour and returns ABORTS to H() and H_Hat(). Is > that my false assumption? > Mike. void H_Hat(u32 M) { if (Aborted_Because_Non_Halting_Behavior_Detected(M, M)) MOV_EAX_1 // Execution of M(M) has been aborted else { MOV_EAX_0 // M(M) has halted HERE: goto HERE; } HALT } void H(u32 M, u32 N) { if (Aborted_Because_Non_Halting_Behavior_Detected(M, M)) MOV_EAX_1 // Execution of M(N) has been aborted else MOV_EAX_0 // M(N) has halted HALT } int main() { u32 M = (u32)H_Hat; H(M, M); H_Hat(M); HALT } In each of the two cases above: Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) Does provide the correct decision for its input. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 26 02:46PM -0500 On 10/26/2020 2:28 PM, Alan Mackenzie wrote: > Why are you being so damned evasive and dishonest? My question was not > about comparing H_Hat with H. It was about comparing your A_B_N_H_B_D > with a putative halt decider. They both give the same results. void H_Hat(u32 M) { if (!Halts(M, M)) MOV_EAX_0 // Does not Halt else { MOV_EAX_1 // Halts HERE: goto HERE; } HALT } void H(u32 M, u32 N) { if (!Halts(M, M)) MOV_EAX_0 // Does not Halt else MOV_EAX_1 // Halts HALT } int main() { u32 M = (u32)H_Hat; H(M, M); HALT } OK then: Let me know which of (a) or (b) is correct and explain why it is correct: (a) H.MOV_EAX_0 // in Linz it is a transition to a final state of ((qn)) (b) H.MOV_EAX_1 // in Linz it is a transition to a final state of ((qy)) Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 26 02:53PM -0500 On 10/26/2020 2:38 PM, Mike Terry wrote: >> Does provide the correct decision for its input. > So what was my false assumption you were referring to? > Mike. This answer may be too difficult to understand without an actual execution trace of fully operational code. I have already explained it again and again and no one has understood. The key summation of all of these execution trace answers is that bool Aborted_Because_Non_Halting_Behavior_Detected(M, M) always decides its input correctly and cannot be shown otherwise. The prior reply to you is much much easier to understand and is a key test of your sincerity in forming mutual understanding. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 26 03:43PM -0500 On 10/26/2020 2:46 PM, olcott wrote: > (a) H.MOV_EAX_0 // in Linz it is a transition to a final state of ((qn)) > (b) H.MOV_EAX_1 // in Linz it is a transition to a final state of ((qy)) > Copyright 2020 Pete Olcott This answer may be too difficult to understand without an actual execution trace of fully operational code. I have already explained it again and again and no one has understood. The key summation of all of these execution trace answers is that bool Aborted_Because_Non_Halting_Behavior_Detected(M, M) always decides its input correctly and cannot be shown otherwise. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 26 04:01PM -0500 On 10/26/2020 3:50 PM, Malcolm McLean wrote: > else > printf("Not aborted\n"); > } You have only shown how to encode this function incorrectly: bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) You have not shown any input where the following design necessarily gets the wrong answer: The redefined halt decider UTM executes its subordinate UTM one state transition at a time until it detects non-halting behavior or its subordinate UTM has terminated normally. If the halt decider UTM detects non-halting behavior of its subordinate UTM it simply stops executing the subordinate and transitions to its own final state of ABORTED_NON_TERMINATING_BEHAVIOR. If the subordinate UTM terminates normally the halt decider UTM transitions to its own final state of SUBORDINATE_HAS_TERMINATED. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 26 04:27PM -0500 On 10/26/2020 4:07 PM, Alan Mackenzie wrote: >> again and no one has understood. > That suggests that your explanation is poor, or that you fail yourself to > understand what you're trying to explain. Tracing hundreds of steps of recursive invocation cannot not be explained in any simple way. I have given the answer many times. It is (apparently) too difficult to understand without an actual execution trace. >> bool Aborted_Because_Non_Halting_Behavior_Detected(M, M) >> always decides its input correctly and cannot be shown otherwise. > It does not, and it has been shown otherwise. I am not saying the code always gets the right answer to do this I have to provide an infinite proof. I am saying that unlike the conventional self-referential halting problem proofs no counter-example can be provided that shows that it necessarily gets the wrong answer. If you really think that I must be wrong then try and find such a counter-example proving that I am wrong. As soon as you find out that this is logically impossible it might begin to occur to you that I might be right. > Your problem is that you do not understand the maths, that you refuse to > understand the maths, and that you do not take advice and help from > people who do understand it. It is not about the math. It is about the computer science. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 26 04:31PM -0500 On 10/26/2020 4:08 PM, Malcolm McLean wrote: >> You have not shown any input where the following design necessarily gets >> the wrong answer: > I'm not disagreeing with you. I'm trying to clarify what you say. Great! Please try and find a counter-example where a halt decider defined as follows would necessarily fail, or agree that the conventional halting problem proof trick no longer works on such a halt decider: The redefined halt decider UTM executes its subordinate UTM one state transition at a time until it detects non-halting behavior or its subordinate UTM has terminated normally. If the halt decider UTM detects non-halting behavior of its subordinate UTM it simply stops executing the subordinate and transitions to its own final state of ABORTED_NON_TERMINATING_BEHAVIOR. If the subordinate UTM terminates normally the halt decider UTM transitions to its own final state of SUBORDINATE_HAS_TERMINATED. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 26 04:35PM -0500 On 10/26/2020 4:26 PM, Keith Thompson wrote: > "function", and what that definition is -- especially when C code is > begin discussed. Readers of comp.theory might not be familiar with the > way you use words. Upon a suggestion of another poster we can hypothetically assume that the x86utm language does not provide any user code access to global data. This change would seem to make what Malcolm said true. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 26 04:57PM -0500 On 10/26/2020 4:07 PM, Alan Mackenzie wrote: >> bool Aborted_Because_Non_Halting_Behavior_Detected(M, M) >> always decides its input correctly and cannot be shown otherwise. > It does not, and it has been shown otherwise. If you were paying very close enough attention rather than merely glancing at a few words here and there under the presumption that I must be incorrect you would notice that none of the examples ever showed a single case where: bool Aborted_Because_Non_Halting_Behavior_Detected(u32 M, u32 N) ever returned an incorrect value for its input. When there are two or three simultaneous instances of H_Hat and two different instances of the halt decider each one being executed in its own process context it may be a little difficult to see which halt decider makes the decision and which H_Hat is the input basis for its decision. A full execution trace will solve this problem. -- Copyright 2020 Pete Olcott |
| Mike Terry <news.dead.person.stones@darjeeling.plus.com>: Oct 26 07:25PM On 26/10/2020 17:36, olcott wrote: >> So for starters you need to define: >> 1) The program spec for >> Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) ?? > To the question: > Does H_Hat halt on it input H_Hat? > Both Yes and No are the wrong final state to transition to. None of that explains what you mean by "impossible to decide correctly" in the context of your challenge, or even make sense in the context of the HP... For GIVEN (/FIXED/) programs H and H_Hat, the calculation H_Hat(H_Hat) either halts or never halts, right? Exactly one of those possibilities is correct. So there IS a perfectly correct answer to the question "Does H_Hat(H_Hat) halt?". A halt decider "decides correctly" if it halts in the corresponding halt decider state (Yes [HALTS or NONHALTS[halts] or q_n [doesn't halt]). So in fact, one of the Yes and No IS the right final state to transition to! The fact is simply H is one of those putative halt deciders that transitions to the WRONG state. Let's make this clearer. For YOUR ACTUAL (soon to be delivered) H and H_Hat, which of these is the case? a) H_Hat(H_Hat) halts b) H_Hat(H_Hat) never halts > shortly. Since I have worked on this about 80 hours per weeks for six > months I have reduced my coding time to less than 40 hours per week for > this home stretch. OK, so you must at least know the answer to my (a) (b) question above, right? >> quite restrictive guidelines for line lengths. I'm all for suggestive >> function names, but we need to be practical! What about ABNHBD()? > No, Not all. Not in the least little bit. Repeating this clumsy phrase makes you look goofy. > The name must be utterly self-descriptive to eliminate any confusion Well, I'm not going to keep on typing all that, so I'll use ABNHBD, and you'll know what I mean. The right way to eliminate confusion is for you to give the specification for the routine, which you've not done yet. The long name fails as a spec! >> Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) gives a >> response that doesn't meet it's spec." > Yes You're saying this is the correct answer to my question (2)? Then you should have said this in response to the question, whereas what you actually answered was a long description of two programs, with an incorrect statement about "wrong states". So... now you need to give that spec! > and I show an overview of the architecture of the halting algorithm > as it would be applied to a UTM halt decider deciding the halting of its > subordinate UTM below: [... snip ...] I never asked about this, and you've said all this elsewhere. Regards, Mike. |
| olcott <NoOne@NoWhere.com>: Oct 26 02:43PM -0500 On 10/26/2020 2:25 PM, Mike Terry wrote: > None of that explains what you mean by "impossible to decide correctly" > in the context of your challenge, or even make sense in the context of > the HP... So in other words it is far too difficult for you to understand that: (a) H.MOV_EAX_0 // in Linz it is a transition to a final state of ((qn)) (b) H.MOV_EAX_1 // in Linz it is a transition to a final state of ((qy)) are both the wrong answer. If you can't acknowledge this you may have to be written off as not actually interested in achieving a mutual understanding. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 26 02:05PM -0500 On 10/26/2020 1:12 PM, André G. Isaak wrote: > H_Hat doesn't specify any sort of recursion, so I don't know why you > keep claiming that. Even in an implementation where your H actually > 'executes' H_Hat in some sort of modified environment, it is not recursive. When Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) is executed in the x86utm process context it creates a new process context and executes H_Hat() in DebugStep() mode within this new H_Hat() process context. This DebugStep() mode reaches Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) in _Hat() and creates another process context in the _Hat() process context. Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) executes this other instance of H_Hat() in the process context of the prior H_Hat(). As soon as it reaches Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) in the second H_Hat() instance the outer Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) that has been watching all of the execution steps in all of the process contexts sees that H_Hat() is invoking Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) from the same machine address a second time without encountering any conditional branch instructions in H_Hat() that would terminate its otherwise infinite recursion. At this point Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) stops executing the first instance of H_Hat() (which also stops everything else in this process tree) and returns TRUE. > itself, it is calling a separate function within H_Hat that just happens > to be identical to the one in H (similarly, the inner H_Hat has its own, > separate, copy of Aborted_Because_Non_Halting_Behavior_Detected) On 10/23/2020 5:51 PM, Mike Terry wrote: > int H_Hat(u32 M) > { > if (Was_Its_Execution_Aborted(M, M)) The above simplified H_Hat() provided by Mike has been applied to the Peter Linz H_Hat() to make it conform to the model of the conventional self-referential halting problem counter-examples: void H_Hat(u32 M) { if (!Halts(M, M)) MOV_EAX_0 // Input Loops else { MOV_EAX_1 // Input Halts HERE: goto HERE; } HALT } > tape configuration about which it answers the question 'will this halt'? > There's nothing in that requiring that anything 'calls' anything, > recursively or otherwise. As you continue to keep ignoring I show how a halt decider can be defined that avoids the conventional halting problem trick. That Peter Linz showed one way that a halt decider will not always work does not show that the halting problem is undecidable. > is not identical to the one in H, then you aren't constructing the > proper relation between H and H_Hat. > André When-so-ever it detects non-halting behavior the halt decider UTM stops executing its subordinate UTM in one state transition at a time mode and transitions to its own final state of: ABORTED_NON_TERMINATING_BEHAVIOR. -- 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