| olcott <NoOne@NoWhere.com>: Oct 22 06:55PM -0500 On 10/22/2020 6:34 PM, Ben Bacarisse wrote: > I'd start by saying that H_Hat neither includes nor makes reference to H > as Linz's H^ does. Yes, I know that H is just a thin shim over > DebugTrace but I am sure you want to get the details right. Linz's H^ is defined as a sequence of two sets of modifications to his H. DebugTrace() contains all of the ⊢* state transtions. > Further questions: is DebugTrace vapourware or do you have it written > and running? The reason for the great delay is that I waited until I got DebugTrace() fully operational before I presented H() and H_Hat(). > It you have it running, can you run DebugTrace(H_Hat, > H_Hat) to get a return value? If not why not? If you can, what is the > return value? It took me a man-year to write my x86utm operating system. Now I finally have the full basis to write the most robust halt deciding code. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 22 07:09PM -0500 On 10/22/2020 6:51 PM, Ben Bacarisse wrote: > Ha! You are using the fact that you are wrong now (no one will agree to > this new claim) to prevent you posting the code that would prove you > right! If it weren't all a big con, it would be logic comedy gold. Maybe you don't really understand this stuff very well after all. A person that memorizes these sort of things purely by rote has no depth of understanding. People can very easily directly see that I am correct when they try to show how to make the input program do the opposite of whatever the halt decider decides and find that this is no longer possible. When the halt decider aborts its input program this input program can't do anything because the memory of its process has been released. -- Copyright 2020 Pete Olcott |
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Oct 22 05:21PM -0700 On 10/22/2020 10:19 AM, olcott wrote: > or not changing the question from: > (a) Does the program halt on its input? > (b) Was the program aborted because non-halting behavior was detected? Wait a minute... How is non-halting behavior detected in an unknown function? Lets say an unknown function has been running for 100 years, and still going strong... Would you say it has non-halting behavior? The function could be programmed to self terminate after 409 years... If you said it is non-halting, well, you would be 100% wrong! Although, you "might" be right because the unknown function just might be programmed to run for infinity. It never terminates. So, would your decider have to run infinitely long to tell if the unknown function never terminates? ;^) |
| olcott <NoOne@NoWhere.com>: Oct 22 07:29PM -0500 On 10/22/2020 6:55 PM, Malcolm McLean wrote: > whole thing aborts. If you are running DebugTrace, this isn't a problem - > just shunt the "abortion" condition up the instances. > However a Turing machine can't abort itself. H() executes DebugTrace() that creates a separate virtual machine process and executes H_Hat() that executes DebugTrace() that creates a separate virtual machine process and executes another H_Hat() process. If DebugTrace() returns a value where 1 == Halts and 0 == ~Halts then the conventional self-referential halting problem proof counter-example can be created where H_Hat() does the opposite of whatever H() decides. H() decides Halts so H_Hat Loops H() decides Loops so H_Hat Halts If DebugTrace() returns a value where 1 == Aborted and 0 == ~Aborted then the conventional self-referential halting problem proof counter-example CANNOT be created and H_Hat() CANNOT do the opposite of whatever H() decides. H() decides Aborted so H_Hat has already ceased to exist. H() decides ~Aborted so H_Hat is allowed to execute to completion. There are no longer any halting problem cases that can be shown to be undecidable with the revised definition of the halt decider. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 22 07:40PM -0500 On 10/22/2020 7:21 PM, Chris M. Thomasson wrote: >> (b) Was the program aborted because non-halting behavior was detected? > Wait a minute... How is non-halting behavior detected in an unknown > function? As has already been pointed out this does not make any difference. In the original definition of the halt decider: H() decides Halts so H_Hat Loops H() decides Loops so H_Hat Halts In the revised definition of the halt decider: H() decides Aborted so H_Hat has already ceased to exist. H() decides ~Aborted so H_Hat is allowed to execute to completion. There are no longer any halting problem cases that can be shown to be undecidable with the revised definition of the halt decider > be programmed to run for infinity. It never terminates. So, would your > decider have to run infinitely long to tell if the unknown function > never terminates? ;^) The key case of correctly deciding the Linz H_hat() Bottom of page 319 http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf Is very easy to decide because of a key detail about the halting problem proofs that no one noticed for 80 years. -- Copyright 2020 Pete Olcott |
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Oct 22 05:44PM -0700 On 10/22/2020 5:40 PM, olcott wrote: > In the revised definition of the halt decider: > H() decides Aborted so H_Hat has already ceased to exist. > H() decides ~Aborted so H_Hat is allowed to execute to completion. What happens if the unknown function never completes because it runs forever? |
| olcott <NoOne@NoWhere.com>: Oct 22 07:49PM -0500 On 10/22/2020 7:44 PM, Chris M. Thomasson wrote: >> H() decides ~Aborted so H_Hat is allowed to execute to completion. > What happens if the unknown function never completes because it runs > forever? There may be very complex cases that are very difficult to correctly decide. All that I have shown is that deciding the halting problem is no longer impossible. By showing that deciding the halting problem is no longer impossible I have refuted all of the proofs of its impossibility. -- Copyright 2020 Pete Olcott |
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Oct 22 05:59PM -0700 On 10/22/2020 5:49 PM, olcott wrote: >> forever? > There may be very complex cases that are very difficult to correctly > decide. Indeed. Well, especially if an unknown function never terminates. Or just runs for 1000 years before terminating. > All that I have shown is that deciding the halting problem is no longer > impossible. How? |
| olcott <NoOne@NoWhere.com>: Oct 22 08:15PM -0500 On 10/22/2020 7:59 PM, Chris M. Thomasson wrote: >> decide. > Indeed. Well, especially if an unknown function never terminates. Or > just runs for 1000 years before terminating. The halting problem has never been about an unknown function. A halt decider is not required to be psychic. >> All that I have shown is that deciding the halting problem is no >> longer impossible. > How? The way that the halting problem works is another program that is exactly like that halt decider is slightly changed so that it does the opposite of whatever the halt decider decides. If the halt decide decides that it will halt it loops. If the halt decider decides that it loops it halts. I changed this so that the halt decider executes its input program in DebugStep() mode until it decides that its input would not halt. Then it aborts the execution of its input. Once the execution of the input program has been aborted it can't do anything at all. If it can't do anything at all then it can't do the opposite of whatever the halt decider decides. The aborted input is the programs would never halt unless they are aborted. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 22 08:26PM -0500 On 10/22/2020 8:06 PM, Malcolm McLean wrote: > There are several ways of looking at what you are doing, depending > on the exact details of the "abort" logic. One is to say that the Halt decider > isn't a Turing machine because it can destroy its own execution environment. Think of it in terms of a UTM the simply decides to stop executing its TM. > Then Linz's proof doesn't apply. Another way of looking at it is to say that > you've a hidden parameter (the number of live instances of H_Hat) which > allows you to toggle the behaviour. x86utm execute main() that executes H() that executes DebugTrace() that creates a whole new process that executes H_Hat() in DebugStep() mode that executes DebugTrace() that creates a whole new process that executes H_hat() in DebugStep() mode. Nothing is hidden DebugStep() can see every single detail of every process that it executes and it can store some (or all) of these details to be used later. Since DebugTrace() itself is executed in its own process it can keep the details of its own slave process separate from every other invocation of every other slave process. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 22 09:27PM -0500 On 10/22/2020 8:50 PM, Ben Bacarisse wrote: > doing something incredible! Don't you just wish you really had those > two Turing machines so you could post them and stun your critics? What > a shame you never did. My current claim that I have already provided an unequivocal refutation ALL of the conventional self-referential halting problem proofs and this naturally takes precedence over all of your lesser points above. There is a simple and direct path to a correct rebuttal of my current claim if and only if I am incorrect. The conventional definition of the halt decider can be easily thwarted by making a program based on this halt decider that does the opposite of whatever the halt decider decides. (1) Original self-referential halting problem counter example (a) Decision: ~Halting and Behavior: Halts (a contradiction) (b) Decision: Halting and Behavior: Loops (a contradiction) When the halt decider is a UTM that executes its TM one state transition at a time and ceases executing this TM as soon as it detects non-halting behavior, and then reports that it aborted the execution of this TM it is reporting non-halting behavior that cannot be contradicted. If you can show how its TM can be defined such that its input does the opposite of whatever the halt decider UTM decides then you would have refuted this new position. On the other hand if it is impossible to derive any examples that this redefined halt decider cannot decide, this would prove that I am correct. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 22 11:02PM -0500 On 10/22/2020 10:41 PM, Richard Damon wrote: > some mathematical interesting uses, while your revised statement has > know known use, and without some major tightening of the conditions in > it, is almost assuredly not to be mathematically interesting. When I said that the original proof is correct yet was based on a fundamentally incorrect assumption it is exactly the same thing as the statement that "cats bark" is correct when we assume that all cats are dogs. Perhaps it is easier to understand it when I say that the original proof is fundamentally incorrect because it is based on fundmentally incorrect assumptions. > A big part of this lack of interest is that detecting halting by > simulating adds no information about the halting behavior above simply > running the orginal machine and observing if it has halted. This statement is incorrect. A halt decider can easily detect infinite loops when the program under test is executed in debug step mode. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 22 11:28PM -0500 On 10/22/2020 11:10 PM, Richard Damon wrote: > decider, we could by running the halt decider on the algorithm instead > of just trying to run the algorithm, and thus get the answer of a proof > the existence or non-existence of that result. I can't make out what you are saying. The halting problem proofs are based on making an input that the halt decider cannot possibly decide. The input program is created from the halt decider and made to do the opposite of whatever ht halt decider decides. This fools the halt decider. If the halt decider decides its input will halt the input program loops. If the halt decider decides its input will loop the input program halts. When the halt decider executes its input in debug trace mode (or a UTM executes its TM one state transition at a time). then as soon as it detects non-halting behavior its stops executing its input and reports non-halting behavior. The input program cannot do the opposite of whatever the halt decider decides because the input program cannot do anything at all because it is no longer executing. There is no longer any input that can fool this halt decider therefore the halting problem proofs have been refuted. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 22 11:31PM -0500 On 10/22/2020 11:00 PM, Ben Bacarisse wrote: > H_Hat(H_Hat): > HERE: goto HERE; > Sure looks like H gets the wrong answer to me. The input program is created from the halt decider and made to do the opposite of whatever the halt decider decides. This fools the halt decider. If the halt decider decides its input will halt the input program loops. If the halt decider decides its input will loop the input program halts. When the halt decider executes its input in debug trace mode (or a UTM executes its TM one state transition at a time). then as soon as it detects non-halting behavior its stops executing its input and reports non-halting behavior. The input program cannot do the opposite of whatever the halt decider decides because the input program cannot do anything at all because it is no longer executing. There is no longer any input that can fool this halt decider therefore the halting problem proofs have been refuted. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 23 12:12AM -0500 On 10/22/2020 11:00 PM, Ben Bacarisse wrote: > MOV_EAX_1 // M(N) has terminated > HALT > } Since I strive for complete honestly I do have to say this this is a clear improvement. > HERE: goto HERE; > HALT > } In this one we are losing the transition to (qy) or ((qn)) detail, yet this is an inessential detail and since we are aiming to generalize beyond Linz it is also an improvement. In both cases you removed clumsiness, so good job. > Neither function returns a result they should be "void". Yes I initially tried for a return value but stack unwinding caused an incorrect return value, so right again. > The EAX > settings in H_Hat are a distraction since H_Hat is not supposed to report > anything at all. All that matters is whether is halts or not. Yes good call. > Now, since you refuse to say what DebugTrace(H_Hat, H_Hat) returns (I > don't think you know yet), we need to consider both cases: I have known for 3.5 years. We discussed this at great length yet you were so sure that I must be wrong that you paid no attention at all. > H_Hat(H_Hat): > HERE: goto HERE; > Sure looks like H gets the wrong answer to me. You actually did quite well in analyzing the above except for one very glaring exception. One of the two return values from DebugTrace() is correct. -- Copyright 2020 Pete Olcott |
| Tim Woodall <news001@woodall.me.uk>: Oct 23 07:05AM > This statement is incorrect. A halt decider can easily detect infinite > loops when the program under test is executed in debug step mode. Does the below function g() terminate? N.B. this code is meant to be simple, not efficient. int p(int n) { int p = 0; int d; if(n<=2) return 0; n--; //n is never increased therefore this function always returns a value less than its input d = n; while(d>2) //This loop always terminates as d or n decreases with each iteration and d<=n { d--; p = n; while(p >= d) //This loop always terminates as p decreases with each iteration p -= d; if(!p) { n--; d = n; } } return n; } void g() { int n = 6; int p1 = n; while( p(p1) + p(p1) >=n ) //Does this loop terminate? { p1 = p(p1); //p1 is always less than n int p2 = p1; while(p1 + p2 > n) //p2 monotonically decreases to zero and p1<n therefore this loop always terminates p2 = p(p2); if(p1+p2 == n) { n = n + 2; p1 = n; } } } Does g terminate? (assuming ints never overflow) |
| "André G. Isaak" <agisaak@gm.invalid>: Oct 23 06:29AM -0600 On 2020-10-22 19:15, olcott wrote: >> Indeed. Well, especially if an unknown function never terminates. Or >> just runs for 1000 years before terminating. > The halting problem has never been about an unknown function. The halting asks whether one can create a TM which will determine whether an *arbitrary* TM will halt. I'm pretty sure that is meant above by 'unknown function'. > A halt decider is not required to be psychic. No, but it has to provide the correct answer for any arbitrary TM. > exactly like that halt decider is slightly changed so that it does the > opposite of whatever the halt decider decides. > If the halt decide decides that it will halt it loops. While Linz's proof uses a simple loop in his Ĥ, what is important to the proof is that it enters a series of states which never halts, not that looping is involved. We can easily construct variants of Linz proof in which, in cases where H determines that a TM will halt, Ĥ enters into some arbitrary non-halting computation, like printing all digits of pi, or the sequence of all primes, or the entire fibonacci series, or any other non-halting computation, rather than entering into a simple loop. All of these proofs would be just as valid as Linz's, and your DebugTrace() strategy wouldn't be able to deal with these. André -- To email remove 'invalid' & replace 'gm' with well known Google mail service. |
| olcott <NoOne@NoWhere.com>: Oct 23 08:38AM -0500 On 10/23/2020 2:05 AM, Tim Woodall wrote: > } > } > Does g terminate? (assuming ints never overflow) All that I have done is refuted the conventional self-referential halting problem proofs that show that a universal halt decider is impossible. I don't handle any difficult cases. I only handle the impossible cases. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 23 08:43AM -0500 On 10/23/2020 4:29 AM, Malcolm McLean wrote: > off in some manner. It never runs forever. > So in fact we have a pretty good, though not perfect, halt detector. But > it's not a Turing machine. A Turing machine can't abort. A UTM can run its TM until it decides that its TM is would not halt. Then the UTM stops running its TM and reports non-halting behavior. The TM cannot then do the opposite of whatever the UTM decided because it is no longer running. Bingo halting is decidable ! -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 23 08:45AM -0500 On 10/23/2020 5:02 AM, Ben Bacarisse wrote: > so if you want to be clear (ha!) you should avoid the word or specify > the meaning when you use it as one form of "looping" is easily > detectable but the other is impossible to detect. What form of looping is literally impossible to detect? -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 23 08:57AM -0500 On 10/23/2020 5:47 AM, Malcolm McLean wrote: > No, that's essential to your system. H_Hat aborts, which it achieves by > writing 0 to eax. That's your "abort path",or "exception return" or whatever > you want to call it. No. When DebugTrace() returns 1 it has indicated that the input program has already been terminated. > If H_Hat doesn't abort, then DebugTrace has to abort it. Abort always means terminated by the operating system. > machine or H_Hat isn't a Turing machine, and you've got round Linz. > Linz's proof only applies to Turing machines, and Turing machines can't > abort. The exact same thing applies to UTMs executing UTMs. My whole system models UTMs executing UTMs as much as can possibly be done when we want to keep the algorithms at the high level of abstraction of C. -- Copyright 2020 Pete Olcott |
| olcott <NoOne@NoWhere.com>: Oct 23 09:10AM -0500 On 10/23/2020 7:29 AM, André G. Isaak wrote: > by 'unknown function'. >> A halt decider is not required to be psychic. > No, but it has to provide the correct answer for any arbitrary TM. It always has complete access to the source code so that it can do anything that it wants including execute this code. > non-halting computation, like printing all digits of pi, or the sequence > of all primes, or the entire fibonacci series, or any other non-halting > computation, rather than entering into a simple loop. You are assuming the detecting these cases is impossible. You are assuming that the smartest program in the world would not be able to recognize that another program is calculating the digits of PI. Alternatively I have refuted the conventional self-referential halting problem proof counter-examples that show that a universal halt dedcider is impossible. If there are no other unconventional halting problem proof counter-examples then creating a universal halt decider is no longer shown to be impossble. > All of these proofs would be just as valid as Linz's, and your > DebugTrace() strategy wouldn't be able to deal with these. > André No, not at all, not in the least bit. Providing cases where deciding halting is difficult is not at all the same thing as providing cases where deciding halting is impossible. Even if there are cases where deciding halting is impossible I have still refuted all of the conventional self-referential cases. -- Copyright 2020 Pete Olcott |
| "André G. Isaak" <agisaak@gm.invalid>: Oct 23 08:30AM -0600 On 2020-10-23 08:10, olcott wrote: >> No, but it has to provide the correct answer for any arbitrary TM. > It always has complete access to the source code so that it can do > anything that it wants including execute this code. It can't simply execute the code. If it just executes the code, then the halt decider isn't going to halt when given code that doesn't halt. It has to somehow determine what the code would do if executed. > You are assuming the detecting these cases is impossible. > You are assuming that the smartest program in the world would not be > able to recognize that another program is calculating the digits of PI. Computer programs aren't smart. They have no intelligence whatsoever. Recognizing that some other program calculates the digits of pi is different from determining that whatever an arbitrary function is doing will not halt. > is impossible. If there are no other unconventional halting problem > proof counter-examples then creating a universal halt decider is no > longer shown to be impossble. But the contradiction which Linz's proof makes is still present in yours. Let's assume that H returns 'forced to abort' when applied to Ĥ(Ĥ). That would mean that Ĥ(Ĥ) is stuck in a loop which your H is able to identify. But Ĥ(Ĥ) enters an infinite loop when the underlying decision code determines that Ĥ was *not* forced to abort. So what you claim is the exact same decision code is giving opposite answers when executed inside H than it is when executed inside Ĥ. So either it is giving the wrong answer in H or it is giving the wrong answer in Ĥ. This is the same contradiction present in the Linz proof. André -- To email remove 'invalid' & replace 'gm' with well known Google mail service. |
| olcott <NoOne@NoWhere.com>: Oct 23 09:52AM -0500 On 10/23/2020 9:30 AM, André G. Isaak wrote: > It can't simply execute the code. If it just executes the code, then the > halt decider isn't going to halt when given code that doesn't halt. It > has to somehow determine what the code would do if executed. The UTM executes the code of its input UTM one state transition at a time until it detects that its input UTM would not halt or until its input UTM terminates on its own. As soon as the UTM detects that its input UTM would not otherwise halt it stops executing its input UTM and reports non-halting behavior. >> You are assuming that the smartest program in the world would not be >> able to recognize that another program is calculating the digits of PI. > Computer programs aren't smart. They have no intelligence whatsoever. Deep Blue was a chess-playing computer developed by IBM. It was the first computer to win both a chess game and a chess match against a reigning world champion under regular time controls. https://en.wikipedia.org/wiki/Deep_Blue_(chess_computer) > Recognizing that some other program calculates the digits of pi is > different from determining that whatever an arbitrary function is doing > will not halt. Yes the latter requires much less knowledge. >> problem proof counter-examples then creating a universal halt decider >> is no longer shown to be impossble. > But the contradiction which Linz's proof makes is still present in yours. No it is not and you can continue to say that you really really believe this yet cannot provide an example of this. > identify. > But Ĥ(Ĥ) enters an infinite loop when the underlying decision code > determines that Ĥ was *not* forced to abort. Since my program does not contain the mind of God there will be many cases that it cannot decide correctly. None of these cases are impossible to decide. > answers when executed inside H than it is when executed inside Ĥ. So > either it is giving the wrong answer in H or it is giving the wrong > answer in Ĥ. If we take my redefined halting decider and interpret its return value using the conventional interpretation: DebugTrace() executes H_Hat() and decides that it would not otherwise halt so it terminates the execution of H_Hat() and reports: (1) Not_Halting. Decision:Not_Halting Behavior:Halting a contradiction DebugTrace() got the wrong answer. If we take my redefined halting decider and interpret its return value using the redefined interpretation: (2) Aborted_Because_Non_Halting_Behavior_Detected Decision:Aborted_Because_Non_Halting_Behavior_Detected Behavior:Aborted_Because_Non_Halting_Behavior_Detected Not a contradiction and the right answer! -- Copyright 2020 Pete Olcott |
| "André G. Isaak" <agisaak@gm.invalid>: Oct 23 09:04AM -0600 On 2020-10-23 08:52, olcott wrote: > first computer to win both a chess game and a chess match against a > reigning world champion under regular time controls. > https://en.wikipedia.org/wiki/Deep_Blue_(chess_computer) Deep blue had no intelligence. It used a purely mechanical chess-playing algorithm. > Since my program does not contain the mind of God there will be many > cases that it cannot decide correctly. None of these cases are > impossible to decide. But here I am talking about the sole case that you claim to actually have solved! > using the conventional interpretation: > DebugTrace() executes H_Hat() and decides that it would not otherwise > halt so it terminates the execution of H_Hat() and reports: You keep talking about DebugTrace() without making it clear which instance you are talking about; the one inside H or the one inside Ĥ. Similarly, when you talk about 'behaviour' it isn't clear whether you are talking about H or Ĥ. > Decision:Aborted_Because_Non_Halting_Behavior_Detected > Behavior:Aborted_Because_Non_Halting_Behavior_Detected > Not a contradiction and the right answer! André -- To email remove 'invalid' & replace 'gm' with well known Google mail service. |
| 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