- Architectural design of a halting problem solution - 3 Updates
- The key aspects of x86utm are now finally complete [ HP proof refutation has been provided ] correction - 15 Updates
- The x86utm operating system shows how the halting problem can be made decidable - 6 Updates
- Fat Binary - MS-Windows and four Linux - 1 Update
| olcott <NoOne@NoWhere.com>: Oct 27 02:30PM -0500 Intuitively, a decider should be a Turing machine that given an input, halts and either accepts or rejects, relaying its answer in one of many equivalent ways, such as halting at an ACCEPT or REJECT state, or leaving its answer on the output tape.Yuval Filmus https://cs.stackexchange.com/questions/84433/what-is-decider Yuval Filmus top 0.04% overall Assistant Professor in the Department of Computer Science at the Technion. It is common knowledge that a halt decider with the following architectural design can be thwarted by an input program that does the opposite of whatever the halt decider decides: The halt decider divides all of its inputs into: (a) HALTS (b) DOES_NOT_HALT This brand new architectural design cannot be thwarted by the conventional self-referential halting problem trick. With this design there is no input that can be shown to be undecidable: The halt decider that divides all of its inputs into: (a) INPUT_PROGRAM_ABORTED_BECAUSE_NON_HALTING_BEHAVIOR_DETECTED (b) INPUT_PROGRAM_HAS_TERMINATED 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 |
| "André G. Isaak" <agisaak@gm.invalid>: Oct 27 01:46PM -0600 On 2020-10-27 13:30, olcott wrote: > The halt decider divides all of its inputs into: > (a) HALTS > (b) DOES_NOT_HALT That isn't an 'architectural design'. That's simply a definition of what a halt decider does. Anything which does not do the above is not a halt decider. The above says nothing whatsoever about 'architectural design'. André -- To email remove 'invalid' & replace 'gm' with well known Google mail service. |
| olcott <NoOne@NoWhere.com>: Oct 27 03:02PM -0500 On 10/27/2020 2:46 PM, André G. Isaak wrote: >> (b) DOES_NOT_HALT > That isn't an 'architectural design'. That's simply a definition of what > a halt decider does. Then my solution can be called a redefinition: The halt decider that divides all of its inputs into: (a) INPUT_PROGRAM_ABORTED_BECAUSE_NON_HALTING_BEHAVIOR_DETECTED (b) INPUT_PROGRAM_HAS_TERMINATED > Anything which does not do the above is not a halt > decider. The above says nothing whatsoever about 'architectural design'. > André Then we can call it the definition of a NON_HALTING_DECIDER. None of its inputs would halt unless it aborts their execution and all of the rest of its inputs would halt. -- Copyright 2020 Pete Olcott |
| Mike Terry <news.dead.person.stones@darjeeling.plus.com>: Oct 27 12:06AM On 26/10/2020 18:14, olcott wrote: > In both cases the input H_Hat would not halt unless it has been aborted: > H_Hat(H_Hat) > H(H_Hat, H_Hat) Talking about what /would/ happen if xxxxx is confusing the discussion, I think. By now you must know for your ACTUAL FINAL coded H and H_Hat: Does the calculation H_Hat(H_Hat) halt? I'm not talking about what its internal Aborted_Because_Non_Halting_Behavior_Detected(M, N) routine does, or what happens in any internal emulations of anything. >> That is why this is the correct halt decider question: >> bool Aborted_Because_Non_Halting_Behavior_Detected(M, N) It is only the correct halt decider question if it actually relates to the halting of calculation (M,N). Otherwise it is not a halt decider, it's a "Internal routine aborted something" decider. Mike. |
| Keith Thompson <Keith.S.Thompson+u@gmail.com>: Oct 26 05:16PM -0700 Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes: [SNIP] Mike, and everyone else, please drop the comp.lang.* newsgroups when you post a followup to one of olcott's articles. -- Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com Working, but not speaking, for Philips Healthcare void Void(void) { Void(); } /* The recursive call of the void */ |
| olcott <NoOne@NoWhere.com>: Oct 26 08:11PM -0500 On 10/26/2020 7:06 PM, Mike Terry wrote: >> H(H_Hat, H_Hat) > Talking about what /would/ happen if xxxxx is confusing the discussion, > I think. That is the problem with posting my results a little bit prematurely. If I simply provided the execution trace of exactly what each one of the virtual machines actually does in each one of their process contexts then it would not be possible to simply disagree that these are the actual execution traces. Since each process context has its own unique memory address and I have updated the x86utm operating system to have some Output() functions I will be able to provide this execution trace fairly soon. > By now you must know for your ACTUAL FINAL coded H and H_Hat: Does the > calculation H_Hat(H_Hat) halt? The key thing to realize is that this function cannot be shown to ever provide an incorrect return value: bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I); All of the other things are simply dodges. In your case not a dishonest dodge. > I'm not talking about what its internal > Aborted_Because_Non_Halting_Behavior_Detected(M, N) routine does, or > what happens in any internal emulations of anything. The key thing to realize is that this function cannot be shown to ever provide an incorrect return value: bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I); This requires knowing in a very complex recursive invocation sequence exactly which instance of that function is returning a value and exactly which instance of H_Hat is its actual input. It turns out that the outermost invocation of bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I); bases its decision on its first parmeter. > It is only the correct halt decider question if it actually relates to > the halting of calculation (M,N). Otherwise it is not a halt decider, > it's a "Internal routine aborted something" decider. This function cannot be shown to ever return an incorrect value: bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I); -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 26 08:35PM -0500 On 10/26/2020 7:59 PM, Richard Damon wrote: > A C function can only give differing outputs if there is state hidden > elsewhere, for a Turing machine, that state would be explicit in the > machine or input. Good answer, better than mine. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 26 10:38PM -0500 On 10/26/2020 9:48 PM, Mike Terry wrote: >> actual execution traces. > Nobody has simply disagreed with any execution traces, because you have > not provided any, I have provided complete description of all of the key elements of the execution trace such that it can be understood bool Aborted_Because_Non_Halting_Behavior_Detected(H_hat, H_Hat) does return the correct value. It is a fact that I did totally prove this point as long as the actual execution is as I have described. It is also reasonably likely that this detailed description may been too difficult to understand. > and more to the point you have refused to answer > questions about your code like whether H_Hat(H_Hat) halts. So this is > not an issue. bool Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) does provide the correct return value. It cannot be shown that it ever does not provide the correct return value. >> bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I); > Since you have refused to provide any spec for > Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I), or to I provided the complete description of the execution trace that proves that it decides (H_Hat, H_Hat) correctly. That this answer was too difficult for you to understand is no evidence what-so-ever that I not provide a complete answer. I acknowledge that if you don't understand an answer that you would have no direct evidence that it is an answer. That is easily fixed. I just have to finish writing the code that fully implements this answer. > define what "return an incorrect value" means, no wonder! It is a > meaningless claim until you clarify exactly what it means. This statement is seeming to be quite disingenuous at this point. Which line of H decides H(H_Hat, H_Hat) correctly: {04, 06} ? Any answer not from this set: {04, 06} indicates that you are trying to dodge the idea of "return an incorrect value" and you always knew all along exactly what I meant. void H_Hat(u32 M) { if (!Halts(M, M)) MOV_EAX_0 // Does not Halt else { MOV_EAX_1 // Halts HERE: goto HERE; } HALT } 01 void H(u32 M, u32 N) 02 { 03 if (!Halts(M, M)) 04 MOV_EAX_0 // Does not Halt 05 else 06 MOV_EAX_1 // Halts 07 HALT 08 } int main() { u32 M = (u32)H_Hat; H(M, M); HALT } > value that disagrees with its spec", but you've never given a spec! And > I don't believe that's actually what you mean anyway, but that's all > you've revealed. I have given the complete spec as a detailed description of the execution trace of how Aborted_Because_Non_Halting_Behavior_Detected() decides (H_Hat, H_Hat) very many times now. It is either that it is too difficult for you to understand or you don't believe that my description is accurate. If it is not too difficult for you to understand then you could evaluate it hypothetically while I write the actual code. If it is too difficult for you to understand ten I will shortly have the code. > the Linz proof), and whether H correctly decides the halting for H^ > running with input H^. THAT is what you've always said you were going > to deliver. I have done that a bunch of times now. It is OK if what I said is too complex to understand. I will write the actual code and then make its execution trace only show the key decision points. -- Copyright 2020 Pete Olcott |
| "André G. Isaak" <agisaak@gm.invalid>: Oct 27 04:53AM -0600 On 2020-10-26 15:57, olcott wrote: > single case where: > bool Aborted_Because_Non_Halting_Behavior_Detected(u32 M, u32 N) > ever returned an incorrect value for its input. Can we get you to commit the following more precise set of claims? (1) In every instance where its input would not halt when run independently, you ABNHBD function will always return 'non halting behavior detected - aborted' (2) In every instance where its input would halt when run independently, your ABNHBD will return 'terminated normally' (3) Your ABNHBD function is actually guaranteed to return one of the above two values for every input. André -- To email remove 'invalid' & replace 'gm' with well known Google mail service. |
| olcott <NoOne@NoWhere.com>: Oct 27 09:53AM -0500 On 10/27/2020 2:03 AM, Alan Mackenzie wrote: >> It is (apparently) too difficult to understand without an actual >> execution trace. > Or your idea is simply incoherent. You can't show any incoherence with this because there is none. You can dogmatically assert incoherence yet can not show it proving that your assertion is merely vacuous. I will soon have fully operational code that shows this: bool Aborted_Because_Non_Halting_Behavior_Detected(H-Hat, H_Hat) decides its input correctly. It creates another process context and executes H-Hat(H_Hat) in this process context in DebugStep() mode. This instance of H_Hat() executes another instance of bool Aborted_Because_Non_Halting_Behavior_Detected(H-Hat, H_Hat) in its own process context. This instance of bool Aborted_Because_Non_Halting_Behavior_Detected(H-Hat, H_Hat) creates another process context and executes yet another H-Hat(H_Hat) in this third process context in DebugStep() mode. // 2018-12-13 @7:00 PM solution As soon as H_Hat's second invocation executes bool Aborted_Because_Non_Halting_Behavior_Detected(H-Hat, H_Hat) a second time from the same machine address and there is no conditional code in the execution trace of H_Hat that would terminate this otherwise infinite recursion then the first instance of bool Aborted_Because_Non_Halting_Behavior_Detected(H-Hat, H_Hat) stops executing H_Hat() in DebugStep() mode and reports true. This same process can be implemented as UTMs executing subordinate UTMs one state transition at a time where each subordinate UTM has its own portion of the master UTM tape. >>>> bool Aborted_Because_Non_Halting_Behavior_Detected(M, M) always >>>> decides its input correctly and cannot be shown otherwise. > So you're either confused or a liar. Here it is much more accurately: It is a partial WOULD_NOT_HALT decider that cannot be shown to have any undecidable input. I say things imprecisely initially so that people can get the gist of the idea before narrowing it down to a more precise statement. >> .... to do this I have to provide an infinite proof. > For which you'd need to learn some mathematics. By merely providing all the steps (see above) of deciding bool Aborted_Because_Non_Halting_Behavior_Detected(H-Hat, H_Hat) I have already proved my point. > returning one of two values, "halts", "doesn't halt". Such functions > have been shown to be impossible. The precise internal details are > unimportant, and I'm not that much interested in them. If we try to return those two values then the input program can do the opposite of whatever the halt decider decides, making halting undecidable. So instead we return these two values: (a) Aborted_Because_Non_Halting_Behavior_Detected (b) Has_Already_Terminated_Normally >> counter-example proving that I am wrong. > I've already done that - a brute force search for a counter-example to > Goldbach's Conjecture. No that example merely shows that you have failed to distinguish between undecided and undecidable. GC is the former and not the latter. In any case I have shown that all of the conventional halting problem proofs do not show that the halting problem is undecidable >> begin to occur to you that I might be right. > It is logically impossible for you to be right, but for some reason you > assume that logic that is beyond your capabilities doesn't apply to you. Or the only reason why no one has correctly shown any mistake in my work is that there is no mistake in my work and I am correct. >>> people who do understand it. >> It is not about the math. It is about the computer science. > That is a truly ignorant remark. Math defines some of its terms differently. I am not referring to those definitions. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 27 10:20AM -0500 On 10/27/2020 5:53 AM, André G. Isaak wrote: > (1) In every instance where its input would not halt when run > independently, you ABNHBD function will always return 'non halting > behavior detected - aborted' Here is what I can commit to: There is no input to this function that can be shown to be undecidable: bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) > (2) In every instance where its input would halt when run independently, > your ABNHBD will return 'terminated normally' H_Hat(H_Hat) only terminates because one of the instances of this recursive invocation was aborted. If none of the instances of its recursive invocation were aborted then H_Hat(H_Hat) would never terminate. H_Hat(H_Hat) is yet another example where bool Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) decides its input correctly. > (3) Your ABNHBD function is actually guaranteed to return one of the > above two values for every input. bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) is a partial WOULD_NOT_HALT decider that will initially only decide (H_Hat, H_Hat). The design for it to correctly decide two other infinite classes of computations is already complete. At no point in my presentation of it will it ever be all knowing. Once it is accepted that this design proves that the conventional self-referential halting problem proofs do not show that the halting problem is undecidable funding may be allocated to enhance the robustness of the halt decider design using deep learning. I would not be interested in this project myself. My interest in in perfecting the upper knowledge ontology of natural language. https://en.wikipedia.org/wiki/Upper_ontology One of the key purposes of this halting problem project is to gain very significant credibility to be able to work on the architecture of the upper knowledge ontology of AI projects like Cyc. The key thing that these projects need is an automated self-validating process to self populate their knowledge base. My upper ontology work would be focused on solving this problem. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 27 10:28AM -0500 On 10/27/2020 9:52 AM, Malcolm McLean wrote: > } > Can't you see what PO is saying? The contradiction no longer exists when we change the function > from "halts" to "AbortedBecauseNonHaltingBehaviourDetected. Yes that is the correct key conclusion. u32 AbortedBecauseNonHaltingBehaviourDetected(u32 P, u32 I) already does a multi level recursive DebugStep(). I have already posted the every single step detailed design of exactly how u32 AbortedBecauseNonHaltingBehaviourDetected(H_Hat, H_Hat) is decided. So I have already proved my point that (H_Hat, H_Hat) is decidable. The last step is writing the code that decides (H_Hat, H_Hat). -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 27 11:00AM -0500 On 10/27/2020 9:30 AM, Mike Terry wrote: > This is what I've been trying to get PO to clarify in my last few posts. > He steadfastly declines to provide an actual specification for what > his ABNHDB() function, or even to clarify anything about what it does, This is about ten times now that I have provided a complete description of the full execution trace of how (H_Hat, H_Hat) is decided: (Your claim that I have never answered this question now seems dishonest). bool Aborted_Because_Non_Halting_Behavior_Detected(H-Hat, H_Hat) decides its input correctly. It creates another process context and executes H-Hat(H_Hat) in this process context in DebugStep() mode. This instance of H_Hat() executes another instance of bool Aborted_Because_Non_Halting_Behavior_Detected(H-Hat, H_Hat) in its own process context. This instance of bool Aborted_Because_Non_Halting_Behavior_Detected(H-Hat, H_Hat) creates another process context and executes yet another H-Hat(H_Hat) in this third process context in DebugStep() mode. // 2018-12-13 @7:00 PM solution As soon as H_Hat's second invocation executes bool Aborted_Because_Non_Halting_Behavior_Detected(H-Hat, H_Hat) a second time from the same machine address and there is no conditional code in the execution trace of H_Hat that would terminate this otherwise infinite recursion then the first instance of bool Aborted_Because_Non_Halting_Behavior_Detected(H-Hat, H_Hat) stops executing H_Hat() in DebugStep() mode and reports true. This same process can be implemented as UTMs executing subordinate UTMs one state transition at a time where each subordinate UTM has its own portion of the master UTM tape. > saying that he's given a "trace" that shows it making the right decision > (whatever that means!). (He refuses to say define what the "right > decision" is, when it's called with an input pair (Pgm, Data).) That is such a foolish thing to say. You are being as dishonest as Ben. bool Aborted_Because_Non_Halting_Behavior_Detected(H-Hat, H_Hat) if the above function did detect non halting behavior then Non_Halting_Behavior_Detected is true. if the above function did abort the execution of its input then Aborted_ is true. If the above function detected non halting behavior and aborted the execution of its input because it detected non halting behavior then Aborted_Because_Non_Halting_Behavior_Detected is true. > The most I've ever seen him say is that ABNHDB() steps through its input > program's execution until either it halts, or it "detects non-halting > behaviour", but he WON'T clarify "non-halting behaviour", even to the Yet another dishonesty. The above detailed description of the execution trace of (H_Hat, H_Hat) is terminated as soon as bool Aborted_Because_Non_Halting_Behavior_Detected(H-Hat, H_Hat) is invoked from the same machine address of H_Hat without any conditional branch instruction in H_Hat that would terminate this otherwise infinite recursion. This is my 2018-12-13 @ 7:00 PM solution. > decider isn't all-knowing, and it may not work with /every/ input". > Fine, we know it only has to work with his H_Hat(H_Hat) calculation. All > my attempts to get him to talk about that specific case come to nothing. Intuitively, a decider should be a Turing machine that given an input, halts and either accepts or rejects, relaying its answer in one of many equivalent ways, such as halting at an ACCEPT or REJECT state, or leaving its answer on the output tape.Yuval Filmus https://cs.stackexchange.com/questions/84433/what-is-decider Yuval Filmus top 0.04% overall Assistant Professor in the Department of Computer Science at the Technion. The architectural design that I provide is of a halt decider that divides all of its input into: (a) ABORTED_BECAUSE_NON_HALTING_BEHAVIOR_DETECTED (b) HAS_ALREADY_HALTED The actual fully operational software that I will provide will be a partial ABORTED_BECAUSE_NON_HALTING_BEHAVIOR_DETECTED decider. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 27 11:05AM -0500 On 10/27/2020 10:45 AM, Malcolm McLean wrote: > I'm trying to get an insight into why PO is convinced that he has refuted > the Linz proof. I might be wrong - I'm not him, I can't read his mind, and > he's not been entirely consistent. But I think I've identified it. The Linz proof** claims to have proved the the halting problem is undecidable. It has not actually proved this. All of these proofs merely show one architectural design of a halt decider that gets the wrong answer some of the time. My architectural design of a halt decider cannot be shown to get the wrong answer any of the time. ** And all of the conventional self-referential halting problem proofs. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 27 01:36PM -0500 On 10/27/2020 11:53 AM, Malcolm McLean wrote: > Do you agree that AbortedBecauseNonHaltingBehaviourDetected() can be > stubbed to deal only with the input H_Hat, H_Hat? Or does this change > somethin fundamental? It is no good to merely stub this function when the complete description of the execution trace showing exactly how (H_Hat, H_Hat) is decided correctly has already been provided. Instead of a stub function we could simply assume that: bool Aborted_Because_Non_Halting_Behavior_Detected(u32 N, u32 M); always returns a correct result meaning that it: "only aborts its input and returns true when it detects the non halting behavior of its input" and otherwise returns false. Then we try to do the same thing as the conventional halting problem proofs and see if there is any input that it cannot correctly decide. -- Copyright 2020 Pete Olcott |
| "André G. Isaak" <agisaak@gm.invalid>: Oct 27 12:53PM -0600 On 2020-10-27 09:20, olcott wrote: > Here is what I can commit to: > There is no input to this function that can be shown to be undecidable: > bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) Are you attempting to answer my first question or my third question here? Saying no input is undecidable would seem to be an answer to my third question. It doesn't seem to have any relevance to my first question. > terminate. H_Hat(H_Hat) is yet another example where > bool Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) > decides its input correctly. So when we consider H(H_Hat, H_HAT) what are you claiming is the output of: (1) Your ABNHBD contained in H (2) Your ABNHBD contained in the outermost instance of H_Hat? > bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) > is a partial WOULD_NOT_HALT decider that will initially only decide > (H_Hat, H_Hat). This contradicts your earlier claim that no input to this function can be undecidable. Are you here claiming that there *are* inputs that aren't decidable, or that there are currently inputs that are not *correctly* decidable? André -- To email remove 'invalid' & replace 'gm' with well known Google mail service. |
| olcott <NoOne@NoWhere.com>: Oct 27 02:44PM -0500 On 10/27/2020 2:05 PM, Malcolm McLean wrote: >> proofs and see if there is any input that it cannot correctly decide. > As I understand it, instead of HALTS / RUNSFOREVER it returns > HALTS / ABORTED. We can explore the difference. New thread: (explores the difference) [Architectural design of a halting problem solution] -- Copyright 2020 Pete Olcott |
| "André G. Isaak" <agisaak@gm.invalid>: Oct 27 01:57PM -0600 On 2020-10-27 10:05, olcott wrote: > show one architectural design of a halt decider that gets the wrong > answer some of the time. My architectural design of a halt decider > cannot be shown to get the wrong answer any of the time. Linz doesn't specify anything at all about the 'architectural design' of H. All he does is claim that H is a halt decider; it's internal workings are left entirely unspecified. He shows that for *any* given H it is possible to derive a second TM, H_Hat, such that if the description of H_Hat is used as the input to H, H will not be able to correctly decide whether H_Hat halts. There's absolutely *no* assumptions made about the internal workings / 'architectural design' of H. André -- To email remove 'invalid' & replace 'gm' with well known Google mail service. |
| olcott <NoOne@NoWhere.com>: Oct 26 08:34PM -0500 On 10/26/2020 7:43 PM, Mike Terry wrote: > H_Hat(H_Hat) halt?", then one of them is the correct answer, BUT H HAS > ALREADY BEEN WRITTEN, and it's too late to change the code, and the > actual code halts with the wrong state. The above way of defining a halt decider provides only a single possible way for the halt decider to provide its halting decision: (a) H transitions to its final state of ((qy)) indicating YES its input halts. (b) H transitions to its final state of ((qn)) indicating NO its input does not halt. Because both of these return values can be contradicted by the behavior of H_Hat() neither one of them is correct. Do you understand and agree with this? -- Copyright 2020 Pete Olcott |
| Mike Terry <news.dead.person.stones@darjeeling.plus.com>: Oct 27 02:11AM On 27/10/2020 01:34, olcott wrote: > halts. > (b) H transitions to its final state of ((qn)) indicating NO its input > does not halt. Any decider has two states, qy and qn that indicate its decision. For a halting decider, they have the meanings you describe. > Because both of these return values can be contradicted by the behavior > of H_Hat() neither one of them is correct. For a given H, the logic is already fixed in H as to which of these states it will transition to, for any particular input. It is too late to start talking about rewriting H a different way. There is only one of the states that H can transition to for a given input, and that is the one its code determines. In the case of H_Hat, that code leads to the wrong state. > Do you understand and agree with this? I understand what I have written. Maybe that is the same as what you mean. Mike. |
| olcott <NoOne@NoWhere.com>: Oct 26 09:57PM -0500 On 10/26/2020 9:11 PM, Mike Terry wrote: >> does not halt. > Any decider has two states, qy and qn that indicate its decision. For a > halting decider, they have the meanings you describe. Intuitively, a decider should be a Turing machine that given an input, halts and either accepts or rejects, relaying its answer in one of many equivalent ways, such as halting at an ACCEPT or REJECT state, or leaving its answer on the output tape. Yuval Filmus https://cs.stackexchange.com/questions/84433/what-is-decider Yuval Filmus top 0.04% overall Assistant Professor in the Department of Computer Science at the Technion. 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. Thus dividing ALL of its input into one of two mutually exclusive categories proving that meets the above definition of a decider. The second category is exactly the same thing as HALTING so it is a halt decider. >> Do you understand and agree with this? > I understand what I have written. Maybe that is the same as what you mean. > Mike. I have never detected a single moment where you were insincere or disingenuous so that is very good. If we both really very sincerely want to achieve mutual understanding then I am sure that we will definitely get there, these things don't have the kind of subjectivity that could be permanently unresolvable. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 26 11:16PM -0500 On 10/26/2020 11:03 PM, Mike Terry wrote: > Just to be clear, HALTING is the category of pairs (P, I) such that P > when run with input I halts. (I don't see what else you could mean...) > Mike. Because it will not be all knowing there will initially be only one case that it decides ABORTED_NON_TERMINATING_BEHAVIOR and that is (H_Hat, H_Hat). Every other case it will simply assume halts. The key thing is that there are no cases that can be shown to be undecidable for a partial halt decider of this design. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 26 11:29PM -0500 On 10/26/2020 11:16 PM, olcott wrote: > (H_Hat, H_Hat). Every other case it will simply assume halts. > The key thing is that there are no cases that can be shown to be > undecidable for a partial halt decider of this design. It seems that it is a partial WOULD_NOT_HALT decider. It is not even looking at halting. It is only looking at WOULD_NOT_HALTing. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 27 11:22AM -0500 On 10/27/2020 9:57 AM, Mike Terry wrote: >> looking at halting. It is only looking at WOULD_NOT_HALTing. > OK, I know we are only interested in the input pair (H_Hat, H_Hat). > You say it is only detecting WOULD_NOT_HALTing. What does that mean? Do you think that it might mean that someone smashed their vanilla ice cream cone on the floor? How about it meaning that I went for a long drive in the country on a sunny day? > Specifically the problem is your inclusion of the word "WOULD". Any > calculation P(I) [for pgm P, with input data I] is either halting or > non-halting. ABORTED_BECAUSE_NON_HALTING_BEHAVIOR_DETECTED > Is the following true? > - ABNHBD(H_Hat, H_Hat) will only return ABORTED if H_Hat(H_Hat) is > non-halting. Not exactly and precisely. bool Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) returns true whenever its input has to be aborted or the halt decider would get stuck in infinite recursion. > HALTING is the usual HP term for the category of pairs (P,I) where P > halts when it runs with input I, i.e. nothing to do with emulators or > "aborting" anything!] Not exactly and precisely because the way that the categories are conventionally divided into HALTING and LOOPING allows an input program to do the opposite of whatever the halt decider decides. These categories eliminate that problem: (a) ABORTED_BECAUSE_NON_HALTING_BEHAVIOR_DETECTED (b) INPUT_HAS_ALREADY_HALTED > Turning this around, this equivalent statement may be easier: > - If calculation H_Hat(H_Hat) halts, ABNHBD(H_Hat, H_Hat) will not > return ABORTED. No, not at all, not in the least little bit. bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) is the architectural design of a halt decider that always correctly divides all of its inputs into: (a) ABORTED_BECAUSE_NON_HALTING_BEHAVIOR_DETECTED (b) INPUT_HAS_ALREADY_HALTED -- Copyright 2020 Pete Olcott |
| gazelle@shell.xmission.com (Kenny McCormack): Oct 27 03:41PM In article <1db47fad-3dee-40c0-bf7d-7e34f35425f1o@googlegroups.com>, >typically prints "This program cannot be run in DOS mode". >If I replace the stub with a 16-Bit version of the sha256 program, then >the fat binary will also run on MS-DOS 6.22. Why don't you? Why not go all the way? -- Note that Oprah actually is all the things that The Donald only wishes he were. For one thing, she actually *is* a billionaire. She's also actually self-made, came from nothing, knows how to run businesses, never went bankrupt, is smart and is mentally stable. |
| 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