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: Sun, 11 May 2025 16:25:14 +0100
Organization: Fix this later
Lines: 73
Message-ID: <vvqfgq$gmmk$1@dont-email.me>
References: <vv1UP.77894$JJT6.54808@fx16.ams4> <vvqd4u$g8a1$1@dont-email.me>
 <7N2UP.527443$wBt6.464256@fx15.ams4>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 11 May 2025 17:25:14 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="023cae9dc0d2c2b383f3d86e34fa8cd9";
	logging-data="547540"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18ZBHLJ2u6hy1oX0pMLRtkpQXXKm5PfC8H1kEWgC6cfqg=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:iQV9nkd81TkR/nm1beo/JyYqlnI=
In-Reply-To: <7N2UP.527443$wBt6.464256@fx15.ams4>
Content-Language: en-GB

On 11/05/2025 15:48, Mr Flibble wrote:
> On Sun, 11 May 2025 15:44:44 +0100, Richard Heathfield wrote:
> 
>> On 11/05/2025 14:21, Mr Flibble wrote:
>>> This reframing dissolves the paradox by making the Halting Problem
>>> itself an ill-posed question.
>>
>> "P is a syntactically correct program in some well-defined
>> Turing-complete language. Does P stop when it is applied to this data
>> X?" is a meaningful and well-formed question. It's not a Carrollian
>> question like Olcott's "what time is it, yes or no?" It has a sensible
>> answer. Either P stops for X, or it doesn't.
>>
>> It's a question that can in many (but not all) cases be answered quickly
>> and easily enough (and correctly) by humans, often requiring no more
>> than a brief glimpse. (I say 'not all' only because it is not beyond the
>> wit of mankind to trump up extraordinarily complicated and deliberately
>> obfuscated code that might easily defeat a programmer's casual glance.)
>>
>> Some simple examples in K&R C:
>>
>> main(){}
>>
>> main(){for(;;);}
>>
>> main(){puts("Hello");}
>>
>> #include <stdio.h>
>> main(){long c=0;int ch; while((ch = getchar()) !=
>> EOF)++c;printf("%ld\n", c);} /* input: the complete works of Shakespeare
>> */
>>
>> Any competent C programmer can solve these at a glance - Halts, Loops,
>> Halts, Halts, in that order - so why shouldn't a program be able to?
>>
>> The Halting Problem asks a more complicated question. ``Is it possible
>> to write a program that answers the above question for arbitrary P and
>> arbitrary X?"
>>
>> Again, the question is meaningful and well-formed. It's syntactically
>> and grammatically adequate, and anyone claiming not to know what it
>> means is laying themselves open to a charge of disingenuousness. The
>> only difficult part is the answer, but there's nothing
>> self-contradictory or self-referential or paradoxical about the
>> question.
> 
> It is insufficient for the question to be syntactically correct, it needs
> to be SEMANTICALLY correct too.

It has a meaning that I can readily understand. Your not liking 
it is not sufficient to render it meaningless.

Ask Mikko, Mike Terry, dbush, wij, or Richard Damon whether they 
can work out what it means. I have no doubt that they all can.

Truth is not a democracy, of course, but it is humans who make 
sense of human language. I'm sure you can find someone who sees 
no meaning in it - a Russian monoglot truck driver, perhaps - but 
to an English-speaking programmer the question is not even 
remotely unclear in its meaning.

The /answer/ might (or might not) turn out to be difficult, but 
the question is perfectly straightforward.

For a question to be semantically incorrect, it takes more than 
just you and your allies to be unhappy with it.

-- 
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