A Possible "solution" to the Halting Problem
in [Theory]
|
From: Jens Auer on 20 Oct 2006 09:44 Peter Olcott schrieb: > It does get the right answer!!! It simply can not provide the results of its > correct and complete decision to a caller that toggles the result of this return > value. I will say it again, most everyone have missed this point: IT DOES GET > THE RIGHT ANSWER!!! How do check for this? Do you just search for the string "WillHalt" with needed parameters?
From: Daryl McCullough on 20 Oct 2006 09:59 Peter Olcott says... >"Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote >> Yes, there are questions whose answer depends on the >> context, but the halting problem is not one of them. > >Merely an empty unsupported statement. No, it's a provably correct statement. >I have proven my point, No, you haven't. -- Daryl McCullough Ithaca, NY
From: Daryl McCullough on 20 Oct 2006 10:02 Peter Olcott says... >>>"Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote >> >>>> If a program is deterministic, then whether >>>> it halts or not is a meaningful question. The fact that WillHalt >>>> is unable to correctly answer question doesn't make the question >>>> ill-formed. >>> >>>In the specific instance of WillHalt() indeed it does. >> >> No, it doesn't. >I have proven that it does No, you haven't. The way you described it, WillHalt will throw a "MalignantSelfReferenceException", which is not correctly answering the question. -- Daryl McCullough Ithaca, NY
From: sillybanter on 20 Oct 2006 11:10 In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: > <sillybanter(a)gmail.com> wrote in message news:TDYZg.3794$4T6.1422(a)trnddc02... > > In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: > >> > >> <sillybanter(a)gmail.com> wrote in message news:bnLZg.5347$NK5.1822(a)trnddc08... > >> > In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: > >> > > >> >> So the equivalent of the return value of the Halt() function from > >> >> the TM is the integer value that the TM's ReadWrite head rests on > >> >> when the TM halts. In this case DOES_NOT_HALT=0 HALTS=1 > >> >> MALIGNANT_SELF_REFERENCE=2. This scenario breaks out of the infinite > >> >> recursion of the original specification of the problem, and provides > >> >> the only possible correct answer. > >> > > >> > In the standard presentation of the halting problem, there is no > >> > recursion, infinite or otherwise. Don't be confused by the fact that > >> > the same name of a function is used in the analyzed program and in the > >> > analyzer - it's not the same thing, and these two instances of > >> > "Halt" are completely separate. > >> > >> See the ANALYTICAL COMMENTARY of this example mentioned below to see my > >> current > >> point. > > > >> ... > > > >> // ANALYTICAL COMMENTARY > >> WillHalt() is provided with the source code of LoopIfHalts(), as > >> input, so WillHalt() can see exactly how the return value of the > >> invocation of itself under test will be used to toggle the result > >> of the analysis of the invocation of itself under test. WillHalt() > >> can see that LoopIfHalts() is toggling the result of the invocation > >> of itself under test to invalidate the analysis of the invocation > >> of itself under test. > >> > >> Therefore WillHalt() can determine that the question: > >> "Does LoopIfHalts(LoopIfHalts) halt?" has no correct YES or NO > >> answer, and is thus erroneously formed because it is asking a > >> YES or NO question that has no correct YES or NO answer. > > > > Except that it, of course, DOES have a correct YES or NO answer. > So which of the correct YES or NO answers can WillHalt() provide > such that it has provided the correct YES or NO answer? If you are > correct, then you MUST be able to correctly select one of these, > otherwise YOU ARE INCORRECT!!! THERE EXISTS NO CORRECT YES OR NO > ANSWER THAT WillHalt() CAN POSSIBLY PROVIDE, THUS THIS HALTING > PROBLEM IS MERELY THE CASE OF THE INABILITY TO CORRECTLY ANSWER AN > ILL-FORMED QUESTION ENTIRELY DUE TO THE FACT THAT THE QUESTION > ITSELF IS ILL-FORMED!!! If you really think about what you yourself just wrote there, you would see that you've exactly described the contradiction that is the heart of the halting problem proof, and hence you have proved that the halting problem is undecidable. Let me try to point this out as clearly as I can - you say "which of the correct YES or NO answers can WillHalt() provide such that it has provided the correct YES or NO answer?" The answer is NEITHER. That doesn't mean that the answer doesn't exist just that this particular algorithm (WillHalt) is wrong. That WillHalt doesn't "provide the correct YES or NO answer" in no way, shape, or form implies that the answer doesn't exist - just that this particular algorithm can't determine it. You say "THERE EXISTS NO CORRECT YES OR NO ANSWER THAT WillHalt() CAN POSSIBLY PROVIDE" - you're absolutely correct that WillHalt will never, ever provide the correct input on this particular input. So what? *Other* algorithms could take this exact same input (with the WillHalt source code) and PROVIDE THE CORRECT ANSWER (we're typing in all caps now I see). But they'll give the wrong answer on *other* inputs. Here's another attempt at explaining it: we agree that WillHalt doesn't return the right YES or NO answer. There are really only two possibilities: 1) The problem is ill-formed and there is no correct answer. 2) The problem is well-formed and WillHalt is wrong. The reason WillHalt fails is precisly because of #2. You argue that the problem is ill-formed *because* WillHalt fails - that's a completely bogus argument because of the (correct) possibility of #2. If the problem is ill-formed, then you should be able to describe why that is so, without talking about how one particular algorithm behaves. That algorithm not behaving well on a particular input just means that the algorithm is wrong on that input. Other algorithms are correct on that input, and so the problem is not ill-formed. So here's your specific challenge: try to argue that the problem is ill-formed without relying on how one particular algorithm behaves on one particular input, because that's falacious reasoning. -- Steve Stringer sillybanter(a)gmail.com
From: sillybanter on 20 Oct 2006 11:14
In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: > <sillybanter(a)gmail.com> wrote in message news:TDYZg.3794$4T6.1422(a)trnddc02... > > Except that it, of course, DOES have a correct YES or NO answer. > > LoopIfHalts(LoopIfHalts) absolutely either halts in a finite number of > > steps or it doesn't. It's that simple. The fact that "WillHalt" > > can't correctly determine which of these is the correct answer is > > irrelevant to whether the answer exists or not. > > > > So the problem is not ill-formed, but WillHalt doesn't get the right > > answer. That's the whole point, you know... > It does get the right answer!!! It simply can not provide the > results of its correct and complete decision to a caller that > toggles the result of this return value. I will say it again, most > everyone have missed this point: IT DOES GET THE RIGHT ANSWER!!! It does not get the correct YES or NO answer, which you have acknowledged in other posts. It gives a cop-out "None of the above" answer - it may be correct that the algorithm doesn't know the answer, but there *is* a correct YES or NO answer that it does *not* get. -- Steve Stringer sillybanter(a)gmail.com |