Path: ...!weretis.net!feeder9.news.weretis.net!news.quux.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: "Fred. Zwarts" <F.Zwarts@HetNet.nl>
Newsgroups: comp.theory
Subject: Re: Halting Problem: What Constitutes Pathological Input
Date: Tue, 6 May 2025 12:17:44 +0200
Organization: A noiseless patient Spider
Lines: 77
Message-ID: <vvcnk8$2ghfp$13@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> <vvb5ca$o4v0$10@dont-email.me>
 <vvb5vp$15u5b$7@dont-email.me> <vvb675$o4v0$11@dont-email.me>
 <vvb9d7$1av94$3@dont-email.me> <vvbani$1b6l1$1@dont-email.me>
 <vvbb82$1a9jr$5@dont-email.me> <vvbcef$1b6l1$3@dont-email.me>
 <vvbe4m$1av94$9@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 06 May 2025 12:17:44 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="86b8754d754b993b604d545d7586d37b";
	logging-data="2639353"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18YQElk8fcfH8XbTIIcQTvc"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:aRAx2lBakmKtXJHETIisYDfUfVM=
Content-Language: nl, en-GB
In-Reply-To: <vvbe4m$1av94$9@dont-email.me>
Bytes: 4908

Op 06.mei.2025 om 00:29 schreef olcott:
> On 5/5/2025 5:00 PM, dbush wrote:
>> On 5/5/2025 5:40 PM, Richard Heathfield wrote:
>>> On 05/05/2025 22:31, dbush wrote:
>>>> It's just that no algorithm exists that can compute that mapping, as 
>>>> proven by Linz and other and as you have *explicitly* agreed is 
>>>> correct.
>>>
>>> He's coming round to the idea, albeit slowly. He can't bring himself 
>>> to describe the mapping as 'incomputable' or 'undecidable', but he's 
>>> started to claim that such a mapping is 'incorrect', which is a tacit 
>>> acknowledgement that it exists.
>>>
>>
>> Oh, he's agreed to it many times.  Here's a partial list:
>>
>>
>> On 3/24/2025 10:07 PM, olcott wrote:
>>  > A halt decider cannot exist
>>
>> On 4/28/2025 2:47 PM, olcott wrote:
>>  > On 4/28/2025 11:54 AM, dbush wrote:
>>  >> And the halting function below is not a computable function:
>>  >>
>>  >
>>  > It is NEVER a computable function
>>  >
>>  >> Given any algorithm (i.e. a fixed immutable sequence of 
>> instructions) X described as <X> with input Y:
>>  >>
>>  >> A solution to the halting problem is an algorithm H that computes 
>> the following mapping:
>>  >>
>>  >> (<X>,Y) maps to 1 if and only if X(Y) halts when executed directly
>>  >> (<X>,Y) maps to 0 if and only if X(Y) does not halt when executed 
>> directly
>>
>> On 3/14/2025 1:19 PM, olcott wrote:
>>  > When we define the HP as having H return a value
>>  > corresponding to the halting behavior of input D
>>  > and input D can actually does the opposite of whatever
>>  > value that H returns, then we have boxed ourselves
>>  > in to a problem having no solution.
>>
>> On 6/21/2024 1:22 PM, olcott wrote:
>>  > the logical impossibility of specifying a halt decider H
>>  > that correctly reports the halt status of input D that is
>>  > defined to do the opposite of whatever value that H reports.
>>  > Of course this is impossible.
>>
>> On 7/4/2023 12:57 AM, olcott wrote:
>>  > If you frame the problem in that a halt decider must divide up finite
>>  > strings pairs into those that halt when directly executed and those 
>> that
>>  > do not, then no single program can do this.
>>
>> On 5/5/2025 5:39 PM, olcott wrote:
>>  > On 5/5/2025 4:31 PM, dbush wrote:
>>  >> Strawman.  The square root of a dead rabbit does not exist, but the
>>  >> question of whether any arbitrary algorithm X with input Y halts when
>>  >> executed directly has a correct answer in all cases.
>>  >>
>>  >
>>  > It has a correct answer that cannot ever be computed
>>
>>
> 
> There never has been any input that could
> ever actually do the opposite of whatever
> value that its termination analyzer returns.
> That part of its code was ALWAYS unreachable.
It is not unreachable, as proven by direct execution and world-class 
simulators. It is unreachable for HHH, because of a bug which makes that 
it aborts prematurely, before it could reach that part.
But exactly that bug makes the program halting and that part of the code 
reachable according to the semantics of the x86 language, which is 
violated by HHH.