Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: olcott Newsgroups: comp.theory Subject: Re: Halting Problem: What Constitutes Pathological Input Date: Tue, 6 May 2025 10:10:01 -0500 Organization: A noiseless patient Spider Lines: 121 Message-ID: References:

MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Tue, 06 May 2025 17:10:02 +0200 (CEST) Injection-Info: dont-email.me; posting-host="4d3877b25e07ae675aebb853b858fd37"; logging-data="3298612"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+WcPEQD1nkug/IwONlxrev" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:d2OVP1cHIRDD5pSQkHLhpr4ZNAc= Content-Language: en-US X-Antivirus: Norton (VPS 250506-2, 5/6/2025), Outbound message In-Reply-To: X-Antivirus-Status: Clean 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 with input Y: >>>>> >>>>> A solution to the halting problem is an algorithm H that computes the >>>>> following mapping: >>>>> >>>>> (,Y) maps to 1 if and only if X(Y) halts when executed directly >>>>> (,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. _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