Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Halting Problem: What Constitutes Pathological Input
Date: Wed, 7 May 2025 11:57:58 +0300
Organization: -
Lines: 57
Message-ID: <vvf7am$u0k0$1@dont-email.me>
References: <GE4SP.47558$VBab.42930@fx08.ams4> <vvamqc$o6v5$4@dont-email.me> <vvan7q$o4v0$1@dont-email.me> <ts5SP.113145$_Npd.41800@fx01.ams4> <vvat0g$vtiu$1@dont-email.me> <vvatf3$o4v0$3@dont-email.me> <vvaut0$vtiu$4@dont-email.me> <vvav6o$o4v0$4@dont-email.me> <vvb329$15u5b$1@dont-email.me> <vvb37g$1451r$1@dont-email.me> <vvb43f$15u5b$4@dont-email.me> <vvb4ok$o4v0$9@dont-email.me> <vvb52g$15u5b$6@dont-email.me> <vvclr6$2lui8$1@dont-email.me> <vvda90$37t3c$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 07 May 2025 10:57:59 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="fb18c6efacd66d99a59635d4c6fef515";
	logging-data="983680"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/g455hj0USqP9OfhDbKwY6"
User-Agent: Unison/2.2
Cancel-Lock: sha1:eJQnxTopYl/s1BuUeh35OMha4XE=

On 2025-05-06 15:36:00 +0000, olcott said:

> On 5/6/2025 4:47 AM, Mikko wrote:
>> On 2025-05-05 19:54:55 +0000, olcott said:
>> 
>>> On 5/5/2025 2:49 PM, dbush wrote:
>>>> On 5/5/2025 3:38 PM, olcott wrote:
>>>>> On 5/5/2025 2:23 PM, Richard Heathfield wrote:
>>>>>> On 05/05/2025 20:20, olcott wrote:
>>>>>>> Is "halts" the correct answer for H to return?  NO
>>>>>>> Is "does not halt" the correct answer for H to return?  NO
>>>>>>> Both Boolean return values are the wrong answer
>>>>>> 
>>>>>> Or to put it another way, the answer is undecidable, QED.
>>>>>> 
>>>>>> See? You got there in the end.
>>>>>> 
>>>>> 
>>>>> Is this sentence true or false: "What time is it?"
>>>>> is also "undecidable" because it is not a proposition
>>>>> having a truth value.
>>>>> 
>>>>> Is this sentence true or false: "This sentence is untrue."
>>>>> is also "undecidable" because it is not a semantically sound
>>>>> proposition having a truth value.
>>>>> 
>>>>> Can Carol correctly answer “no” to this (yes/no) question?
>>>>> 
>>>>> Both Yes and No are the wrong answer proving that
>>>>> the question is incorrect when the context of who
>>>>> is asked is understood to be a linguistically required
>>>>> aspect of the full meaning of the question.
>>>> 
>>>> And "does algorthm X with input Y halt when executed directly" has a 
>>>> single well defined answer.
>>>> 
>>> 
>>> That is not even the actual question.
>>> 
>>> Does the finite string input DD to HHH specify
>>> a computation that halts? No it does not.
>> 
>> That question is a category error. The halting question is not about
>> finite strings but about computations.
> 
> HHH must compute the mapping from its finite string
> of x86 code input to the actual behavior that this
> finite string input specifies.

No, that is not what the halting problem requires. The halting problem
requires that HHH must be given a finite string that tells what HHH
needs to know about DD in order to correctly predict whether DD halts
if it is directly executed.

-- 
Mikko