A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 20 Oct 2006 08:46 <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!!! > 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... > > -- > > Steve Stringer > sillybanter(a)gmail.com >
From: Patricia Shanahan on 20 Oct 2006 08:57 Peter Olcott wrote: > "Patricia Shanahan" <pats(a)acm.org> wrote in message .... > I will only proceed beyond this example, iff you agree that I have made my point > with this example. Bye.
From: Aatu Koskensilta on 20 Oct 2006 09:03 Peter Olcott wrote: > 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 Too bad for WillHalt, then. The program still either halts or does not halt given the input. > 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!!! Yep, it might be that WillHalt could answer "Well, this question is posed so that I can't possibly answer it correctly", but then it would have to use some algorithm to decide which program-input pairs constitute ill-formed questions. What is your proposed algorithm for doing so? For example, is the following question ill-formed: Does the program P halt with input 0? where P is a program executing the following algorithm 1. n := 4 2. if n isn't a sum of two primes, go into an endless loop if WillHalt("P",0) returns true and otherwise print "neener-neener" 3. n := n+2 4. Go to step 2 What is the algorithm WillHalt uses to determine whether this is an ill-formed question or not? -- Aatu Koskensilta (aatu.koskensilta(a)xortec.fi) "Wovon man nicht sprechen kann, daruber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Peter Olcott on 20 Oct 2006 09:26 <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. > 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!!! > > -- > > Steve Stringer > sillybanter(a)gmail.com >
From: Peter Olcott on 20 Oct 2006 09:27
<sillybanter(a)gmail.com> wrote in message news:nGYZg.3795$4T6.1868(a)trnddc02... > In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: >> >> <sillybanter(a)gmail.com> wrote in message news:SrLZg.5348$NK5.2906(a)trnddc08... >> > In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: >> > >> >> That seems to be a very precise English language statement that is >> >> most typically used to describe the results of the HP. It is this >> >> statement that I refute. I may be wrong, I have been wrong before, >> >> but, it is still this specific statement that I refute. The HP can >> >> be decided, yet the answer can not be restricted to YES or NO >> >> because the question is not a YES or NO question. >> > >> > There are certainly problems that are ill-formed, but the halting >> > problem is not one of those. Deal with the real form of the halting > >> I think that I have shown in my prior response to you at least one >> example of a halting problem, that is only a problem because it is >> ill formed. > > No, you certainly haven't. The halting problem is not ill-formed, and > has a well-defined answer for each and every input. Including the one > that you think, for some reason, doesn't have a yes or no answer. > >> Iff (if and only if) I can reach a consensus on this >> point, I will proceed to a UTM version of the same problem, and >> attempt to show the mathematical mapping from the prior example to >> the UTM example. I will not do this unless or until I have reached a >> consensus on my prior point. > > You will not get consensus on this point, because you're wrong, and > pretty much everyone here except you sees that quite clearly. > > -- > > Steve Stringer > sillybanter(a)gmail.com > Or, pretty much everyone here does not 100% completely grasp every subtle nuance of the complete meaning of my statements. |