Re: Flibble’s Leap: Why Behavioral Divergence Implies a Type Distinction in the Halting Problem

On 12/05/2025 17:32, Ben Bacarisse wrote:

Richard Heathfield <rjh@cpax.org.uk> writes:
 

<snip>

>
QA: "P is a syntactically correct program in some well-defined
Turing-complete language. Does P stop when it is applied to this data
X?"

 Sometimes PO accepts this a yes/no question with a correct answer in
every case and sometimes he does not.  On those days when he does accept
it, he asserts (quite unambiguously -- I can post a direct quote or a
message ID) that no is sometimes the correct answer even when P(X)
halts.
 

QB: ``Is it possible to write a program that answers QA for arbitrary P and
arbitrary X?"

<snip>

But on some days, PO does /not/ accept that there is a correct yes/no
answer to QA in every case.  On those days, he thinks there is a
"pathological input" for which there is no correct answer.

<foreshadowing>
   Sit up, folks...
</foreshadowing>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

This was a very common problem with students.  They so buy into the
assumption "let H be a TM that decides halting" that they think that H'
and H^ (to use Linz's notation) also exist and so there really is a
concrete string of symbols (the encoding of H^ which I write as [H^])
such that H^([H^]) halts if it doesn't and doesn't halt if it does.
 Of course, there are no pathological inputs like this because H does not
exist.  For every TM, M, the machines M' and M^ do indeed exist, [M^]
really is some finite string of symbols and M^([M^]) either halts or it
does not halt.  But because none of the infinite variety of Ms
implements the halting function, there is no paradox or pathological
input anywhere to be seen.

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Here, Ben cuts straight to the heart of the matter. If you haven't got it yet, cut along the plussed lines, optimise the font size for one full page, print, and blu-tac the page to your fridge.

Aside...  Forgive me for repeatedly replying to you.

Nothing to forgive.

It's because I
know you from comp.lang.c and because you are, I think, new to this
thread which has been going on for over 20 years.

I am, yes. 20 years, though? Really? That's one hell of a filibuster, albeit one that's several decades too late.

I think everyone else
here knows the history, but you might not know what PO has said in the
past and, anyway, I think it helps to remind everyone that PO has given
the game away more than once.

...which suggests that he may be yanking a 20-year-old chain just because he likes to hear it rattle.
<snip>
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within