Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: =?utf-8?Q?Re:_Flibble=E2=80=99s_Leap:_Why_Behavioral_Divergence_Implies_a_Type_Distinction_in_the_Halting_Problem?=
Date: Mon, 12 May 2025 11:59:10 +0300
Organization: -
Lines: 74
Message-ID: <vvsd8u$10o64$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>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 12 May 2025 10:59:10 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="53834dc5258f5a8959041c054fdb6ec4";
	logging-data="1073348"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19tCwHUFV8cBZ1IHaxc9SES"
User-Agent: Unison/2.2
Cancel-Lock: sha1:Hn6AlNEM0yYULT0sqbhq6c/1wwE=
Bytes: 4175

On 2025-05-11 15:25:14 +0000, Richard Heathfield said:

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

And it is not Turing computable whether a Flibble or Olcott woutld call
a question semantically incorrect.

-- 
Mikko