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

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?

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