- Architectural design of a halting problem solution - 16 Updates
- T const - 1 Update
- Fat Binary - MS-Windows and four Linux - 1 Update
| olcott <NoOne@NoWhere.com>: Oct 27 06:43PM -0500 On 10/27/2020 5:07 PM, Malcolm McLean wrote: > But it's a very long way round. If you were writing a real fully-fledged > function, you would of course have to do this. But all you are doing is trying > to refute Linz. So you only need to handle one case. Not really. The hard part that took about 2000 hours was writing the x86utm operating system. I could finish the halt deciding code in 40 to 80 hours. I am definitely going to finish this code very soon. More importantly the impossibility of creating an input that bool Aborted_Because_Non_Halting_Behaviour_Detected(u32 P, u32 I) cannot correctly decide meaning that: "It only reports true in those cases where its input would not halt unless it was aborted and its input was aborted" and in all the others case is reports false. I can't begin to understand why Mike Terry had such an awfully difficult time with something as self-evident as this meaning. People don't seem to be able to stay focused on this single crucially important point: Find an input where bool Aborted_Because_Non_Halting_Behaviour_Detected(u32 P, u32 I) gets the wrong answer or admit that there is no such input. -- Copyright 2020 Pete Olcott |
| Richard Damon <Richard@Damon-Family.org>: Oct 27 09:45PM -0400 On 10/27/20 5:27 PM, olcott wrote: > 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. Except that it DOES get the wrong answer for H_Hat, because H_Hat DOES halt, at least if H give the answer that it aborted and H meets the requirements of a decider to be always finite in execution. The actual machine H_Hat was not aborted, just the simulation of the model of H_Hat run inside H, and that simulation MUST by definition be finite in execution whatever the program is that it is analyzing. You can't 'blame' H_Hat for needing to be aborted, when the actual fault was in you simulator. Note, that your detrmination of 'Halting' is spurious, because it is a function of what H did, and just shows a limitation of your chosen method, By similar argument a poorly designed alternate H might just decide that ALL machines had infinite behavior because H did in analysing it so it aborts all machines. This makes 'Aborted' a meaningless term. Also, I suspect that you are going to have a problem handling a large class of interesting programs which go towards or to infinite execution but never have a repeated state. One example would be a program of the form: define f(i) while true: if p(i) then Halt(i) else i := i+1 where p(i) is some finite executing test on i to determine if it meets some property, and we want to find the first such number at least as large as the input to the machine. p could be a prime test, it could be an impossible test (one that will never be true so it needs to be aborted) or it could be a test that just won't be meet until i gets very big, like is i equal to the factorial of a googleplex. This machine NEVER repeats state, so your design can't determine infinite execution by looking for repeated state. Determining between the last two cases likely exceeds your machines capability, or your patience. This is why 'debug stepping' is NOT really a viable method of determining halting. |
| olcott <NoOne@NoWhere.com>: Oct 27 09:28PM -0500 On 10/27/2020 8:45 PM, Richard Damon wrote: > Except that it DOES get the wrong answer for H_Hat, because H_Hat DOES > halt, at least if H give the answer that it aborted and H meets the > requirements of a decider to be always finite in execution. 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 } 01 int main() 02 { 03 u32 M = (u32)H_Hat; 04 H_Hat(M); 05 HALT 06 } This line of H_Hat: if (Aborted_Because_Non_Halting_Behavior_Detected(M, M)) invokes this function call Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat). The above function call returns true because its first H_Hat parameter must be aborted on its input (the second H_Hat parameter). bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) can never ever be shown to decide its input incorrectly. Line 04 of main: H_Hat(M); IS NOT INPUT TO bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 27 09:55PM -0500 On 10/27/2020 9:48 PM, Richard Damon wrote: >> bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) > H_Hat, the machine running, did NOT have infinite execution, therefore > if H properly followed it through, it would have seen that it stopped. No that is not true. I thought that might be true too the first time that I analyzed this months ago. It turns out that unless H_Hat is aborted it really never does stop running. If we simply wait and see what H_Hat does it never ever stops running. > implementation of your halt detector, it is NOT inevitable and in fact > your design can't handle a lot of machines that are interesting, because > they may execute infinitely without every repeating a state. There is not any input that can be shown to cause: bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) to decide its input incorrectly. I have already thought these things all the way through. -- Copyright 2020 Pete Olcott |
| "André G. Isaak" <agisaak@gm.invalid>: Oct 27 10:49PM -0600 On 2020-10-27 15:23, olcott wrote: >> decider at all. > The above two sets are the exact same sets that a correct halt decider > would decide. In that case, can you answer the following two extremely simple questions which I asked in a previous post but which you did not answer 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? André -- To email remove 'invalid' & replace 'gm' with well known Google mail service. |
| olcott <NoOne@NoWhere.com>: Oct 28 12:05AM -0500 On 10/27/2020 11:49 PM, André G. Isaak wrote: > (1) Your ABNHBD contained in H? > (2) Your ABNHBD contained in the outermost instance of H_Hat? > André bool Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) always returns true in the outermost instance of its recursive invocation. It does that because that is the only correct return value for its input. It always decides its input correctly and there is no input that can be shown that it decides incorrectly. Can you see how this completely answers your question? -- Copyright 2020 Pete Olcott |
| "André G. Isaak" <agisaak@gm.invalid>: Oct 27 11:25PM -0600 On 2020-10-27 23:05, olcott wrote: >> André > bool Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) > always returns true in the outermost instance of its recursive invocation. So the answer to (2) is that it returns ABORTED. That doesn't answer my question (1). What does your ABNHBD in H return? André -- To email remove 'invalid' & replace 'gm' with well known Google mail service. |
| olcott <NoOne@NoWhere.com>: Oct 28 12:31AM -0500 On 10/28/2020 12:25 AM, André G. Isaak wrote: >> invocation. > So the answer to (2) is that it returns ABORTED. > That doesn't answer my question (1). What does your ABNHBD in H return? bool Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) always returns true in the outermost instance of its recursive invocation. Do you think that always means once in a while? -- Copyright 2020 Pete Olcott |
| "André G. Isaak" <agisaak@gm.invalid>: Oct 27 11:55PM -0600 On 2020-10-27 23:31, olcott wrote: > always returns true in the outermost instance of its recursive > invocation. > Do you think that always means once in a while? If the ABNHBD invoked in the outermost H_Hat returns ABORTED, that means the outmost H_Hat does indeed halt, so if the ABNHBD invoked in H returns ABORTED then it is getting the wrong answer! André -- To email remove 'invalid' & replace 'gm' with well known Google mail service. |
| Richard Damon <Richard@Damon-Family.org>: Oct 28 09:04AM -0400 On 10/27/20 10:55 PM, olcott wrote: > that I analyzed this months ago. It turns out that unless H_Hat is > aborted it really never does stop running. If we simply wait and see > what H_Hat does it never ever stops running. And that is the problem with your H, not with H_Hat. H, by definition, must have finite execution. If we can supply H with some input which it can't determine the right answer with finite execution, then H is NOT a proper halting determinater. Your 'abort' result is really, at least sometimes, an 'I don't know' answer, you haven't proven that the supplied program will never halt (because you haven't seen repeated state) or seen that it halted (which makes the answer easy) so it punts and just aborts and makes a bold statement, that can be wrong. It is theroretically possible, within the definition of H, that all H is is a finite regex on the input machine, or some magic hash. None of these can possibly have this infinite recursion issue, so H can't 'blame' the recursion on H_Hat, so can't claim that H_Hat 'was aborted'. Again part of the issue is you want to change the question, but if you do, you can't apply your results to the original question. The ONLY question of a Halt Decider is that H(M,N) will indicate in finite time, what will happen if we run M(N). It doesn't matter if H(M,N) releases the 7 plagues, if running M(N) doesn't, then that is not part of the answer. It is clear, that from the answer you say H(H_Hat, H_Hat) will produce, that is 'Will Not Halt' (that you call 'Aborted') that when you apply that to the run of H_Hat(H_Hat), and that machine terminates in finite time, the H(H_Hat, H_Hat) got the answer wrong. The question is NOT about what happened to the emulated M(N), because the problem doesn't assume emulation (in fact it can be shown that emulation can't be a universal solution), but what would happen to a REAL M(N) run. It is like disproving that you can't trisect an arbitrary angle with compass and straight edge, by saying you can if the angle happens to be a right angle. Different Question, different results. The original, classical, halting problem statement has useful implication in the theory of Mathematics and Logic. Your modified question, I don't know of a use. Yes, you can disproof Linz, if you change to domain that you are applying Linz to. It has LONG been know that if you don't need to be a UNIVERSAL halt determinater, that there are a number of classes a Turing machines that you can determine if they will halt or not. The key here is that they can't handle any arbitrary Turing Machine. In particular, the easiest case is for machines that stay bounded over there full execution of the problem. It is the unboundedness that causes the problems, and is where you seem to have the issues, and where other aspects you have problems with, like incompleteness, come in. |
| Mostowski Collapse <janburse@fastmail.fm>: Oct 28 02:13PM +0100 In what parallel universum does your nonsense have anything to do with Prolog? You fucking moron spammer Richard Damon? No need to post responses on comp.lang.prolog. Richard Damon schrieb: |
| Mostowski Collapse <janburse@fastmail.fm>: Oct 28 02:13PM +0100 In what parallel universum does your nonsense have anything to do with Prolog? You fucking moron spammer Richard Damon? No need to post responses on comp.lang.prolog. Richard Damon schrieb: |
| David Brown <david.brown@hesbynett.no>: Oct 28 03:12PM +0100 On 28/10/2020 14:13, Mostowski Collapse wrote: > No need to post responses on comp.lang.prolog. > Richard Damon schrieb: >> bla bla not a bit of Prolog bla bla Even better - would all the sane people in these pointless "olcott" threads /please/ remove the language groups from the replies? They are not remotely relevant or on-topic for C, C++ or Prolog. I don't think they are of much interest for theoretical computation either, but as I don't follow comp.theory, I can't be sure. We all know that this "Olcott" person is a manic poster and can't be stopped. But Richard Damon, and some of the others in these threads, is a reasonable person. If you folks want to discuss Olcott's ideas, make sure you remove all non-relevant newsgroups from the posts and follow-ups. And if he insists on putting them back in, then please boycott him altogether. |
| olcott <NoOne@NoWhere.com>: Oct 28 05:50PM -0500 On 10/28/2020 12:55 AM, André G. Isaak wrote: > the outmost H_Hat does indeed halt, so if the ABNHBD invoked in H > returns ABORTED then it is getting the wrong answer! > André bool Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat); Never decides its input incorrectly. No dishonest dodge will show this. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 28 05:54PM -0500 On 10/28/2020 4:38 AM, Alan Mackenzie wrote: >> input has already halted. > That leaves, of course, the cases where the function never returns, > neither halting nor detecting "non-halting behaviour". bool Aborted_Because_Non_Halting_Behavior_Detected(u32 N, u32 M) It cannot be shown that it ever decides its input incorrectly. Furthermore although very complex examples can be provided, none of these examples can be shown to be undecidable. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 28 06:18PM -0500 On 10/28/2020 8:04 AM, Richard Damon wrote: > haven't seen repeated state) or seen that it halted (which makes the > answer easy) so it punts and just aborts and makes a bold statement, > that can be wrong. I did not answer these posts this morning so that I could work on providing the example program. bool Aborted_Because_Non_Halting_Behavior_Detected(u32 M, u32 M). There is no input that can be proved to be undecidable for the above function. > is a finite regex on the input machine, or some magic hash. None of > these can possibly have this infinite recursion issue, so H can't > 'blame' the recursion on H_Hat, so can't claim that H_Hat 'was aborted'. I have defined a Non_Halting decider that has no input that can be shown to be undecidable. It is possible to define this differently so that it is no longer a decider for all of its input. This of course would form no rebuttal of my definition at all. > question of a Halt Decider is that H(M,N) will indicate in finite time, > what will happen if we run M(N). It doesn't matter if H(M,N) releases > the 7 plagues, if running M(N) doesn't, then that is not part of the answer. I think that the only way that I changed the question is that the halt decider became a non-halting decider. It Accepts non-halting programs and Rejects halting programs. > that is 'Will Not Halt' (that you call 'Aborted') that when you apply > that to the run of H_Hat(H_Hat), and that machine terminates in finite > time, the H(H_Hat, H_Hat) got the answer wrong. You may not be able to understand that my analysis is correct until I have fully operational code. I worked on this all day. > the problem doesn't assume emulation (in fact it can be shown that > emulation can't be a universal solution), but what would happen to a > REAL M(N) run. You may not be able to understand that my analysis is correct until I have fully operational code. I worked on this all day. This function can not be shown to have any undecidable inputs: bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I) int main() { H_Hat(H_Hat); } Would never terminate unless this function aborts it input: Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) > The original, classical, halting problem statement has useful > implication in the theory of Mathematics and Logic. Your modified > question, I don't know of a use. I defined a NON_HALT decider that always Accepts its input if its input would not halt and Rejects its input if its input would halt. > execution of the problem. It is the unboundedness that causes the > problems, and is where you seem to have the issues, and where other > aspects you have problems with, like incompleteness, come in. I defined a NON_HALTING decider that always Accepts NON_HALTING input and Rejects HALTING input. -- Copyright 2020 Pete Olcott |
| Bonita Montero <Bonita.Montero@gmail.com>: Oct 28 08:10PM +0100 Advocating for either style is stupid. Programmers should be able to read both styles as both are easy to read. But programmers are often compulsive and irrational. |
| Frederick Gotham <cauldwell.thomas@gmail.com>: Oct 28 06:18AM -0700 On Tuesday, October 27, 2020 at 3:42:06 PM UTC, Kenny McCormack wrote: > Why don't you? > Why not go all the way? No point because DOS 6.22 doesn't have "findstr" which I need for extracting the Microsoft exectuable file from my fat binary. If I can come up with another clever way of extracting the Microsoft binary that doesn't involve 'findstr', then yeah it would be worth putting a 16-Bit DOS version in there too. |
| 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