Path: ...!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: olcott Newsgroups: comp.theory,sci.logic Subject: Re: D correctly simulated by pure function H cannot possibly reach its, own line 06 --- Linz Date: Sun, 26 May 2024 14:14:14 -0500 Organization: A noiseless patient Spider Lines: 77 Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sun, 26 May 2024 21:14:14 +0200 (CEST) Injection-Info: dont-email.me; posting-host="b67ec24a85de95a55e6b4d0cc81926c3"; logging-data="3715595"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/hqrhpUqrFjOqdojX6we88" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:s/2ljrQBIMDfxt2D/DMIVPRM+x8= Content-Language: en-US In-Reply-To: Bytes: 5306 On 5/26/2024 12:48 PM, Richard Damon wrote: > On 5/26/24 1:26 PM, olcott wrote: >> On 5/26/2024 12:16 PM, Richard Damon wrote: >>> On 5/26/24 1:01 PM, olcott wrote: >>>> On 5/26/2024 11:31 AM, Richard Damon wrote: >>>>> On 5/26/24 10:13 AM, olcott wrote: >>>>>> On 5/26/2024 6:43 AM, Richard Damon wrote: >>>>>> >>>>>> typedef int (*ptr)();  // ptr is pointer to int function in C >>>>>> 00       int H(ptr p, ptr i); >>>>>> 01       int D(ptr p) >>>>>> 02       { >>>>>> 03         int Halt_Status = H(p, p); >>>>>> 04         if (Halt_Status) >>>>>> 05           HERE: goto HERE; >>>>>> 06         return Halt_Status; >>>>>> 07       } >>>>>> 08 >>>>>> 09       int main() >>>>>> 10       { >>>>>> 11         H(D,D); >>>>>> 12         return 0; >>>>>> 13       } >>>>>> >>>>>> >>>>>>> Because, as I have said, the answer and reasoning changes >>>>>>> depending on what you acknowledged are the implications of your >>>>>>> stipulations. For instance, if your actual understanding of being >>>>>>> a "Pure Function" is that the program is the equivalent of a >>>>>>> Turing Machine, then we need to add a strictness to the >>>>>>> definition that isn't normally used for just "Pure Functions", >>>>>>> like accessing value of registers like the program counter or >>>>>>> stack pointer might not be allowed in some cases. (which breaks >>>>>>> you H). >>>>>>> >>>>>> >>>>>> Since we can see (and you already agreed) that D correctly simulated >>>>>> by pure simulator H remains stuck in infinite recursive simulation >>>>>> then >>>>>> we also know that D never reaches its own line 06 and halts in less >>>>>> than an infinite number of correctly simulated steps. >>>>> >>>>> But it depends on what H actually does, which you refuse to agree to. >>>>> >>>> >>>> When I specify that D is correctly simulated by pure function H, that >>>> means that H is a pure simulator that stops simulating D after some >>>> finite number of correctly simulated steps. There is absolutely nothing >>>> else that needs to be known about H besides this. >>>> >>> >>> And, do you accept that this exact description means that H is NOT >>> the computational equivalent of a Turing Machine, and that this >>> simulation doesn't prove that its input is not a non-halting program? >>> >> >> In other words you are saying that it is 100% totally impossible to >> adapt an actual UTM so that it stops simulating after a finite number of >> steps. > > Yep, at least and have it still be a UTM. > When Ĥ is applied to ⟨Ĥ⟩ Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞ Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn When we see that ⟨Ĥ⟩ ⟨Ĥ⟩ correctly simulated by embedded_H in an infinite number of steps cannot possibly reach its own simulated final state of ⟨Ĥ.qn⟩ and halt then we correctly deduce that the same thing applies when simulating halt decider embedded_H correctly simulates less than an infinite number of steps of ⟨Ĥ⟩ ⟨Ĥ⟩. -- Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer