A Possible "solution" to the Halting Problem
in [Theory]
|
From: Dr A. N. Walker on 19 Oct 2006 11:57 In article <o_JZg.31120$eZ4.25272(a)dukeread06>, Peter Olcott <NoSpam(a)SeeScreen.com> wrote: >"Patricia Shanahan" <pats(a)acm.org> wrote in message >news:ueDZg.11396$Y24.6326(a)newsread4.news.pas.earthlink.net... >> [...] >So you agree that my example shows that within the specific context of this >example I have shown that this specific form of a Halting Problem is merely the >ill-formed question of: >"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. I don't know what PatS may or may not agree with, but *I* don't agree. It isn't that the question is ill-formed, or has no correct YES or NO answer, but rather that we can't tell you *which* is the correct answer until *after* you show us the code. The proof shows that there is no *correct* HP solver, and thus your "LoopIfHalts" code is built from a program that doesn't work. Once you either tell us from your own analysis why your "Halt" code doesn't work [and "LoopIfHalts" will give you a specific non-working instance for you to look at], or show us the code so that we can look for ourselves, *then* we can work out what the halting status of "LoopIfHalts(LoopIfHalts)" is. You can't reasonably expect us to do that with no knowledge of what the secret "Halt" subroutine within "LoopIfHalts" really does, only that it doesn't do what it is claimed to do. -- Andy Walker, School of MathSci., Univ. of Nott'm, UK. anw(a)maths.nott.ac.uk
From: Patricia Shanahan on 19 Oct 2006 12:29 Peter Olcott wrote: > "Patricia Shanahan" <pats(a)acm.org> wrote in message > news:ueDZg.11396$Y24.6326(a)newsread4.news.pas.earthlink.net... >> Peter Olcott wrote: >> ... >>> I can do as others have done and complicate the problem beyond all possible >>> recognition. Instead I chose to boil the problem down to its most fundamental >>> essence. Try to address the problem as I have framed it, and refrain from >>> attempts to change this framework. The ability to complicate the example so >>> that no one can understand it, is not a valid form of refutation. >>> >>> Within the exact and precise framework that I have defined the Halting >>> Problem, is it now clear, that at least within the context of this framework >>> 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. >> ... >> >> If you are defining your own problem, you can solve it any way you like, >> but please don't call it "the Halting Problem" unless you really do mean >> a decision procedure for the set of terminating Turing machine computations. >> >>> Maybe it might help if you don't begin your response starting with the goal >>> of refutation? >> It would not help at all with testing the validity of your ideas, which >> is my objective. >> >> If you are trying to test a program, do you feed it only the easy cases, >> or do you feed it deliberately difficult cases, such as the largest and >> smallest permitted inputs? >> >> Patricia > > So you agree that my example shows that within the specific context of this > example I have shown that this specific form of a Halting Problem is merely the > ill-formed question of: > "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. > > If you agree with this please say so, if you don't agree with this then please > explain why you do not agree. I strongly disagree with any idea of using the term "halting problem" for this, because the Halting Problem is a decision problem. It asks whether its input is, or is not, a member of a specific language, and the only possible answers are to accept or reject the input. Note that the traditional proof shows that self-contradictory programs can be created if you assume the set of Turing machine computations that halt is a decidable language. In my opinion, the only reasonable reaction to the LoopIfHalts behavior is to conclude that there is no decision algorithm for halting TM computations. Once you accept that, LoopIfHalts cannot be written because there is no Halts function for it to call. Instead of working on the decision problem, you seem to be trying to construct a function that maps input strings to "Yes", "No", or "MSR". Whether MSR is the correct output for a specific input depends on exactly how MSR is defined. I cannot comment on which result is the right one for a given program until you define your function. I strongly suspect your function will be either unrelated to the Halting problem or not computable, but I won't know which unless you define it. > > Apparently you do not agree that this example of a Halting Problem > mathematically maps tot he original Halting Problem. I will proceed to this step > only after we have formed agreement on the preceding step. Effective > communication must proceed one step at a time, or it does not work effectively.
From: MoeBlee on 19 Oct 2006 12:35 Peter Olcott wrote: > "MoeBlee" <jazzmobe(a)hotmail.com> wrote in message > news:1161222967.470438.31270(a)m7g2000cwm.googlegroups.com... > > Peter Olcott wrote: > >> it is > >> merely the case that some ill-formed questions have no correct answer. > > > > There is no "ill-formed question" involved in the theorem that, to > > quote a standard textbook, "there exists a Turing machine whose halting > > problem is recursively unsolvable." > > > > It is only unsolvable, because it is ill-formed. One could say that all > ill-formed questions are unsolvable questions, this leaves out a crucial detail. > How tall are you, (blue or green) ? is an unsolvable math problem, more > importantly it is an ill-formed question. There is no question at all in the statement or proof of the theorem. There are no interrogatives in a fully formalized proof of the halting theorem. The interrogatives involved are for the purpose of motivating the mathematics, but are not part of the theorem itself nor its proof. Morevover, there is nothing "ill-formed" in the questions. Either a given Turing machine with an initial state halts or it doesn't, and regarding any Turing machine with an inititial state we can ask whether it halts. > It matters not whether an ill-formed question is posed in natural language or in > the language of mathematical formalism, in either case it is still an ill-formed > question. There are no interrogatives in a fully formalized proof of the unsolvability of the halting problem. MoeBlee
From: The Ghost In The Machine on 19 Oct 2006 13:48 In sci.logic, Patricia Shanahan <pats(a)acm.org> wrote on Thu, 19 Oct 2006 15:42:15 GMT <r1NZg.15912$UG4.2273(a)newsread2.news.pas.earthlink.net>: > The Ghost In The Machine wrote: >> In sci.logic, Patricia Shanahan >> <pats(a)acm.org> >> wrote >> on Wed, 18 Oct 2006 22:22:10 GMT >> <mOxZg.15598$UG4.10415(a)newsread2.news.pas.earthlink.net>: >>> Peter Olcott 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. >>> OK, so now we are down to a well-defined environment. Perhaps >>> you can explain how you define a MALIGNANT_SELF_REFERENCE in a Turing >>> machine computation? >>> >>> Patricia >> >> It can always be true, which leads to a Halt() function >> that always throws an exception. This is a valid if >> pointless solution. > > Whether it is a valid solution depends on the definition of > MALIGNANT_SELF_REFERENCE. If it is just equivalent to the I_GIVE_UP > exception, then always throwing it is valid but pointless. > > To the extent that I've been able to find out its meaning, it seems to > relate to whether the result will be used to control whether the TM > halts or not. That, of course, is a halting problem equivalent test, so > it cannot be implemented. Assuming 'MALIGNANT_SELF_REFERENCE' can be well-defined at all. Given any code sequence, there are a lot of code sequences that do exactly the same sequence of actions (take the original and stick NOPs on the front, if nothing else). Any of these might be used in the implementation of LoopIfHalts(). > > Patricia -- #191, ewill3(a)earthlink.net Murphy was an optimist. -- Posted via a free Usenet account from http://www.teranews.com
From: Charlie-Boo on 19 Oct 2006 15:37
Peter Olcott wrote: > "MoeBlee" <jazzmobe(a)hotmail.com> wrote in message > news:1161210790.800534.60930(a)h48g2000cwc.googlegroups.com... > > Peter Olcott wrote: > >> What is the > >> official precise English language conclusion drawn from the results of the > >> mathematical analysis of the Halting Problem? > > > > Why not start by at least informing yourself of an exact mathematical > > statement of the theorem and its proof? > > > > MoeBlee > > > > That is not within my purpose. My purpose is to show that the Halting Problem is > really nothing more than an ill-formed question. Ill-formed in what sense? The problem is that it is inconsistent - regarding whether a program that runs the program being specified against its input as both program and input, when run against itself halts or not. Results from Mathematical Logic manifest themselves in common programming activities. In this case, it is just a case where the programmer sends the specs back to the applications specialist for fixing due to bad logic in the spec. (I know people don't like the idea that the HP is simply an example of bad specs, but it's true. There is an inconsistency in the spec when you put all of its aspects together. You simply have to look at it as a scientist, rather than becoming emotional and defensive about it.) C-B |