A Possible "solution" to the Halting Problem
in [Theory]
|
From: Patricia Shanahan on 16 Oct 2006 21:50 Peter Olcott wrote: > "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. I'm not sure whether all that means "yes" or "no". To try to understand, I'd like to nail down some terminology and program names. http://www.mtnmath.com/whatrh/node49.html contains a simplified version of the proof. Could you explain, in the terminology of that page, how h would detect a situation in which it should throw the exception. Patricia
From: Peter Olcott on 16 Oct 2006 22:20 "Patricia Shanahan" <pats(a)acm.org> wrote in message news:_FWYg.7998$Lv3.6750(a)newsread1.news.pas.earthlink.net... > Peter Olcott wrote: >> "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. > > I'm not sure whether all that means "yes" or "no". Are you saying that the behavior of the algorithm depends on what its caller is going to do with the result? Yes! In the atypical instance of the Halting Problem the called can know in advance both that its actions will effect the caller, and exactly how its actions will effect the caller. Because it has this information in advance it can decide what to do about it, and thereby effect the total outcome. > > To try to understand, I'd like to nail down some terminology and program > names. http://www.mtnmath.com/whatrh/node49.html contains a simplified > version of the proof. > > Could you explain, in the terminology of that page, how h would detect a > situation in which it should throw the exception. > > Patricia
From: Patricia Shanahan on 16 Oct 2006 23:11 Peter Olcott wrote: > "Patricia Shanahan" <pats(a)acm.org> wrote in message > news:_FWYg.7998$Lv3.6750(a)newsread1.news.pas.earthlink.net... >> Peter Olcott wrote: >>> "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. >> I'm not sure whether all that means "yes" or "no". > > > Are you saying that the behavior of the algorithm depends on what its caller > is going to do with the result? > > Yes! In the atypical instance of the Halting Problem the called can know in > advance both that its actions will effect the caller, and exactly how its > actions will effect the caller. Because it has this information in advance it > can decide what to do about it, and thereby effect the total outcome. HOW does h know "exactly how its actions will affect this caller"? All it knows is its caller has fed it a number, and asked "Is this the Goedel number of a computation that halts?". We know that the TM in that computation uses a copy of h as part of its source code, but it could be obfuscated. > >> To try to understand, I'd like to nail down some terminology and program >> names. http://www.mtnmath.com/whatrh/node49.html contains a simplified >> version of the proof. >> >> Could you explain, in the terminology of that page, how h would detect a >> situation in which it should throw the exception. >> >> Patricia > >
From: William Elliot on 17 Oct 2006 02:46 On Tue, 17 Oct 2006, Patricia Shanahan wrote: > Peter Olcott wrote: > > Yes! In the atypical instance of the Halting Problem the called can > > know in advance both that its actions will effect the caller, and > > exactly how its actions will effect the caller. Because it has this > > information in advance it can decide what to do about it, and thereby > > effect the total outcome. > > HOW does h know "exactly how its actions will affect this caller"? All > it knows is its caller has fed it a number, and asked "Is this the > Goedel number of a computation that halts?". We know that the TM in that > computation uses a copy of h as part of its source code, but it could be > obfuscated. > Here's a halting algorithm for OP to lament upon. 1) OP, to prove the validity of his notion, will always ignore or misconstrue your comments. 2) No matter what you say or do, the results will be the same, OP notions is always correct. It can not, will not ever be else. 3) The program of you replying and OP stringing you along won't halt. 4) Therefore, output is not-halt. Thus the algorithm, as the algorithm has put out output, has halted. Then, dear Patricia, upon the futility of your expert efforts, do you HALT!
From: Peter Olcott on 17 Oct 2006 08:46
"William Elliot" <marsh(a)hevanet.remove.com> wrote in message news:Pine.BSI.4.58.0610162328190.15058(a)vista.hevanet.com... > On Tue, 17 Oct 2006, Patricia Shanahan wrote: >> Peter Olcott wrote: > >> > Yes! In the atypical instance of the Halting Problem the called can >> > know in advance both that its actions will effect the caller, and >> > exactly how its actions will effect the caller. Because it has this >> > information in advance it can decide what to do about it, and thereby >> > effect the total outcome. >> >> HOW does h know "exactly how its actions will affect this caller"? All >> it knows is its caller has fed it a number, and asked "Is this the >> Goedel number of a computation that halts?". We know that the TM in that >> computation uses a copy of h as part of its source code, but it could be >> obfuscated. >> > Here's a halting algorithm for OP to lament upon. > 1) OP, to prove the validity of his notion, will always ignore or > misconstrue your comments. > 2) No matter what you say or do, the results will be the same, OP > notions is always correct. It can not, will not ever be else. > 3) The program of you replying and OP stringing you along won't > halt. > 4) Therefore, output is not-halt. > > Thus the algorithm, as the algorithm has put out output, has halted. > Then, dear Patricia, upon the futility of your expert efforts, do you > HALT! That is factually incorrect. I was here a couple of years ago, and the line-of-reasoning that I presented at the time was proven to be incorrect by newstome(a)comcast.net a PhD computer science professor. |