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: Tue, 6 May 2025 20:45:59 -0500
Organization: A noiseless patient Spider
Lines: 134
Message-ID: <vvee0n$89u0$2@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>
 <vvckjd$2krkf$1@dont-email.me> <vvd8o9$34l9k$4@dont-email.me>
 <b2aa4a06c49960ef30db2f18da40a9319808fce5@i2pn2.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 07 May 2025 03:46:00 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="ee5137430f56269cd3e6381ddf24cf46";
	logging-data="272320"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19Kbmgn/9FaZQscfZpE1Ud3"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:xq2s0YhKSxUWANwA04SI+A6HgOU=
In-Reply-To: <b2aa4a06c49960ef30db2f18da40a9319808fce5@i2pn2.org>
X-Antivirus: Norton (VPS 250506-6, 5/6/2025), Outbound message
X-Antivirus-Status: Clean
Content-Language: en-US

On 5/6/2025 5:43 PM, Richard Damon wrote:
> On 5/6/25 11:10 AM, olcott wrote:
>> On 5/6/2025 4:26 AM, Mikko wrote:
>>> On 2025-05-05 18:14:25 +0000, olcott said:
>>>
>>>> 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.
>>>
>>> Irrelevant. One of the boolean values (the one not returned) is the
>>> right one as can be determined e.g. with an UTM.
>>>
>>>>> You only get something that appears that way when a false 
>>>>> assumption is made, namely that the halting function is computable.
>>>>
>>>> The mapping from the input HHH(DD) finite string of
>>>> machine code to DOES SPECIFY RECURSIVE EMULATION
>>>> THAT WOULD PREVENT DD FROM EVER HALTING.
>>>
>>> No, it does not. HHH returns 0 and DD halts.
>>>
>>
>> You can't show the detailed steps of the execution
>> trace of DD emulated by HHH (according to the rules
>> of the x86 language) where DD halts because you are wrong.
> 
> Because a trace of DD correctly emulatd by HHH doesn't exist as HHH 
> doesn't correctly emulate DD
> 

Show what the execution trace of DD emulated by HHH
according to the rules of the x86 language should be

_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