Path: ...!weretis.net!feeder9.news.weretis.net!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: Thu, 8 May 2025 07:20:28 -0400 Organization: i2pn2 (i2pn.org) Message-ID: <27e0f87daada3cedc00656b074b24248ef242fe8@i2pn2.org> References: <5b84f927f8052f5392b625cef9642140d439d1c7@i2pn2.org> <1a99b2ee77f8c0d1ff37e5febb47c5be17b2d4fb@i2pn2.org> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Thu, 8 May 2025 11:22:29 -0000 (UTC) Injection-Info: i2pn2.org; logging-data="3647871"; mail-complaints-to="usenet@i2pn2.org"; posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg"; User-Agent: Mozilla Thunderbird X-Spam-Checker-Version: SpamAssassin 4.0.0 Content-Language: en-US In-Reply-To: Bytes: 12995 Lines: 307 On 5/8/25 12:37 AM, olcott wrote: > On 5/7/2025 10:30 PM, Richard Damon wrote: >> On 5/7/25 10:50 AM, olcott wrote: >>> On 5/7/2025 6:12 AM, Richard Damon wrote: >>>> On 5/6/25 10:40 PM, olcott wrote: >>>>> On 5/6/2025 6:00 PM, Richard Damon wrote: >>>>>> On 5/6/25 1:54 PM, olcott wrote: >>>>>>> On 5/6/2025 6:06 AM, Richard Damon wrote: >>>>>>>> On 5/5/25 10:29 PM, olcott wrote: >>>>>>>>> On 5/5/2025 8:06 PM, Richard Damon wrote: >>>>>>>>>> On 5/5/25 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. >>>>>>>>>>> >>>>>>>>>>> int DD() >>>>>>>>>>> { >>>>>>>>>>>    int Halt_Status = HHH(DD); >>>>>>>>>>>    if (Halt_Status) >>>>>>>>>>>      HERE: goto HERE; >>>>>>>>>>>    return Halt_Status; >>>>>>>>>>> } >>>>>>>>>> >>>>>>>>>> Which isn't a program until you include the SPECIFIC HHH that >>>>>>>>>> it refutes, and thus your talk about correctly emulated by HHH >>>>>>>>>> is just a lie. >>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> 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. >>>>>>>>>>> >>>>>>>>>> >>>>>>>>>> And *ITS INPUT*, for the HHH that answers 0, is the >>>>>>>>>> representation of a program >>>>>>>>> >>>>>>>>> Not at all. This has always been stupidly wrong. >>>>>>>>> The input is actually a 100% perfectly precise >>>>>>>>> sequence of steps. With pathological self-reference >>>>>>>>> some of these steps are inside the termination analyzer. >>>>>>>>> >>>>>>>> >>>>>>>> Can't be, as the input needs to be about a program, which must, >>>>>>>> by the definition of a program, include all its algorithm. >>>>>>>> >>>>>>>> Yes, there are steps that also occur in the termination >>>>>>>> analyzer, but they have been effectively copied into the program >>>>>>>> the input describes. >>>>>>>> >>>>>>>> Note, nothing says that the representation of the program has to >>>>>>>> be an assembly level description of it. It has to be a complete >>>>>>>> description, that 100% defines the results the code will >>>>>>>> generate (and if it will generate) but it doesn't need to be the >>>>>>>> exact assembly code, >>>>>>>> >>>>>>>> YOU even understand that, as you present the code as "C" code, >>>>>>>> which isn't assembly. >>>>>>>> >>>>>>>> What you forget is that the input program INCLUDES as its >>>>>>>> definiton, all of the code it uses, and thus the call to the >>>>>>>> decider it is built on includes that code into the decider, and >>>>>>>> that is a FIXED and DETERMINDED version of the decider, the one >>>>>>>> that THIS version of the input is designed to make wrong. >>>>>>>> >>>>>>>> This doesn't change when you hypothosize a different decider >>>>>>>> looking at THIS input. >>>>>>>> >>>>>>> >>>>>>> >>>>>> 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 >>>>>>> >>>>>>> *would never stop running unless aborted* >>>>>>> Refers to a hypothetical HHH/DD pair of the same HHH that >>>>>>> DD calls except that this hypothetical HHH never aborts. >>>>>>> >>>>>> >>>>>> Right, but a correct simulation of D does halt, >>>>> >>>>> How the Hell is breaking the rules specified >>>>> by the x86 language possibly correct? >>>> >>>> Right, how is HHH correct to abort its emulation? >>>> >>>>> >>>>> I could say that the sum of 5 + 7 is a dirty sock >>>>> according to the rules of random gibberish. >>>> >>>> Yes, and you do, because most of what you say IS "random gibberish" >>>> >>>>> >>>>> When I go by the rules of arithmetic I am proved >>>>> wrong. >>>> >>>> But the problem is you don't do that, but think you are because you >>>> don't know the rules. >>>> >>>>> >>>>> DD emulated by HHH according to the rules >>>>> of the x86 language that specify the HHH also >>>>> emulates itself emulating DD >>>> >>>> No it isn't. >>>> >>>>> >>>>> until HHH determines that for the hypothetical >>>>> HHH/DD pair where the hypothetical HHH never >>>>> aborts DD would never stop running. >>>> >>>> Which isn't part of the rules. >>>> >>>>> >>>>> >>>>>      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 >>>>> >>>>>      *would never stop running unless aborted* >>>>>      refers to the hypothetical HHH/DD pair where >>>>>      HHH never aborts its simulation. >>>>> >>>> >>>> That second paragraph is a lie and a misquote. >>>> >>> >>> I still have the original email. >>> Ben has already verified this. >>> This is an actual cut-and-paste of the words >>> >>> *From Thursday, October 13, 2022 12:16 PM email* >>> 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 H can abort its simulation of D and correctly >>> report that D specifies a non-halting sequence of configurations. >>> >>> In that email he requested that I surround that paragraph with >>> >>> >>> >>> I also posted Date: Thu, 13 Oct 2022 11:46:22 -0500 >>> [Michael Sipser of MIT validates the notion of a simulating halt >>> decider] >>> >>> that contains the exact same word-for-word paragraph >>> https://al.howardknight.net/? >>> STYPE=msgid&MSGI=%3Cti9fd0%241unl%241%40gioia.aioe.org%3E >> ========== REMAINDER OF ARTICLE TRUNCATED ==========