Re: Halting Problem Corrected

Mr Flibble <flibble@red-dwarf.jmc.corp> writes:

Obviously my idea necessitates extending the definition of a halt
decider:
>
1) Decider decision is HALTS if input halts.
2) Decider decision is NON-HALTING if input does not halt.
3) Decider rejects pathological input as invalid by signaling sNaP.
>
Thoughts?

The trouble is that this specification has a pointless third case.
Since every "input" either halts or does not halt, all inputs are
covered by your first two cases.  There are no computations that don't
do one or the other.

You can certainly have an almost-decider, AHD, that detects three cases:

1) The computations AHD can definitely work out are halting;
2) the computations AHD can definitely work our are non-halting;
3) all the others.

But that's old news.  Of course such an AHD could well be very useful
depending on how good it is, but it's not of any interest from a
theoretical point of view.

--
Ben.