A Possible "solution" to the Halting Problem
in [Theory]
|
From: Daryl McCullough on 19 Oct 2006 09:48 Peter Olcott says... >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?" That's not an ill-formed question. It is a perfectly good question, and it has a perfectly good answer: Yes, it halts (by throwing an exception). (The semantics of exceptions hasn't been spelled out, but in most normal programming languages, if a program throws an exception, then the program stops at that point.) -- Daryl McCullough Ithaca, NY
From: Dr A. N. Walker on 19 Oct 2006 10:15 In article <KyxZg.28265$eZ4.22514(a)dukeread06>, Peter Olcott <NoSpam(a)SeeScreen.com> wrote: >> [...] There is also no need for >> the HP to refer to programs *at all*; >Then what would it be that we are attempting to test the halting of? It would >seem that you must be wrong here. If there are no programs, then there is no >halting, thus no "Halting Problem" is possible, [...] I didn't say "there are no programs", only that the HP doesn't need to refer to them. Ever since the invention of the "stored program" concept, we have known that there is no interesting distinction between "program" and "data". As for "halting", this is merely one particular state of the computer [and not usually, since the invention of operating systems, an actual literal "halt", but merely an instruction to the OS that it is not to return control to this program]. >> there is a simple equivalent >> formulation entirely in terms of data [eg as supplied to a UTM]. >A UTM is essentially defined as being a program. A UTM is essentially a *computer*. Spot the difference. >>> 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. >> No, it doesn't show that. No matter how MSR your program may be, >> there are programs out there that will show whether or not your program >> with its data will halt. But this is a game of "you show me yours and >> I'll show you mine". >Not when the result of this determination is structured as listed below: > http://www.cprogramming.com/tutorial/computersciencetheory/halting.html Yes, even so. What that [standard] proof shows is that *if* you show me your [purported] halt-tester, *then* I can construct a derived [MSR] program on which your tester fails. I can't write down that code without seeing the code that claims to be a correct tester, and after I have written down my buster, all it shows is that your code is incorrect. The MSR program is not itself hard to analyse -- no harder than your code on which it is based. *Your* code cannot analyse it, but there is other code out there that can [but that code in turn is not going to be able to analyse some inputs]. See "http://www.maths.nott.ac.uk/personal/anw/G12FCO/lect18.html" for perhaps relevant [though now rather old] discussion. [The preceding lecture discusses UTMs and the standard HP proof, and there are also relevant snippets in later lectures.] It's not MSR-ness of code that makes it hard to analyse, but what we might loosely call "3x+1" or "Collatz" behaviour -- code with lots of special cases that never seem to explode to the extent that it's provable we're losing, but never collapse to a result either, so that it always seems worthwhile to go on a little longer. -- Andy Walker, School of MathSci., Univ. of Nott'm, UK. anw(a)maths.nott.ac.uk
From: The Ghost In The Machine on 19 Oct 2006 10:16 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. In any event, Turing machines cannot reference themselves; there's no concept of a pointer therein. Coding systems might; one old machine in particular (the HP 21xx series), when presented with JSR Addr, did the following: M[Addr] = PC+1 PC = Addr+1 which in its way is a form of code modification. (The return was simply a JMP ADDR,I.) On a higher level one can contemplate function synthesis, in language that support first-level functions. However, that isn't self-referential, but function copying. -- #191, ewill3(a)earthlink.net Useless C++ Programming Idea #7878218: class C { private: virtual void stupid() = 0; }; -- Posted via a free Usenet account from http://www.teranews.com
From: The Ghost In The Machine on 19 Oct 2006 10:18 In sci.logic, MoeBlee <jazzmobe(a)hotmail.com> wrote on 18 Oct 2006 17:29:52 -0700 <1161217792.569440.110550(a)h48g2000cwc.googlegroups.com>: > Peter Olcott wrote: >> I know that the UTM form mathematically maps to the form that I provided. > > Sure you do. > > MoeBlee > Without a well-defined method of testing for MALIGNANT_SELF_REFERENCE, I for one would stipulate that Peter Olcott's solution is of little use. (Assuming MALIGNANT_SELF_REFERENCE can even be defined.) -- #191, ewill3(a)earthlink.net Linux. Because life's too short for a buggy OS. -- Posted via a free Usenet account from http://www.teranews.com
From: Patricia Shanahan on 19 Oct 2006 11:42
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. Patricia |