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 14:21:06 -0400
Organization: A noiseless patient Spider
Lines: 99
Message-ID: <vvavii$o4v0$5@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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 05 May 2025 20:21:06 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="18d110b57402f35c65b5688042d33321";
	logging-data="791520"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/Uww7nPkykKgevAu48hzrU"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:CafyiQFbq1fO2+yHJxchijCAet4=
In-Reply-To: <vvav61$vtiu$5@dont-email.me>
Content-Language: en-US

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.

Show it.

Failure to do so in your next reply or within one hour of your next 
posting in this newsgroup will be taken as your official on-the-record 
admission that the halting problem is NOT ill-formed and that the below 
criteria is VALID:


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