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: olcott <polcott333@gmail.com>
Newsgroups: comp.theory
Subject: Re: Halting Problem: What Constitutes Pathological Input
Date: Mon, 5 May 2025 13:47:21 -0500
Organization: A noiseless patient Spider
Lines: 95
Message-ID: <vvb13p$vtiu$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>
 <vvao8p$o4v0$2@dont-email.me> <vvav61$vtiu$5@dont-email.me>
 <vvavii$o4v0$5@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 20:47:22 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="0a6320ec149f030cd98ca15e4d2d5e5f";
	logging-data="1046110"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/s5RiId0xUUiye+cGkp1Fl"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:iXPVhyK7X690uZVXr8ibJk4BDEw=
X-Antivirus-Status: Clean
Content-Language: en-US
X-Antivirus: Norton (VPS 250505-4, 5/5/2025), Outbound message
In-Reply-To: <vvavii$o4v0$5@dont-email.me>
Bytes: 4661

On 5/5/2025 1:21 PM, dbush wrote:
> On 5/5/2025 2:14 PM, olcott wrote:
>> On 5/5/2025 11:16 AM, dbush wrote:
>>> On 5/5/2025 12:13 PM, 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
>>>
>>> All algorithms either halt or do not halt when executed directly. 
>>> Therefore the problem is not ill formed.
>>>
>>
>> When BOTH Boolean RETURN VALUES are the wrong answer
>> THEN THE PROBLEM IS ILL-FORMED. Self-contradiction must
>> be screened out as semantically incorrect.
> 
> In other words, you're claiming that there exists an algorithm, i.e. a 
> fixed immutable sequence of instructions, that neither halts nor does 
> not halt when executed directly.
> 

That is not what I said.
Is this sentence true or false: "This sentence is not true" ?
Is the same sort of category error that Flibble is referring to.

-- 
Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer