Alex Allain has written a few interesting articles including a theoretical one that demonstrates in simple terms the insolubility of the halting problem. http://www.cprogramming.com/tutorial/computersciencetheory/halting.html. Here is a quick summary. Suppose that there is such a decider DOES-HALT(program, input) that return true if program halts on input, and returns false otherwise. He then shows that such a program cannot exist. He constructs SELF-HALT(program) { if(DOES-HALT(program, program)) infinite loop else halt } If we pass SELF-HALT to SELF-HALT() a contradiction results. * * * * * So suppose now that there is a program DOES-HALT() that always answers the question if program halts on input EXCEPT in cases where the assumption that it does answer leads to a contradiction, and whenever DOES-HALT() does answer, the answer will be correct. Let us now construct a program SELFIE(void) { SELF-HALT(SELF-HALT) // ~T(halts) } What happens when we pass SELFIE() to SELF-HALT()? SELF-HALT(SELFIE) { if(DOES-HALT(SELFIE, SELFIE) // ~halts infinite loop else halt } SELFIE() does not need a parameter, so DOES-HALT() will simply ignore the second argument. I am suggesting that the following will halt and say 'no'. DOES-HALT(SELF-HALT, SELFIE) Any questions? -- X.Y. Newberry If Jack says �What I am saying at this very moment is not true�, we can successfully and truly assert that he did not utter a truth: �What Jack said is not true�. But it is hardly conceivable that Jack�s utterance is true by virtue of its success in attributing non-truth to itself. Haim Gaifman
![]() |
0 |
![]() |
On 11/20/2016 9:56 AM, X.Y. Newberry wrote: > Alex Allain has written a few interesting articles > including a theoretical one that demonstrates in > simple terms the insolubility of the halting problem. > http://www.cprogramming.com/tutorial/computersciencetheory/halting.html > . Here is a quick summary. Suppose that there is such a decider > > DOES-HALT(program, input) > > that return true if program halts on input, and returns false > otherwise. He then shows that such a program cannot exist. > He constructs > > SELF-HALT(program) > { > if(DOES-HALT(program, program)) > infinite loop > else > halt > } > > If we pass SELF-HALT to SELF-HALT() a contradiction results. > > * * * * * > > So suppose now that there is a program DOES-HALT() that > always answers the question if program halts on input > EXCEPT in cases where the assumption that it does answer > leads to a contradiction, > and whenever DOES-HALT() does answer, > the answer will be correct. It would be clearer if you picked a different name, since DOES-HALT(,) already has a description, even though there is no actual program DOES-HALT(,) as you note. Since the program you describe has three outcomes (broadly speaking, if not three final states) -- print "HALTS" and halt, print "LOOPS" and halt, loop -- I suggest something like HALTS-LOOPS-EXPLODES(,) ("EXPLODES" is meant to evoke the mythical machine language command HCF Halt and Catch Fire ) That's kind of long. It might good to abbreviate it HLX(,) It's not clear to me when HLX is supposed to loop. I know, you say it will loop when answering will lead to a contradiction, but I think of it more like the existence of some program (such as DOES-HALT) leading to a contradiction. And, since DOES-HALT doesn't exist, it can't be input to create a loop-state for HLX. Of course, if we are talking about abstract programs, any particular (program(),input) pair will either halt or loop. Catching fire or exploding is not one of the choices. So, I wonder on which program-inputs HLX will "return" EXPLODES (by not returning anything -- sorry about the poor terminology). It cannot be that you mean for HLX to return HALTS or LOOPS on all inputs that would halt or loop if run and not return on "the others" (whatever "the others" may be) -- because no others exist (such "others" as we are discussing do not exist). If there were such a program HLX(,) it wouldn't matter that the result was "signaled" by never returning. If there were such a program HLX(,), never-returning would serve as well as returning, because we would be able to calculate when it would not return. DOES-HALT(program(),input) { if HLX(HLX(,),(program(),input)) = LOOPS return EXPLODES else if HLX(program(),input) = LOOPS return LOOPS else if HLX(program(),input) = HALTS return HALTS else catch-fire } (If I understand what you mean, "catch-fire" should never be executed, under any circumstances.) DOES-HALT looks to me like a perfect halting-decider, which we've proved doesn't exist. If HLX is a near-perfect halting-decider, which tells the truth about all programs that halt or loop, that implies the existence of the non-existent perfect halting-decider. So, HLX is not that. What is HLX? On what _existing_ inputs does HLX loop? > Let us now construct a program > > SELFIE(void) > { > SELF-HALT(SELF-HALT) // ~T(halts) > } I assume you mean this by SELFIE, calling your hypothetical near-perfect halting-decider instead of the earlier perfect halting-decider DOES-HALT: SELF-HALT(program) { if(HLX(program, program)) infinite loop else halt } > What happens when we pass SELFIE() to SELF-HALT()? > > SELF-HALT(SELFIE) > { > if(DOES-HALT(SELFIE, SELFIE) // ~halts > infinite loop > else > halt > } > > SELFIE() does not need a parameter, > so DOES-HALT() will simply ignore the second argument. > > I am suggesting that the following will halt and say 'no'. > > DOES-HALT(SELF-HALT, SELFIE) > > Any questions? Which, if any, existent program-inputs does the second DOES-HALT (which I call HLX) loop on?
![]() |
0 |
![]() |
Jim Burns wrote: > On 11/20/2016 9:56 AM, X.Y. Newberry wrote: > >> Alex Allain has written a few interesting articles >> including a theoretical one that demonstrates in >> simple terms the insolubility of the halting problem. >> http://www.cprogramming.com/tutorial/computersciencetheory/halting.html >> . Here is a quick summary. Suppose that there is such a decider >> >> DOES-HALT(program, input) >> >> that return true if program halts on input, and returns false >> otherwise. He then shows that such a program cannot exist. >> He constructs >> >> SELF-HALT(program) >> { >> if(DOES-HALT(program, program)) >> infinite loop >> else >> halt >> } >> >> If we pass SELF-HALT to SELF-HALT() a contradiction results. >> >> * * * * * >> >> So suppose now that there is a program DOES-HALT() that >> always answers the question if program halts on input >> EXCEPT in cases where the assumption that it does answer >> leads to a contradiction, >> and whenever DOES-HALT() does answer, >> the answer will be correct. > > It would be clearer if you picked a different name, > since DOES-HALT(,) already has a description, even though > there is no actual program DOES-HALT(,) as you note. Taken into consideration. > Since the program you describe has three outcomes > (broadly speaking, if not three final states) > -- print "HALTS" and halt, print "LOOPS" and halt, loop -- > I suggest something like HALTS-LOOPS-EXPLODES(,) > ("EXPLODES" is meant to evoke the mythical machine language > command HCF Halt and Catch Fire ) > That's kind of long. It might good to abbreviate it HLX(,) > > It's not clear to me when HLX is supposed to loop. > I know, you say it will loop when answering will lead to > a contradiction, but I think of it more like the existence > of some program (such as DOES-HALT) leading to a contradiction. > And, since DOES-HALT doesn't exist, it can't be input to > create a loop-state for HLX. I was speaking strictly about HLX. > Of course, if we are talking about abstract programs, any > particular (program(),input) pair will either halt or loop. > Catching fire or exploding is not one of the choices. > So, I wonder on which program-inputs HLX will "return" EXPLODES > (by not returning anything -- sorry about the poor terminology). > > It cannot be that you mean for HLX to return HALTS or > LOOPS on all inputs that would halt or loop if run and > not return on "the others" (whatever "the others" may be) -- > because no others exist (such "others" as we are discussing > do not exist). > > If there were such a program HLX(,) it wouldn't matter that > the result was "signaled" by never returning. If there > were such a program HLX(,), never-returning would serve > as well as returning, because we would be able to calculate > when it would not return. > > DOES-HALT(program(),input) > { > if HLX(HLX(,),(program(),input)) = LOOPS > return EXPLODES > else if HLX(program(),input) = LOOPS > return LOOPS > else if HLX(program(),input) = HALTS > return HALTS > else > catch-fire > } > > (If I understand what you mean, "catch-fire" > should never be executed, under any circumstances.) No. > DOES-HALT looks to me like a perfect halting-decider, > which we've proved doesn't exist. If HLX is a > near-perfect halting-decider, which tells the truth > about all programs that halt or loop, that implies > the existence of the non-existent perfect halting-decider. > > So, HLX is not that. What is HLX? On what _existing_ inputs > does HLX loop? > >> Let us now construct a program >> >> SELFIE(void) >> { >> SELF-HALT(SELF-HALT) // ~T(halts) >> } > > I assume you mean this by SELFIE, calling your hypothetical > near-perfect halting-decider instead of the earlier > perfect halting-decider DOES-HALT: > > SELF-HALT(program) > { > if(HLX(program, program)) > infinite loop > else > halt > } Yes. >> What happens when we pass SELFIE() to SELF-HALT()? >> >> SELF-HALT(SELFIE) >> { >> if(DOES-HALT(SELFIE, SELFIE) // ~halts >> infinite loop >> else >> halt >> } >> >> SELFIE() does not need a parameter, >> so DOES-HALT() will simply ignore the second argument. >> >> I am suggesting that the following will halt and say 'no'. >> >> DOES-HALT(SELF-HALT, SELFIE) >> >> Any questions? > > Which, if any, existent program-inputs does the second DOES-HALT > (which I call HLX) loop on? I think this will loop: HLX(SELFIE, SELFIE) -- X.Y. Newberry If Jack says �What I am saying at this very moment is not true�, we can successfully and truly assert that he did not utter a truth: �What Jack said is not true�. But it is hardly conceivable that Jack�s utterance is true by virtue of its success in attributing non-truth to itself. Haim Gaifman
![]() |
0 |
![]() |