A Possible "solution" to the Halting Problem
in [Theory]
|
From: rupertmccallum on 16 Oct 2006 18:46 Peter Olcott wrote: > "Rupert" <rupertmccallum(a)yahoo.com> wrote in message > news:1160975938.946169.291050(a)i3g2000cwc.googlegroups.com... > > > > Peter Olcott wrote: > >> The Halt program throws an "Invalid Input" exception. > >> This would be analogous to the hardware exception of an attempt to divide by > >> zero. > > > > The set of programs which the program claimed to halt, the set of > > programs which the program claimed to not halt, and the set of programs > > for which the program threw the exception would all have to be > > recursive. > > > > Hopefully the program would be sound, so that all the programs which > > the program claimed to halt would actually halt. So the set of programs > > which the program claimed to halt would be a recursive subset of the > > set of programs which do actually halt. > > > > This would mean there are some programs which do actually halt, but the > > program can't tell this. > > > > It can determine that each and every program that HALTS does indeed HALT, yet > can not always provide this determination as a return value. This is not at all > the same thing as correctly concluding that its capabilities are inherently > limited, only its communication protocol is limited. > I don't understand the distinction. > It knows that the program HALTS, and merely must refrain from saying that the > program HALTS, because saying that the program HALTS provides a different > execution trace, thus a different program, and therefore a different end result.
From: William Elliot on 16 Oct 2006 19:51 On Mon, 16 Oct 2006, Peter Olcott wrote: > "William Elliot" <marsh(a)hevanet.remove.com> wrote in message > > On Mon, 16 Oct 2006, Peter Olcott wrote: > >> "William Elliot" <marsh(a)hevanet.remove.com> wrote in message > >> > On Sun, 15 Oct 2006, Peter Olcott wrote: > >> >> > "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: > Because of this I would conclude that either [the test of being an > algorithm] is not a valid test, or the definition of the term > [algorithm] may be less useful than presupposed. > Oh, that's your computer nerd handicap, that everything is programable computerese. Well it isn't. Definitions aren't algorithm and algorithms aren't definitions. However as you insist, would you give the definition of an algorithm, which of course by your naivete is the same as giving an algorithm for algorithm. Thus for your grandioso intellectual bravado Riddle of the day. What is the algorithm for algorithm? In the mean time, please produce an algorithm for a well ordering of the real numbers as constructed in ZFC. You'll also have fun producing an algorithm for determining if a number is transcendental. Test your algorithm with known transcendental numbers pi, e and log_e 2.
From: William Elliot on 16 Oct 2006 19:59 On Mon, 16 Oct 2006, Patricia Shanahan wrote: > > Are you saying that the behavior of the algorithm depends on what its > caller is going to do with the result? If so, that is a far bigger > change in the concept of algorithm than merely adding exceptions. > Of course, he's taken lessons from Bush, correct results are always produced by wishful thinking. > If not, I'm really confused about what you are saying. > Isn't it clear? Run his program on this thread. What's the output? HALT!
From: Peter Olcott on 16 Oct 2006 20:51 "Patricia Shanahan" <pats(a)acm.org> wrote in message news:hHTYg.7886$Lv3.7266(a)newsread1.news.pas.earthlink.net... > Peter Olcott wrote: >> "Patricia Shanahan" <pats(a)acm.org> wrote in message >> news:qfOYg.14496$UG4.1437(a)newsread2.news.pas.earthlink.net... >>> Peter Olcott wrote: >>> .... >>>> To frame the exception handling mechanism within the historical context of >>>> a Turing Machine we only need to establish three integer values mapped to >>>> three different semantic meanings: >>>> 0=NOT_HALTS 1=HALTS 2= INVALID_INPUT. The input is invalid in each and >>>> every case where providing the result of the determination of halting >>>> derives a different execution trace, thus changing the result. >>> Yes, but what is the algorithm for determining whether the result of the >>> determination of halting derives a different execution trace? >> >> You have it incorrectly, the result does not provide a different execution >> trace. It is the act of providing this result that derives the different >> execution trace. Halt() can determine that the test program will halt, it >> merely can not provide the results of this determination to the caller in >> this case. Halt() determines that providing the results of its correct and >> complete analysis is used to alter the execution trace, thus forming a >> different execution trace than the one that is the subject of the test. > > Are you saying that the behavior of the algorithm depends on what its caller > is going to do with the result? If so, that is a far bigger change in the > concept of algorithm than merely adding exceptions. The difficulty of the Halting Problem is that because of its infinitely recursive structure it is very difficult to see that the typical common sense assumptions that apply to nearly every other algorithm do not apply to this one. One of the most significant aspects of this atypical case, is that in the very unusual case of the Halting Problem, a function can see exactly how it is being called, and the effects of any actions that it takes upon its own caller. Within the specification of the Halting Problem, the Halt() function and its caller combined together form the program under test. In this case the behavior of one of the constituent parts (the Halt() function) forms the basis for the behavior of the other constituent part (the caller). Since this structure is directly presented to the Halt() function as input, the Halt() function can see exactly what its caller intends to do with any result that it provides (or actions that it takes). So the Halt() function breaks out of this otherwise infinitely recursive structure and provides the only possible correct answer given the specification of this problem: it throws the INVALID_INPUT exception. The Turing Machine equivalent of this would be halting with the ReadWrite Head of its tape positioned at a token indicating the semantic meaning of INVALID_INPUT. What this boils down to is not the Kurt Godel / Alan Turning conclusion that there exists some valid questions that are outside of the domain of logic, but, simply that there are some questions where the question itself is incorrect, and for this reason only, have no correct answer. > > If not, I'm really confused about what you are saying. > > Patricia
From: Peter Olcott on 16 Oct 2006 20:53
<rupertmccallum(a)yahoo.com> wrote in message news:1161038767.998763.305740(a)m73g2000cwd.googlegroups.com... > > Peter Olcott wrote: >> "Rupert" <rupertmccallum(a)yahoo.com> wrote in message >> news:1160975938.946169.291050(a)i3g2000cwc.googlegroups.com... >> > >> > Peter Olcott wrote: >> >> The Halt program throws an "Invalid Input" exception. >> >> This would be analogous to the hardware exception of an attempt to divide >> >> by >> >> zero. >> > >> > The set of programs which the program claimed to halt, the set of >> > programs which the program claimed to not halt, and the set of programs >> > for which the program threw the exception would all have to be >> > recursive. >> > >> > Hopefully the program would be sound, so that all the programs which >> > the program claimed to halt would actually halt. So the set of programs >> > which the program claimed to halt would be a recursive subset of the >> > set of programs which do actually halt. >> > >> > This would mean there are some programs which do actually halt, but the >> > program can't tell this. >> > >> >> It can determine that each and every program that HALTS does indeed HALT, yet >> can not always provide this determination as a return value. This is not at >> all >> the same thing as correctly concluding that its capabilities are inherently >> limited, only its communication protocol is limited. >> > > I don't understand the distinction. There is no incompleteness. > >> It knows that the program HALTS, and merely must refrain from saying that the >> program HALTS, because saying that the program HALTS provides a different >> execution trace, thus a different program, and therefore a different end >> result. > |