Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Halting Problem: What Constitutes Pathological Input
Date: Tue, 6 May 2025 12:35:32 +0300
Organization: -
Lines: 79
Message-ID: <vvcl54$2lap7$1@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>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 06 May 2025 11:35:32 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="12c6f9b145a2857328672086e7280225";
	logging-data="2796327"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX193VQZ+nkH4gk14eQJgXHPx"
User-Agent: Unison/2.2
Cancel-Lock: sha1:JoVtpTHR1ZtewiUBZXpqqMNYswg=

On 2025-05-05 17:37:20 +0000, olcott said:

> 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.

No, it does not. The input is DD specifides exactly the same sequence
of steps as DD. HHH just answers about a different sequence of steps
instead of the the seqeunce specified by its input.

-- 
Mikko