A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 17 Oct 2006 14:36 "Dr A. N. Walker" <anw(a)maths.nott.ac.uk> wrote in message news:eh302u$pvn$1(a)oyez.ccc.nottingham.ac.uk... > In article <Vt5Zg.8306$eZ4.1179(a)dukeread06>, > Peter Olcott <NoSpam(a)SeeScreen.com> wrote: >> [...] If one takes the historical definition of the problem >>artificially constrained to providing a Boolean result, then one can correctly >>conclude that a case can be constructed such that a Halt() function can not >>provide a correct Boolean result. It can not provide a correct Boolean result >>specifically because of the malignant self referential structure of the >>problem. > > It isn't the Halting Problem itself that is "malignant" or "self- > referential", not anyway in its usual formulation or the related proofs. > Rather, it is one *specific* instance of a very similar problem, constructed > so as to "bust" a *specific* purported "Halt()" function. For each potential > "Halt()" function, there exists a corresponding buster; the conclusion is > that no such function can be correct. I thought that the "problem" part of the term "Halting Problem" was directly referring to the existence of this case of malignant self-reference such that it appears to defeat attempts to determine whether or not any program in the set of all programs, halts. > >>The inability to provide a correct Boolean result has been misconstrued to >>mean >>that there are some problems that can never be solved, because there exists a >>case of malignant self-reference where a correct Boolean result can not be >>provided. > > There is no specific instance of the HP that can never be solved, > for an emulator that ran for sufficiently long would solve it; sadly, > "sufficiently long" is not computable by means of a fixed, specific > algorithm [otherwise the HP would be solvable]. Also there is no great > difficulty in providing the correct results for the "buster" instances. > The problem is that the "busted" solver cannot itself do this; and if > you write bigger and better solvers that can, then they in turn have > bigger and better "busters" that they cannot resolve. > > Whether allowing more results is interesting or helpful is quite > another matter. But it is not going to resolve the fundamental problem > underlying the HP -- that there is only a limited amount of information > that a specific program/algorithm [within the limitations of computing > and programming as usually understood] can determine about programs in > general, and that this information cannot reliably include such things > as whether or not the program halts, My primary point is based on the subtle distinction between your precise statement of the conclusions that can be drawn from the HP, and the actual correct conclusions that can actually be drawn. It is apparently a very subtle fallacy of equivocation that people have continued to make for generations. One must treat English as a mathematical formalism to avoid having the next point slip right past the mind's ability to grasp it: The HP does not show any limitation what-so-ever to the capability to determine the halting status of any program. All that the HP shows is that there exists some cases of malignant self-reference where this determination can not be provided as a return value to a caller. > whether control ever passes to line > 123, whether it ever prints "Hello, world!", whether it ever reads from > its input [in the usual, not the Turing Machine, sense], and so on. > > This is quite different from asking about some specific program, > for which these questions [in particular] can all be answered. Indeed, > they can all be answered by a quite simple program. But you may, in > practice, have to wait beyond the heat death of the Universe -- not a > problem for mathematics, only for mathematicians [and other real people]. > > -- > Andy Walker, School of MathSci., Univ. of Nott'm, UK. > anw(a)maths.nott.ac.uk
From: MoeBlee on 17 Oct 2006 17:02 Peter Olcott wrote: > I will frame this in the terms of the Halting Problem because I understand > computer science much more deeply than math. Say what you want about computer science, but the statement of the unsolvability of the halting problem and the proof of the theorem are perfectly formed mathematics; the statement of the theorem and the proof are not "ill-formed" and is not analogous to division by zero, which has to do with conditional definition and descriptions that do not properly refer.. MoeBlee
From: Peter Olcott on 17 Oct 2006 17:23 "MoeBlee" <jazzmobe(a)hotmail.com> wrote in message news:1161118961.027553.142520(a)f16g2000cwb.googlegroups.com... > Peter Olcott wrote: >> I will frame this in the terms of the Halting Problem because I understand >> computer science much more deeply than math. > > Say what you want about computer science, but the statement of the > unsolvability of the halting problem and the proof of the theorem are > perfectly formed mathematics; the statement of the theorem and the > proof are not "ill-formed" and is not analogous to division by zero, > which has to do with conditional definition and descriptions that do > not properly refer.. > > MoeBlee > The conclusion that a universal halt detector can not be constructed is incorrect. The proofs do not show that a universal halt-detector can not be constructed. The proofs only show that a universal halt-detector can not provide the results of its analysis in the case of malignant self-reference where the caller uses the results to change the outcome of the analysis.
From: MoeBlee on 17 Oct 2006 19:00 Peter Olcott wrote: > The conclusion that a universal halt detector can not be constructed is > incorrect. The proofs do not show that a universal halt-detector can not be > constructed. The proofs only show that a universal halt-detector can not provide > the results of its analysis in the case of malignant self-reference where the > caller uses the results to change the outcome of the analysis. The proof is of a mathematical theorem. Whatever that has to do with a "universal halt detector", I'll leave you to you. Meanwhile, "malignant self-reference" has nothing to do with the mathematical theorem and proof. MoeBlee
From: Peter Olcott on 17 Oct 2006 19:09
"MoeBlee" <jazzmobe(a)hotmail.com> wrote in message news:1161126035.398008.237140(a)i3g2000cwc.googlegroups.com... > Peter Olcott wrote: >> The conclusion that a universal halt detector can not be constructed is >> incorrect. The proofs do not show that a universal halt-detector can not be >> constructed. The proofs only show that a universal halt-detector can not >> provide >> the results of its analysis in the case of malignant self-reference where the >> caller uses the results to change the outcome of the analysis. > > The proof is of a mathematical theorem. Whatever that has to do with a > "universal halt detector", I'll leave you to you. Meanwhile, "malignant > self-reference" has nothing to do with the mathematical theorem and > proof. > > MoeBlee > The "Halting Problem" is about "Halting". The mathematics is an attempt to create a mathematical formalism that corresponds to the concept of halting. |