A Possible "solution" to the Halting Problem
in [Theory]
|
From: Patricia Shanahan on 16 Oct 2006 09:07 Peter Olcott wrote: > "William Elliot" <marsh(a)hevanet.remove.com> wrote in message > news:Pine.BSI.4.58.0610152213330.1333(a)vista.hevanet.com... >> On Sun, 15 Oct 2006, Peter Olcott wrote: >>> <mareg(a)mimosa.csv.warwick.ac.uk> wrote in message >>>> "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: >>>>> X = 50.0 / 0.0 >>>>> Is this an unsolvable problem or an ill-formed problem? >>>> I cannot see a problem there at all, just an equation with an undefined >>>> RHS. >>>> What is the problem exactly? >>> What is the value of X? >>> >> Just like he told you, X doesn't have a value. > > Which is the same result obtained from Halt() when it throws the INVALID_INPUT > exception. It neither returns HALTS, nor NOT_HALTS. There is no magic to exception throwing. It is just a programming language technique for communicating the results of a frequent test. Anything that could be done by e.g. having an exception for division by zero could also be done by having an explicit test for acceptability of a division, combined with a division operation whose results are completely undefined for invalid inputs: if(isValid("50.0 / 0.0") then X = 50.0 / 0.0 else GiveUp Because they add complication without adding anything to what can be computed, exceptions are usually ignored in theory of computation. However, if you are going to add them, the exception condition has to be computable for them to make any sense. What is your algorithm for computing whether a halting problem input is valid or not? Patricia
From: Peter Olcott on 16 Oct 2006 11:42 "Patricia Shanahan" <pats(a)acm.org> wrote in message news:EuLYg.14458$UG4.11820(a)newsread2.news.pas.earthlink.net... > Peter Olcott wrote: >> "William Elliot" <marsh(a)hevanet.remove.com> wrote in message >> news:Pine.BSI.4.58.0610152213330.1333(a)vista.hevanet.com... >>> On Sun, 15 Oct 2006, Peter Olcott wrote: >>>> <mareg(a)mimosa.csv.warwick.ac.uk> wrote in message >>>>> "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: >>>>>> X = 50.0 / 0.0 >>>>>> Is this an unsolvable problem or an ill-formed problem? >>>>> I cannot see a problem there at all, just an equation with an undefined >>>>> RHS. >>>>> What is the problem exactly? >>>> What is the value of X? >>>> >>> Just like he told you, X doesn't have a value. >> >> Which is the same result obtained from Halt() when it throws the >> INVALID_INPUT exception. It neither returns HALTS, nor NOT_HALTS. > > There is no magic to exception throwing. It is just a programming > language technique for communicating the results of a frequent test. > Anything that could be done by e.g. having an exception for division by > zero could also be done by having an explicit test for acceptability of > a division, combined with a division operation whose results are > completely undefined for invalid inputs: > > if(isValid("50.0 / 0.0") then > X = 50.0 / 0.0 > else > GiveUp > > Because they add complication without adding anything to what can be > computed, exceptions are usually ignored in theory of computation. > > However, if you are going to add them, the exception condition has to be > computable for them to make any sense. What is your algorithm for > computing whether a halting problem input is valid or not? > > Patricia 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.
From: Patricia Shanahan on 16 Oct 2006 12:16 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? Or other proof that the set of invalid inputs is TM-decidable? The algorithm gets as input the Goedel number corresponding to a TM-computation, a combination of initial tape state and machine description. Patricia
From: Peter Olcott on 16 Oct 2006 12:53 "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. > Or other > proof that the set of invalid inputs is TM-decidable? > > The algorithm gets as input the Goedel number corresponding to a > TM-computation, a combination of initial tape state and machine description. > > Patricia
From: Patricia Shanahan on 16 Oct 2006 18:27
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. If not, I'm really confused about what you are saying. Patricia |