Path: 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: Wed, 7 May 2025 10:36:39 -0500
Organization: A noiseless patient Spider
Lines: 137
Message-ID: <vvfum7$130t3$6@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> <vvf9td$ujn3$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 17:36:40 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="ee5137430f56269cd3e6381ddf24cf46";
	logging-data="1147811"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19XX28EnOLPMGbvQKEhq4KY"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:x6ZusTwewnTtJBIB+2VLDQhvU/4=
In-Reply-To: <vvf9td$ujn3$1@dont-email.me>
Content-Language: en-US
X-Antivirus-Status: Clean
X-Antivirus: Norton (VPS 250507-2, 5/7/2025), Outbound message

On 5/7/2025 4:42 AM, Mikko wrote:
> 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.
> 

The execution trace of DD correctly emulated by HHH
keeps repeating the first five instructions until
HHH correctly determines:

*simulated D would never stop running unless aborted*
In other words HHH predicts what the behavior of DD
*would be* if HHH was a UTM.

_DD()
[00002133] 55         push ebp      ; housekeeping
[00002134] 8bec       mov ebp,esp   ; housekeeping
[00002136] 51         push ecx      ; make space for local
[00002137] 6833210000 push 00002133 ; push DD
[0000213c] e882f4ffff call 000015c3 ; call HHH(DD)
[00002141] 83c404     add esp,+04
[00002144] 8945fc     mov [ebp-04],eax
[00002147] 837dfc00   cmp dword [ebp-04],+00
[0000214b] 7402       jz 0000214f
[0000214d] ebfe       jmp 0000214d
[0000214f] 8b45fc     mov eax,[ebp-04]
[00002152] 8be5       mov esp,ebp
[00002154] 5d         pop ebp
[00002155] c3         ret
Size in bytes:(0035) [00002155]


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