Path: news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!news.quux.org!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail From: Richard Damon Newsgroups: comp.theory Subject: Re: Halting Problem: What Constitutes Pathological Input Date: Wed, 7 May 2025 06:40:21 -0400 Organization: i2pn2 (i2pn.org) Message-ID: References:

MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Wed, 7 May 2025 11:13:26 -0000 (UTC) Injection-Info: i2pn2.org; logging-data="3507609"; mail-complaints-to="usenet@i2pn2.org"; posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg"; User-Agent: Mozilla Thunderbird X-Spam-Checker-Version: SpamAssassin 4.0.0 In-Reply-To: Content-Language: en-US On 5/6/25 10:44 PM, olcott wrote: > On 5/6/2025 9:34 PM, Richard Damon wrote: >> On 5/6/25 9:47 PM, olcott wrote: >>> 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 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. >>>> >>>> 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 >>> >> >> Since HHH doesn't do that, > > and you cannot possibly point out what the correct > steps should be because you know that you are lying. Then you need to show me how to draw a round square. Your HHH corrrectly emulating DD is just as impossible. I could show you a correct emulation of the input, after fixing your mistake in omitting most of the code, but why should I do that, as it is AFTER fixing your mistakes. All you are doing is proving you are just an idiot that doesn't know what he is doing. > > _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] > > WHich isn't a valid input by itself, as it isn't a complete program, and when you add in your stupulated Halt7.c you have defined your Halt7.c as a program that doesn't do what you claim. First you need to show me a definition of a HHH that actually does a correct emulation, but also gives the answer you claim it is correct to do so. The problem you have is that you can't do that, as it is impossible, something you yourself have proven, but just don't understand that you have do so.