Path: ...!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 10:42:13 +0200
Organization: A noiseless patient Spider
Lines: 133
Message-ID: <vvci15$2ghfp$7@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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 06 May 2025 10:42:13 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="86b8754d754b993b604d545d7586d37b";
	logging-data="2639353"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19q7dLjRD9I/wUndKlQsDph"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:eUDiOjw51ROwrWmli3RzSVGA0GI=
Content-Language: nl, en-GB
In-Reply-To: <vvb329$15u5b$1@dont-email.me>
Bytes: 5944

Op 05.mei.2025 om 21:20 schreef olcott:
> On 5/5/2025 1:14 PM, dbush wrote:
>> On 5/5/2025 2:09 PM, olcott wrote:
>>> On 5/5/2025 12:45 PM, dbush wrote:
>>>> On 5/5/2025 1:37 PM, olcott wrote:
>>>>> On 5/5/2025 11:13 AM, Mr Flibble wrote:
>>>>>> On Mon, 05 May 2025 11:58:50 -0400, dbush wrote:
>>>>>>
>>>>>>> On 5/5/2025 11:51 AM, olcott wrote:
>>>>>>>> On 5/5/2025 10:17 AM, Mr Flibble wrote:
>>>>>>>>> What constitutes halting problem pathological input:
>>>>>>>>>
>>>>>>>>> Input that would cause infinite recursion when using a decider 
>>>>>>>>> of the
>>>>>>>>> simulating kind.
>>>>>>>>>
>>>>>>>>> Such input forms a category error which results in the halting 
>>>>>>>>> problem
>>>>>>>>> being ill-formed as currently defined.
>>>>>>>>>
>>>>>>>>> /Flibble
>>>>>>>>
>>>>>>>> I prefer to look at it as a counter-example that refutes all of the
>>>>>>>> halting problem proofs.
>>>>>>>
>>>>>>> Which start with the assumption that the following mapping is 
>>>>>>> computable
>>>>>>> and that (in this case) HHH computes it:
>>>>>>>
>>>>>>>
>>>>>>> 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
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>> int DD()
>>>>>>>> {
>>>>>>>>     int Halt_Status = HHH(DD);
>>>>>>>>     if (Halt_Status)
>>>>>>>>       HERE: goto HERE;
>>>>>>>>     return Halt_Status;
>>>>>>>> }
>>>>>>>>
>>>>>>>> https://github.com/plolcott/x86utm
>>>>>>>>
>>>>>>>> The x86utm operating system includes fully operational HHH and DD.
>>>>>>>> https://github.com/plolcott/x86utm/blob/master/Halt7.c
>>>>>>>>
>>>>>>>> When HHH computes the mapping from *its input* to the behavior 
>>>>>>>> of DD
>>>>>>>> emulated by HHH this includes HHH emulating itself emulating DD. 
>>>>>>>> This
>>>>>>>> matches the infinite recursion behavior pattern.
>>>>>>>>
>>>>>>>> Thus the Halting Problem's "impossible" input is correctly 
>>>>>>>> determined
>>>>>>>> to be non-halting.
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>> Which is a contradiction.  Therefore the assumption that the above
>>>>>>> mapping is computable is proven false, as Linz and others have 
>>>>>>> proved
>>>>>>> and as you have *explicitly* agreed is correct.
>>>>>>
>>>>>> The category (type) error manifests in all extant halting problem 
>>>>>> proofs
>>>>>> including Linz.  It is impossible to prove something which is ill- 
>>>>>> formed
>>>>>> in the first place.
>>>>>>
>>>>>> /Flibble
>>>>>
>>>>> The above example is category error because it asks
>>>>> HHH(DD) to report on the direct execution of DD() and
>>>>> the input to HHH specifies a different sequence of steps.
>>>>>
>>>>
>>>> In other words, you're demonstrating that you don't understand proof 
>>>> by contradiction, a concept taught to and understood by high school 
>>>> students more than 50 years your junior.
>>>>
>>>
>>> Self-contradiction is semantically ill-formed and has
>>> nothing to do with proof by contradiction.
>>>
>>
>> The contradiction comes about as a result of the assumption that an 
>> algorithm exists that computes the following mapping, 
> 
> NOT AT ALL.
> The self-contradiction comes when an input D
> to a termination analyzer H is actually able
> to do the opposite of whatever value that H
> returns. In this case BOTH Boolean RETURN
> VALUES ARE THE WRONG ANSWER.
> 
> D conditions its behavior on the value that H returns
> to it. This means that there are two instances of D
> paired with corresponding instances of H.
> 
> This will be too difficult for you if you don't
> understand the notion of hypothetical possibilities.
> 
> Is "halts" the correct answer for H to return?  

For one H it is the correct answer, for the other H the answer should be NO.
But both return the wrong answer. Both are wrong.


 > NO> Is "does not halt" the correct answer for H to return?

For one H it is the correct answer, for the other H the answer should be 
YES.
But both return the wrong answer. Both are wrong.


 > NO> Both Boolean return values are the wrong answer
> BECAUSE THE INPUT IS SELF-CONTRADICTORY.

You seem to have a problem with the meaning of the word 'self'. One H is 
not the other H. One D is not the other D.
Each H contradicts its own D. There is no self-contradiction.