Path: ...!eternal-september.org!feeder3.eternal-september.org!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: Wed, 7 May 2025 12:42:05 +0300
Organization: -
Lines: 101
Message-ID: <vvf9td$ujn3$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> <vvcl54$2lap7$1@dont-email.me> <vvd9tn$37t3c$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 07 May 2025 11:42:05 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="25df689eb2c62a67673a2c25ccb2e051";
	logging-data="1003235"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19TupCnTVinJVy4NWQZL90V"
User-Agent: Unison/2.2
Cancel-Lock: sha1:VKsvBvwuKNtRwCaKzXc7omI7GwY=
Bytes: 4821

On 2025-05-06 15:29:59 +0000, olcott said:

> On 5/6/2025 4:35 AM, Mikko wrote:
>> 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.
> 
> <MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022>
>      If simulating halt decider H correctly simulates its
>      input D until H correctly determines that its simulated D
>      *would never stop running unless aborted* then
> 
> *input D* is the actual input
> *would never stop running unless aborted*
> is the hypothetical H/D pair where H does not abort.

H is hypthetical. There is no actual decider in Sipeser's words. But
what is said about D is true about any actual input as there is no
restriction on D other than it is an input to H.

> You cannot possibly show the exact execution trace

That's right. An execution trace is too long to make without tools
that I don't have. Just remenber that absence of evidence is not
evidence of absense.

-- 
Mikko