| olcott <NoOne@NoWhere.com>: Oct 27 03:13PM -0500 On 10/27/2020 3:03 PM, Mike Terry wrote: > decidable, including many whose domain is the same as that halting > problem's. Possibly if you made the definition of the your decision > well defined, it could be one of those... I have redefined the impossible halt decider into a NON_HALTING_DECIDER that divides all of its inputs into: (a) INPUT_PROGRAM_ABORTED_BECAUSE_NON_HALTING_BEHAVIOR_DETECTED (b) INPUT_PROGRAM_HAS_TERMINATED As you can see from (b) the NON_HALTING_DECIDER is still a halt decider. -- Copyright 2020 Pete Olcott |
| "André G. Isaak" <agisaak@gm.invalid>: Oct 27 02:34PM -0600 On 2020-10-27 14:13, olcott wrote: > (a) INPUT_PROGRAM_ABORTED_BECAUSE_NON_HALTING_BEHAVIOR_DETECTED > (b) INPUT_PROGRAM_HAS_TERMINATED > As you can see from (b) the NON_HALTING_DECIDER is still a halt decider. If your (a) and (b) are simply new names for 'doesn't halt' and 'halts', then this is just as subject to Linz's proof as any other purported halt decider. If they are not, and there are cases where 'aborted' and 'halted' don't mean exactly the same thing, then what you have isn't a halt decider at all. A halt decider determines if a particular TM, T, will halt for input I. IOW, it tells us something about the behaviour of T when confronted with input I. Part (b) of your 'redefinition' presupposes that we have actually already run T(I). That still tells us that T(I) halts, but we could have just run T(I) ourselves to make this determination, so your 'redefinition' doesn't provide us with any useful information in this case. Part (a) of your redefinition is where things really get mucked up since it presupposes that we have already attempted to run T(I); moreover, we have done it in some sort of specialized environment E in which it is possible to force things to abort. Therefore, your 'revision' is asking how T behaves when confronted with input I IN ENVIRONMENT E. Whereas the actual definition of a halt decider tells us about T, in your 'revised' version we have no way of knowing whether it is telling us about T or about E in cases where the input is forced to terminate. What you have isn't analogous to a halt decider. It is a How-does-this-TM-behave-in-environment-E decider. Unless you can provide some reason why I should care about how things behave in environment E (or environment E at all, for that matter), this isn't something that is of interest. André -- To email remove 'invalid' & replace 'gm' with well known Google mail service. |
| olcott <NoOne@NoWhere.com>: Oct 27 04:23PM -0500 On 10/27/2020 3:34 PM, André G. Isaak wrote: > If your (a) and (b) are simply new names for 'doesn't halt' and 'halts', > then this is just as subject to Linz's proof as any other purported halt > decider. I dared anyone to show this and they absolutely could not because it is impossible. > If they are not, and there are cases where 'aborted' and 'halted' don't > mean exactly the same thing, then what you have isn't a halt decider at > all. The above two sets are the exact same sets that a correct halt decider would decide. > A halt decider determines if a particular TM, T, will halt for input I. Apparently it is much easier to decide the cases that would not halt unless aborted and leave the halting cases as those that are left over. > IOW, it tells us something about the behaviour of T when confronted with > input I. bool Aborted_Because_Non_Halting_Behavior_Detected(u32 T, u32 I) Try and find a (T, I) pair that the above function cannot correctly decide. By correctly decide what I mean is the totally obvious: The above function returns true and this sentence is true: "T was aborted because non halting behavior was detected." bool Aborted_Because_Non_Halting_Behavior_Detected(u32 T, u32 I) would be incorrect when it returns true and: (a) The input program was not aborted. (b) Non-halting behavior was not detected. (c) Non-halting behavior was erronesously reported. (d) The input program was aborted and the halt decider correctly detected non-halting behavior of the input program, yet the input program was aborted for some other reason besides the fact that non-halting behavior was detected. > already run T(I). That still tells us that T(I) halts, but we could have > just run T(I) ourselves to make this determination, so your > 'redefinition' doesn't provide us with any useful information in this case. You must not have through that one through very well. The NON_HALTING_DECIDER screens out all of the infinite executions. > have done it in some sort of specialized environment E in which it is > possible to force things to abort. Therefore, your 'revision' is asking > how T behaves when confronted with input I IN ENVIRONMENT E. No, not really, not at all. bool Aborted_Because_Non_Halting_Behavior_Detected(u32 T, u32 I) only aborts the execution of programs that would not otherwise halt. If H_Hat(H_Hat) did not have any of its otherwise infinitely recursive invocations terminated it would never stop running. 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 } int main() { u32 M = (u32)H_Hat; H_Hat(M); HALT } > us about T or about E in cases where the input is forced to terminate. > What you have isn't analogous to a halt decider. It is a > How-does-this-TM-behave-in-environment-E decider. No, not at all, not in the least. bool Aborted_Because_Non_Halting_Behavior_Detected(u32 T, u32 I) only aborts the execution of programs that would not otherwise halt. > behave in environment E (or environment E at all, for that matter), this > isn't something that is of interest. > André The following definition shows that it is not any specialied environment it is merely the conventional notion of a UTM. 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 27 04:27PM -0500 On 10/27/2020 4:11 PM, Mike Terry wrote: >> all. > Exactly, and in another thread PO has confirmed that 'aborted' includes > cases where the calculation in question halts. That is flat out not true. In every single case where this halt decider decides that its input must be aborted its input would not otherwise halt: bool Aborted_Because_Non_Halting_Behavior_Detected(u32 N, u32 M) Also in every single case where the above function returns false its input has already halted. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 27 04:54PM -0500 On 10/27/2020 4:44 PM, Malcolm McLean wrote: >> input has already halted. > So write a stub for bool Aborted_Because_Non_Halting_Behavior_Detected > that just works on the input H_Hat, H_Hat. That would be no better than telling people that I must be correct because I really know that I am right, the same petitio principii logical fallacy that they are using in their utterly vacuous rebuttals. I simply have to finish writing the actual halt deciding code for bool Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat). I already totally explained (2018-12-13 solution) exactly how this works. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 27 04:57PM -0500 On 10/27/2020 4:33 PM, Mike Terry wrote: > totally different programs. > I won't be repeating everything again in a new thread :) > Mike. It is totally your confusion not mine. bool Aborted_Because_Non_Halting_Behavior_Detected(u32 N, u32 M) always decides its inputs correctly. Your incorrect attempt at a counter-example was not an input to bool Aborted_Because_Non_Halting_Behavior_Detected(u32 N, u32 M) -- Copyright 2020 Pete Olcott |
| Mostowski Collapse <janburse@fastmail.fm>: Oct 27 09:07PM +0100 In what parallel universum does your nonsense have anything to do with Prolog? You fucking inhibited cross posting moron? No need to post responses on comp.lang.prolog. olcott schrieb: |
| 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