Path: ...!weretis.net!feeder9.news.weretis.net!i2pn.org!i2pn2.org!.POSTED!not-for-mail From: Richard Damon Newsgroups: comp.theory,sci.logic Subject: Re: D correctly simulated by H cannot possibly halt --- templates and infinite sets Date: Tue, 28 May 2024 23:38:43 -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, 29 May 2024 03:38:43 -0000 (UTC) Injection-Info: i2pn2.org; logging-data="2526408"; mail-complaints-to="usenet@i2pn2.org"; posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg"; User-Agent: Mozilla Thunderbird In-Reply-To: Content-Language: en-US X-Spam-Checker-Version: SpamAssassin 4.0.0 Bytes: 6655 Lines: 158 On 5/28/24 10:23 PM, olcott wrote: > On 5/28/2024 9:04 PM, Richard Damon wrote: >> On 5/28/24 12:16 PM, olcott 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       } >>> >>> When Ĥ is applied to ⟨Ĥ⟩ >>> Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞ >>> Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn >>> >>> *Formalizing the Linz Proof structure* >>> ∃H  ∈ Turing_Machines >>> ∀x  ∈ Turing_Machines_Descriptions >>> ∀y  ∈ Finite_Strings >>> such that H(x,y) = Halts(x,x) >> >> But since for x being the description of the H^ built from that H and >> y being the same, it turns out that no matter what answer H gives, it >> will be wrong. >> > > We have not gotten to that point yet this post is so that > you can fully understand what templates are and how they work. But note, x, being a Turing Machine, is NOT a "template" And H, isn't a "set of Turing Machines", but an arbitrary member of that set, so all we need to do is find a single x, y, possible determined as a function of H (so, BUILT from a template, but not a template themselves) that shows that particular H was wrong. That is basically what Linz does. Given a SPECIFIC (but arbitary) H, we can construct a specific H^ built from a template from H, that that H can not get right. All the other H's might get this input right, but we don't care, we have shown that for every H we > >> (And I think you have an error in your reference to Halts, I think you >> mean Halts(x,y) not Halts(x,x) >> > > Yes good catch. I was trying to model embedded_H / ⟨Ĥ⟩ > and then changed my mind to make it more general. > >>> >>> *Here is the same thing applied to H/D pairs* >>> ∃H ∈ C_Functions >>> ∀D ∈ x86_Machine_Code_of_C_Functions >>> such that H(D,D) = Halts(D,D) >> >> Not the same thing. >> ∃H ∈ C_Functions >> is not equivalent to >> ∃H  ∈ Turing_Machines >> >> as there are many C_Functions that are not the equivalent of Turing >> Machines. >> > > The whole purpose here is to get you to understand what > templates are and how they reference infinite sets. > But the problem is that even in your formulation, H and D are, when doing the test, SPECIFIC PROGRAMS and not "templates" as Halts is defined on the domain of PROGRAMS. Similarly, a "Template" doesn't have a specific set of x86_Machine_Code_of_C_function, at least not one with defined behavior since if it tries to reference code outside of itself, then Halts of that just isn't defined, only Halts of that code + the specific machine deciding it. >> >>> >>> In both cases infinite sets are examined to see >>> if any H exists with the required properties. >>> >> >> Yes, but the logic of Turing Machines looks at them one at a time, and >> the input is a FULL INDEPENDENT PROGRAM. >> > > ∃H  ∈ Turing_Machines > That does not look at one machine it looks as an infinite set of > machines. I am very happy to find out that you were not playing head > games. Linz actually used the words that you referred to. while the ∃H part can create a set of machines, each element of that set is INDIVIDUALLY TESTED in the following conditions, so, when we get to your test H(x,y) = Halts(x,x), each of H, x, y are individual members of the set, and we THEN collect the set of all of them. If we try to say ∃x ∈ Natural Numbers, such that x+x = 3 we can't say that x is both 1 and 2 and thus as a set meet the requirement. For the conditions, each qualifier select a single prospective element, and those are tested to see if that meet the requirement. > >> I'm not sure what you can define your computation system to be >> actually based on, and what its supposed use is, since your 'decider' >> and 'input' are so intertwined. >> > > The whole purpose here is to get you to understand what > templates are and how they reference infinite sets. I understand how they work, the problem is you think they somehow change the meaning of the final condition. H(D,D) == Halts(D,D) doesn't mean that we get to look at some other choice of H with some other choice of D to provide the D for Halts then what H was given. > >> And your supposed algorithm just doesn't work when you try to make you >> system "Turing Complete" by letting D have the ability to have a COPY >> of H, and being able to make copies of its input, like real Turing >> machines can. >> > > The whole purpose here is to get you to understand what > templates are and how they reference infinite sets. > > All the other issues are for another different post. > And you are just showing that YOU don't understand it, as it doesn't get you anywhere closer to you goal. The qualifier step is STILL done with a single specific element from each of the sets. Since for every element of the first set (your ∃H) there exists an input that that particular H will get wrong, you can't use the "infinite set of H/D" to argue that it was right. All that does is prove that their does NOT exist an H that meets the requirements.