Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: dbush <dbush.mobile@gmail.com>
Newsgroups: comp.theory
Subject: Re: Halting Problem: What Constitutes Pathological Input
Date: Mon, 5 May 2025 15:49:41 -0400
Organization: A noiseless patient Spider
Lines: 47
Message-ID: <vvb4ok$o4v0$9@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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 05 May 2025 21:49:41 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="18d110b57402f35c65b5688042d33321";
	logging-data="791520"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+vM7i8+Nq0G0KXVjORI3R/"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:34uRK0qjieeYbAOHxzoQfVHwvbM=
In-Reply-To: <vvb43f$15u5b$4@dont-email.me>
Content-Language: en-US

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.


Given an implementation of function H for which the function call H(D) 
return 0, we'll call this algorithm H0, and the function D that calls 
this we'll call algorithm D0.

Given an implementation of function H for which the function call H(D) 
returns 1, we'll call this algorithm H1, and the function D that calls 
this we'll call algorithm D1.

Algorithm D0 halts when executed directly, so the correct answer is 1.

Algorithm D1 does not halt when executed directly, so the correct answer 
is 0.

Algorithm H1 gives the wrong answer for algorithm D1, and algorithm H0 
gives the wrong answer for algorithm D0.  So it's not that both answers 
are wrong.