Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: dbush Newsgroups: comp.theory Subject: Re: DDD specifies recursive emulation to HHH and halting to HHH1 Date: Sat, 29 Mar 2025 16:11:33 -0400 Organization: A noiseless patient Spider Lines: 142 Message-ID: References: <45b3405a167984b8649777fdc0804b124b21e19b@i2pn2.org> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sat, 29 Mar 2025 21:11:33 +0100 (CET) Injection-Info: dont-email.me; posting-host="d82829ff2684f0f25de37249bda61e80"; logging-data="2306565"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+ZFY5wnYOujEiIqo5+sR9k" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:CfqlvO44p+YfoQE5XJ5bC+DAAd4= Content-Language: en-US In-Reply-To: Bytes: 6670 On 3/29/2025 3:46 PM, olcott wrote: > On 3/29/2025 2:25 PM, dbush wrote: >> On 3/29/2025 3:19 PM, olcott wrote: >>> On 3/29/2025 2:01 PM, dbush wrote: >>>> On 3/29/2025 2:58 PM, olcott wrote: >>>>> On 3/29/2025 1:37 PM, dbush wrote: >>>>>> On 3/29/2025 2:15 PM, olcott wrote: >>>>>>> On 3/29/2025 4:31 AM, joes wrote: >>>>>>>> Am Fri, 28 Mar 2025 14:27:36 -0500 schrieb olcott: >>>>>>>>> On 3/28/2025 2:17 PM, dbush wrote: >>>>>>>>>> On 3/28/2025 3:02 PM, olcott wrote: >>>>>>>>>>> On 3/28/2025 1:12 PM, dbush wrote: >>>>>>>>>>>> On 3/28/2025 1:57 PM, olcott wrote: >>>>>>>>>>>>> On 3/27/2025 9:33 PM, dbush wrote: >>>>>>>>>>>>>> On 3/27/2025 10:10 PM, olcott wrote: >>>>>>>>>>>>>>> On 3/27/2025 8:24 PM, dbush wrote: >>>>>>>>>>>>>>>> On 3/27/2025 9:21 PM, olcott wrote: >>>>>>>>>>>>>>>>> On 3/27/2025 8:09 PM, dbush wrote: >>>>>>>>>>>>>>>>>> On 3/27/2025 9:07 PM, olcott wrote: >>>>>>>>>>>>>>>>>>> On 3/27/2025 7:38 PM, dbush wrote: >>>>>>>> >>>>>>>>>>>>>>>> Good, because that's all that's required for a solution >>>>>>>>>>>>>>>> to the >>>>>>>>>>>>>>>> halting problem: >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>> There are sometimes when the behavior of TM Description D >>>>>>>>>>>>>>> correctly simulated by UTM1 does not match the behavior >>>>>>>>>>>>>>> correctly >>>>>>>>>>>>>>> simulated by UTM2. >>>>>>>>>>>>>> >>>>>>>>>>>>>> Irrelevant, because to satisfy the requirements, the >>>>>>>>>>>>>> behavior of >>>>>>>>>>>>>> the described machine when executed directly must be >>>>>>>>>>>>>> reported. >>>>>>>>>>>>> >>>>>>>>>>>>> I HAVE PROVED THAT THE REQUIREMENT IS WRONG NITWIT. >>>>>>>> According to what? WE require it. YOU are answering a different >>>>>>>> question. >>>>>>>> >>>>>>>>>>>> Category error. >>>>>>>>>>>> I want to know if any arbitrary algorithm X with input Y >>>>>>>>>>>> will halt >>>>>>>>>>>> when executed directly. >>>>>>>>>>> >>>>>>>>>>> It is 100% impossible for any TM to take another executing TM >>>>>>>>>>> as its >>>>>>>>>>> input. >>>>>>>> Quit that. >>>>>>>> >>>>>>>>>> But it can take a complete description of a TM that >>>>>>>>> >>>>>>>>> Is not always a perfect proxy for the behavior of the direct >>>>>>>>> execution >>>>>>>>> of the underlying machine. >>>>>>> >>>>>>>> Uh yes it is. >>>>>>>> >>>>>>> >>>>>>> That my proof that I am correct >>>>>>> is over your head is less than >>>>>>> no rebuttal what-so-ever. >>>>>> >>>>>> The fact that such TM description can be given to a UTM which will >>>>>> exactly replicate the behavior of the described TM when executed >>>>>> directly proves otherwise is apparently over your head. >>>>>> >>>>> >>>>> One cannot correctly ignore the effect that a specified >>>>> pathological relationship has between its simulator >>>>> and its input on the behavior of this input. >>>>> >>>> >>>> All it means is that HHH does not correctly map DDD to 1 as per the >>>> requirements: >>>> >>> >>> int sum(int x, int y) { return x + y; } >>> In the same way that sum(2,3) cannot be mapped to 7. >> >> It can, it just wouldn't meet the requirements of the mathematical >> "sum" function. >> > > int DD() > { >   int Halt_Status = HHH(DD); >   if (Halt_Status) >     HERE: goto HERE; >   return Halt_Status; > } > > Likewise if HHH reported on the behavior of the > directly executed DD It would be behaving as required: 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 > >>> >>> Computations apply a set of finite string transformation >>> rules to an input finite string to derive an output finite >>> string. >> >> And if the mapping in question is not computable, no computation can >> do it. >> > > The same way that the sum(2,3) cannot report 7. > If it is required to report 7 then the requirement is wrong. It's not wrong if the requirement is to compute the sum of the two input numbers plus two. > >>> >>> The semantic property that input DDD specifies to HHH >>> is non-halting. >>> >> >> int greater_than_5(int x) >> { >>      return 1; >> } >> >> Similarly, the semantic property that input 3 specifies to >> greater_than_5 is a number greater than 5. > > The name of a function is not binding on its algorithm. > It is in this case, and since the input to greater_than_5 specifies a number greater than 5, it is correct to report this.