Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: Mikko 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: References: <7N2UP.527443$wBt6.464256@fx15.ams4> 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 >>> 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