A Possible "solution" to the Halting Problem
in [Theory]
|
From: Daryl McCullough on 19 Oct 2006 23:45 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. -- Daryl McCullough Ithaca, NY
From: Daryl McCullough on 19 Oct 2006 23:49 Peter Olcott says... >"Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote >> As you described it, LoopIfHalts *halts* (after >> raising an exception) if given its own source code as input. >> So the correct answer to the question is: Yes, LoopIfHalts >> halts when given its own source code as input. >> >> The answer is "true". It's *always* true. There is nothing >> ill-defined about the question. It's just that WillHalts >> fails to give the correct answer. > >Yet again you fail to get the precise context correctly, >(don't feel bad most everyone had made this same mistake >for many decades). I don't feel bad, it's just that what you are saying is wrong. >The correct answer to the question, also depends on the context >of whom is being asked. No, it does not. >When you are asked the question there is a different correct >answer than when WillHalt() is asked this same question. No, there is not. >If I ask you the name of your wife, I get one answer, >if I ask your wife the exact same question, "What is >the name of your wife?" I get a different answer. >Context is everything. Yes, there are questions whose answer depends on the context, but the halting problem is not one of them. -- Daryl McCullough Ithaca, NY
From: sillybanter on 20 Oct 2006 00:54 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... -- Steve Stringer sillybanter(a)gmail.com
From: sillybanter on 20 Oct 2006 00:56 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
From: Ben Bacarisse on 20 Oct 2006 01:20
"Peter Olcott" <NoSpam(a)SeeScreen.com> writes: > It is equivalent to saying that no correct answer exists to the > question, "How tall are you green or blue?" because the question > itself is ill-formed. It is not at all equivalent to I_GIVE_UP. You have not been able to say exactly when a question is ill-formed, and you are very worried about what you see as "malignant self-reference", but the HP comes in many disguises. As a programmer you will be very familiar with context-free grammars. CFGs are used to describe the syntax of all sorts of programming languages: a finite set of clauses describe how, starting from an initial clause, sequences of strings drawn from the grammar's "terminal alphabet" can be generated. Given the simple alphabet S = {0, 1} this grammar: E -> D E | /\ D -> 0 | 1 has the rather boring property that is can generate all strings of 0s and 1s. We say the language of the grammar L(E) = S* (the set of all string made from the symbols in S). I am using /\ to mean the empty string (since it shows up better) and | to show alternatives in rules. The grammar: X -> D X | 1 D -> 0 | 1 does not generate all string because every string in L(X) ends with a 1. It seems to me a simple and well-formed question to ask of a grammar, G, if L(G) = S* and, more specifically, to imagine a program bool generates_all_binary_strings(grammar g) { if (<have a really good look at g and if it does>) return true; else return false } This problem is equivalent to the Halting Problem so the The Halting Theorem tells me that no such program exists, but where is the ill-formedness of the question and where is the malignancy? [Aside. I don't really expect you to be convinced by this. In fact I expect you to say "since I've solved the HP this one is solvable too!". But since you have resolutely refused to say what kind of thing might shake you resolve, I thought I'd try this take -- a simple, easy to understand problem that is just as "nasty" as the HP.] -- Ben. |