Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: Mikko Newsgroups: comp.theory Subject: Re: Halt Deciders must be computable functions --- dbush was always wrong Date: Mon, 24 Mar 2025 10:00:38 +0200 Organization: - Lines: 90 Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Mon, 24 Mar 2025 09:00:39 +0100 (CET) Injection-Info: dont-email.me; posting-host="3edb2b95d4b8e02638e23f2f474fbe8a"; logging-data="490645"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18Mhv4IhKauKUshYDltC+/H" User-Agent: Unison/2.2 Cancel-Lock: sha1:khr7/hbKRJONlMKN9iYB4RS4VJY= Bytes: 5687 On 2025-03-23 20:08:25 +0000, olcott said: > On 3/23/2025 4:49 AM, Mikko wrote: >> On 2025-03-22 15:47:03 +0000, olcott said: >> >>> On 3/22/2025 9:57 AM, Mikko wrote: >>>> On 2025-03-21 15:25:09 +0000, olcott said: >>>> >>>>> On 3/21/2025 10:00 AM, olcott wrote: >>>>>> On 3/21/2025 9:44 AM, dbush wrote: >>>>>>> On 3/17/2025 11:29 PM, olcott wrote: >>>>>>>> On 3/17/2025 8:25 PM, dbush wrote: >>>>>>>>> On 3/17/2025 9:18 PM, olcott wrote: >>>>>>>>>> On 3/17/2025 7:48 PM, dbush wrote: >>>>>>>>>>> On 3/17/2025 8:44 PM, olcott wrote: >>>>>>>>>>>> On 3/17/2025 7:22 PM, dbush wrote: >>>>>>>>>>>>> On 3/17/2025 8:18 PM, olcott wrote: >>>>>>>>>>>>>> On 3/17/2025 7:00 PM, dbush wrote: >>>>>>>>>>>>>>> On 3/17/2025 7:51 PM, olcott wrote: >>>>>>>>>>>>>>>> On 3/17/2025 5:15 PM, dbush wrote: >>>>>>>>>>>>>>>>> On 3/17/2025 6:10 PM, olcott wrote: >>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>> The halt decider does not and cannot possibly >>>>>>>>>>>>>>>>>> compute the mapping from the actual behavior >>>>>>>>>>>>>>>>>> of an executing process. >>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> No one claimed it should.  What it must do is determine what would >>>>>>>>>>>>>>>>> happen in the hypothetical case that a direct execution is done. >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> It can only do that when it assumes that the behavior >>>>>>>>>>>>>>>> specified by the semantics of its input machine language >>>>>>>>>>>>>>>> exactly matches this behavior. Its only basis is this >>>>>>>>>>>>>>>> input finite string. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> i.e. the semantics of the x86 language when those actual instructions >>>>>>>>>>>>>>> are actually executed on an actual x86 processor. >>>>>>>>>>>>>>> >>>>>>>>>>>>>> >>>>>>>>>>>>>> A termination analyzer has no access to that. >>>>>>>>>>>>> >>>>>>>>>>>>> The input is required to be a complete description of the program that >>>>>>>>>>>>> can be used to determine its full behavior.  In the case of DD, that >>>>>>>>>>>>> description is the code of the function DD, the code of the function >>>>>>>>>>>>> HHH, and everything that HHH calls down to the OS level. >>>>>>>>>>>> >>>>>>>>>>>> It does do that and this behavior does specify >>>>>>>>>>> >>>>>>>>>>> Halting behavior when executed directly, which is what is to be >>>>>>>>>>> reported on as per the requirements: >>>>>>>>>>> >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> It has always been incorrectly assumed that the input >>>>>>>>>> finite string is a perfect proxy for the behavior >>>>>>>>>> of the direct execution. >>>>>>>>> >>>>>>>>> False.  The input finite string is REQUIRED to be a perfect proxy for >>>>>>>>> direct execution, as per the requirements: >>>>>>>>> >>>>>>>> >>>>>>>> It looks like you simply don't understand that a >>>>>>>> counter-factual requirement is necessarily incorrect. >>>>>>> >>>>>>> Category error.  Requirements can't be false.  They can however be >>>>>>> impossible to satisfy. >>>>>>> >>>>>> >>>>>> When the definition of a [HALT decider] contradicts the definition of a >>>>>> [decider] in the same field of inquiry at least one of them is >>>>>> incorrect. >>>> >>>> No, there is nothing incorrect there. It simply means a halpt decider >>>> is not a decider, >>> >>> It has always been stipulated that a [halt decider] is a type >>> of [decider]. This means that every halt decider only has the >>> behavior that its finite string input specifies as its only basis. >> >> No, it has not. "Halting decider" can be defined without mentioning >> "decider" and some authors do so. > > I forgot that the notion of computable function already proves my point Maybe, if you have a point. But it does not prove your false claim above. -- Mikko