Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Richard Heathfield <rjh@cpax.org.uk>
Newsgroups: comp.theory
Subject: =?UTF-8?Q?Re=3A_Flibble=E2=80=99s_Leap=3A_Why_Behavioral_Divergence?=
 =?UTF-8?Q?_Implies_a_Type_Distinction_in_the_Halting_Problem?=
Date: Mon, 12 May 2025 18:58:34 +0100
Organization: Fix this later
Lines: 77
Message-ID: <vvtcsa$17c1i$1@dont-email.me>
References: <vv1UP.77894$JJT6.54808@fx16.ams4> <vvqd4u$g8a1$1@dont-email.me>
 <7N2UP.527443$wBt6.464256@fx15.ams4> <vvqfgq$gmmk$1@dont-email.me>
 <os3UP.670056$BFJ.223954@fx13.ams4> <vvqja4$gldn$10@dont-email.me>
 <vvql92$g8ck$4@dont-email.me> <87ikm5oklo.fsf@bsb.me.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Mon, 12 May 2025 19:58:35 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="326561ee20835be188f66800f9e0102a";
	logging-data="1290290"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19kx2fyraW3PqY85avkMffvdY7da3v7e3BbIS5FCtWDZA=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:wYGFVrurGLN8RgruETPTZGuboyQ=
Content-Language: en-GB
In-Reply-To: <87ikm5oklo.fsf@bsb.me.uk>

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