A Possible "solution" to the Halting Problem
in [Theory]
|
From: Jens Auer on 23 Oct 2006 12:11 Peter Olcott schrieb: >> There is a function called >> DetectedSelfReferenceTogglesTheReturnValue(SourceCode, >> InputData). After finding the self-reference (which is IMHO undecidable as >> well), it has to check the expression after the self-reference if it is the >> opposite of the WillHalt(s,s) expression. In other words, >> DetectedSelfReferenceTogglesTheReturnValue(SourceCode, >> InputData) has to determine the halting value of the expression following the >> condition, in the LoopIfHalts example this would be while(TRUE); this is a >> circular definition. > > It is not a circular definition, it is a stub for details left out. It doesn't matter how you actually define this stub. To give the correct answer, you first have to check if an expression f(s,s) == TRUE is equivalent to WillHalt(s,s) == TRUE. Ups, you first need to see if f(s,s) halts => first circle. If the condition is TRUE, you have to check if the expression in the then-statement does not halt. Ups, second circle.
From: Jens Auer on 23 Oct 2006 12:21 Peter Olcott schrieb: > "Jens Auer" <jens.auer-news(a)betaversion.net> wrote in message > news:453c5c09(a)news.ish.de... >> Peter Olcott wrote: >>> What is the result of MalignantSelfReference(g,g) FALSE >>> what is the result of WillHalt(g, g) TRUE >>> >>> WillHalt(), LoopIfHalts() and g() all have different execution traces. >> Then MalignantSelfReference(g,g) can see that f is different from WillHalt, in >> other words it shows that f is not equivalent to WillHalt. This is not >> possible in general because it involves, as Patricia notes, solving the >> halting problem. For computing MalignantSelfReference(g,g), you need to solve >> the halting problem for g, but MalignantSelfReference(g,g) is itself part of >> your halting problem solver. Do you see the problem? > > Rice's theorem? A possible practical way around the results of this theorem > would be to constrain the means of specifying algorithms to some form of > well-ordered set where Rice's theorem would not apply. I don't know what you mean by "constrain the means of specifying algorithms to some form of well-ordered set", but you cannot change the rules of game as you need. The Halting Problem is defined on Turing Machines, so you must cope with either TMs or some equivalent form. And the problem is not Rice's theorem but the circular dependance of WillHalt and SMR as you defined them. > In this case one could not only possibly achieve a universal halt detector that > works correctly on every program that adheres to the required specification > conventions, but, further still an automatic logical validator. In any case my > original point still applies. You do know that first-order predicate logic itself is undecidable? Or this another sort of an ill-formed question, to ask whether a logic statement in first-order predicate logic is true or not? > The classical form of the Halting Problem still > seems to be more accurately construed as an ill-formed question, rather than an > undecidable problem. It is undecidable in the sense that decision problems are defined in CS. If you want to define this in any other way, go on but please don't call it Halting Problem and use another word than decision problem. The only ill-formedness is that the problem cannot be solved in general. Sad enough, but perfectly valid and provably correct. To show that the general prove is not correct, you must find an error in the reasoning. Than, you can try to show a computable function with which solves the halting problem for TMs.
From: Peter Olcott on 23 Oct 2006 13:32 "Jens Auer" <jens.auer-news(a)betaversion.net> wrote in message news:ehipim$10di$1(a)f1node01.rhrz.uni-bonn.de... > Peter Olcott schrieb: > >>> There is a function called >>> DetectedSelfReferenceTogglesTheReturnValue(SourceCode, >>> InputData). After finding the self-reference (which is IMHO undecidable as >>> well), it has to check the expression after the self-reference if it is the >>> opposite of the WillHalt(s,s) expression. In other words, >>> DetectedSelfReferenceTogglesTheReturnValue(SourceCode, >>> InputData) has to determine the halting value of the expression following >>> the condition, in the LoopIfHalts example this would be while(TRUE); this is >>> a circular definition. >> >> It is not a circular definition, it is a stub for details left out. > It doesn't matter how you actually define this stub. To give the correct > answer, you first have to check if an expression f(s,s) == TRUE is equivalent > to WillHalt(s,s) == TRUE. Ups, you first need to see if f(s,s) halts => first > circle. > If the condition is TRUE, you have to check if the expression in the > then-statement does not halt. Ups, second circle. I have updated my position to clarify it and correct any inconsistencies. My updated position is as follows: The question posed to the TM is: "Does the program halt { State(HALTS) or State(NOT_HALTS) }?" is an ill-formed question because the TM is constrained to provide its response from a solution set that contains no correct answer. Thus the Halting Problem meets the definition of an ill-formed question. The Halting Problem is only undecidable because it has the same form as the question" "How tall are you green or blue?" It was the recent dialogue with Daryl, that enabled me to correct the inconsistencies and ambiguities with my prior position. Thanks Daryl!
From: Chris Menzel on 23 Oct 2006 15:22 On Mon, 23 Oct 2006 18:21:02 +0200, Jens Auer <jens.auer-news(a)betaversion.net> said: > Peter Olcott schrieb: >> In this case one could not only possibly achieve a universal halt >> detector that works correctly on every program that adheres to the >> required specification conventions, but, further still an automatic >> logical validator. In any case my original point still applies. > > You do know that first-order predicate logic itself is undecidable? Of course he doesn't. > Or this another sort of an ill-formed question, For him, no doubt. > to ask whether a logic statement in first-order predicate logic is > true or not? You mean "valid", of course. >> The classical form of the Halting Problem still seems to be more >> accurately construed as an ill-formed question, rather than an >> undecidable problem. > It is undecidable in the sense that decision problems are defined in CS. > If you want to define this in any other way, go on but please don't call > it Halting Problem and use another word than decision problem. The only > ill-formedness is that the problem cannot be solved in general. In other words, it is not ill-formed at all. ;-)
From: Daryl McCullough on 23 Oct 2006 15:44
Peter Olcott says... >The question posed to the TM is: "Does the program halt { State(HALTS) or >State(NOT_HALTS) }?" No, the question is just "Does program P halt on input X?". If you are the one who is writing WillHalt, you get to decide what it means for WillHalt to have figured out that the answer is "yes", and you get to decide what it means for WillHalt to have figured out that the answer is "no". -- Daryl McCullough Ithaca, NY |