| Deutsch English Français Italiano |
|
<v3ek0l$2maau$1@dont-email.me> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Mikko <mikko.levanto@iki.fi> Newsgroups: comp.theory Subject: =?utf-8?Q?Re:_A_simulating_halt_decider_applied_to_the_The_Peter_Linz_Turing_Machine_description_=E2=9F=A8=C4=A4=E2=9F=A9?= Date: Sat, 1 Jun 2024 10:52:53 +0300 Organization: - Lines: 177 Message-ID: <v3ek0l$2maau$1@dont-email.me> References: <v2nsvh$1rd65$2@dont-email.me> <v30vp3$3s4od$1@dont-email.me> <v321o0$28n58$1@i2pn2.org> <v3255k$2pkb$2@dont-email.me> <v326fd$28n59$2@i2pn2.org> <v327h8$3a17$1@dont-email.me> <v328l1$28n58$2@i2pn2.org> <v329t8$3mh0$2@dont-email.me> <v32ait$28n58$4@i2pn2.org> <v32bvc$48pj$1@dont-email.me> <v32cko$2937i$1@i2pn2.org> <v32nsa$6fo3$1@dont-email.me> <v32tfs$29dee$1@i2pn2.org> <v331mf$84p2$1@dont-email.me> <v332ci$29def$2@i2pn2.org> <v33790$8u5p$1@dont-email.me> <v337r0$29dee$2@i2pn2.org> <v338c5$94g8$1@dont-email.me> <v339kr$29dee$3@i2pn2.org> <v33aj7$9f3u$1@dont-email.me> <v33bo5$29def$4@i2pn2.org> <v33dt7$dlnv$1@dont-email.me> <v33f6d$29dee$4@i2pn2.org> <v33g9j$e3ug$1@dont-email.me> <v33gss$29def$6@i2pn2.org> <v33hbf$e6qn$1@dont-email.me> <v34fg0$2bb65$2@i2pn2.org> <v36pgt$12lh7$1@dont-email.me> <v379la$159q4$2@dont-email.me> <v398hu$1j7to$1@dont-email.me> <v39ue9$1mtd9$3@dont-email.me> <v3chls$280e0$1@dont-email.me> <v3cqnm$29gdk$1@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sat, 01 Jun 2024 09:52:54 +0200 (CEST) Injection-Info: dont-email.me; posting-host="6553536d1ebba9134c01b65a06740e6f"; logging-data="2828638"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/kz0RWpLD9raG3qFU+JnH+" User-Agent: Unison/2.2 Cancel-Lock: sha1:zNZ/esT9Vp1Ozf/bX80+yMlJcXc= Bytes: 8998 On 2024-05-31 15:35:18 +0000, olcott said: > On 5/31/2024 8:00 AM, Mikko wrote: >> On 2024-05-30 13:20:09 +0000, olcott said: >> >>> On 5/30/2024 2:06 AM, Mikko wrote: >>>> On 2024-05-29 13:13:13 +0000, olcott said: >>>> >>>>> On 5/29/2024 3:37 AM, Mikko wrote: >>>>>> On 2024-05-28 11:34:24 +0000, Richard Damon said: >>>>>> >>>>>>> On 5/27/24 10:59 PM, olcott wrote: >>>>>>>> On 5/27/2024 9:52 PM, Richard Damon wrote: >>>>>>>>> On 5/27/24 10:41 PM, olcott wrote: >>>>>>>>>> On 5/27/2024 9:23 PM, Richard Damon wrote: >>>>>>>>>>> On 5/27/24 10:01 PM, olcott wrote: >>>>>>>>>>>> On 5/27/2024 8:24 PM, Richard Damon wrote: >>>>>>>>>>>>> On 5/27/24 9:04 PM, olcott wrote: >>>>>>>>>>>> >>>>>>>>>>>>>>>> I totally do. Can you please write down the >>>>>>>>>>>>>>>> "completely specified state transition/tape operation table." >>>>>>>>>>>>>>>> of this specific (thus uniquely identifiable) machine I would >>>>>>>>>>>>>>>> really like to see it. >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> But it was proven that no such machine exists! >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> Remember, the proof starts with the hypothetical that such a machine >>>>>>>>>>>>>>> exists. Such a machine WOULD HAVE a completely specified state >>>>>>>>>>>>>>> transition/tape operation table. >>>>>>>>>>>>>>> >>>>>>>>>>>>>> >>>>>>>>>>>>>> That is not what you said. >>>>>>>>>>>>>> >>>>> There doesn't need to be a unique finite string, but it is a 100% >>>>>>>>>>>>>> >>>>> completely specified state transition/tape operation table. >>>>>>>>>>>>>> >>>>>>>>>>>>>> "a 100% completely specified state transition/tape operation table" >>>>>>>>>>>>>> of a non-existent machine. >>>>>>>>>>>>> >>>>>>>>>>>>> Right, by presuming that you have a Turing Machine, you have a >>>>>>>>>>>>> completly specified state transition/tape operation table. >>>>>>>>>>>>> >>>>>>>>>>>>> You may not KNOW what that table is if you don't know what the exact >>>>>>>>>>>>> machine is, but you know it exists. >>>>>>>>>>>> >>>>>>>>>>>> >>> But it was proven that no such machine exists! >>>>>>>>>>>> > ... but you know it exists. >>>>>>>>>>>> >>>>>>>>>>>> >>> But it was proven that no such machine exists! >>>>>>>>>>>> > ... but you know it exists. >>>>>>>>>>>> >>>>>>>>>>>> >>> But it was proven that no such machine exists! >>>>>>>>>>>> > ... but you know it exists. >>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> Really, then show that one exists! >>>>>>>>>>> >>>>>>>>>> >>>>>>>>>> *I am quoting your words. You did contradict yourself* >>>>>>>>>> *I am quoting your words. You did contradict yourself* >>>>>>>>>> *I am quoting your words. You did contradict yourself* >>>>>>>>>> *I am quoting your words. You did contradict yourself* >>>>>>>>>> *I am quoting your words. You did contradict yourself* >>>>>>>>>> *I am quoting your words. You did contradict yourself* >>>>>>>>>> *I am quoting your words. You did contradict yourself* >>>>>>>>>> *I am quoting your words. You did contradict yourself* >>>>>>>>>> *I am quoting your words. You did contradict yourself* >>>>>>>>>> *I am quoting your words. You did contradict yourself* >>>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> Really, where did I say that H exists? >>>>>>>>> >>>>>>>>> I said that if a Turing Machine exists, then its transition table does too. >>>>>>>>> >>>>>>>> >>>>>>>> OK my mistake this time. I did not take into account the full context. >>>>>>>> I will go back an read the Linz proof and see if he said anything >>>>>>>> about a specific machine. >>>>>>> >>>>>>> Read the DEFINITION of the problem. He talks about "a" machine. Using a >>>>>>> singular article means you are working with just one. >>>>>>> >>>>>>> >>>>>>> Taking stuff out of context is a common problem with you, when you >>>>>>> don't understand something, you just make up what it must mean, and >>>>>>> stick to that. That isn't the way to learn. >>>>>>> >>>>>>> >>>>>>>> >>>>>>>> None of the proofs ever try to show that there exists one machine that >>>>>>>> gets the wrong answer. They are always at least trying to prove that no >>>>>>>> machine of the infinite set of machine gets the right answer. >>>>>>>> >>>>>>> >>>>>>> What I see, is they always start with a prototypical single machine, >>>>>>> and show that it gets the answer wrong, and then they use categorical >>>>>>> logic to say that we can do this same thing for all of them. >>>>>> >>>>>> It is possible to formulate the claim and proof so that H is an universally >>>>>> quantified variable. But the usual way is apparently equally good for the >>>>>> target audience. >>>>>> >>>>> >>>>> *Formalizing the Linz Proof structure* >>>>> ∃H ∈ Turing_Machines >>>>> ∀x ∈ Turing_Machines_Descriptions >>>>> ∀y ∈ Finite_Strings >>>>> such that H(x,y) = Halts(x,y) >>>> >>>> That is not a proof structure. That is the counter-hypothesis of Linz' proof. >>>> Also note that both x and y are finite strings. >>>> >>> >>> The above is what Linz is claiming evaluates to false, he says >>> there is no such H. >> >> Yes, and proves the claim. >> >>> A decider computes the mapping from finite string inputs to >>> its own accept or reject state. >> >> An existing decider. >> >>> A decider does not and cannot compute the mapping from Turing_Machine >>> inputs to its own accept or reject state. >> >> An exsiting decider. >> > > When Ĥ is applied to ⟨Ĥ⟩ > Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞ > Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn Of those two lines one is false. As embedded_H is a copy of H both lines imply that H is not a halt decider. > *Formalizing the Linz Proof structure* > ∃H ∈ Turing_Machines > ∀x ∈ Turing_Machine_Descriptions > ∀y ∈ Finite_Strings > such that H(x,y) = Halts(x,y) As already noted, the above is not a part of a proof structure. > That <is> what Linz is claiming is false. > *Here is the same claim with 100% complete specificity* > such that H(⟨Ĥ⟩, ⟨Ĥ⟩) != Halts(⟨Ĥ⟩, ⟨Ĥ⟩) That does not make sense. Every H such that H(⟨Ĥ⟩, ⟨Ĥ⟩) != Halts(⟨Ĥ⟩, ⟨Ĥ⟩) is uninteresting. > *A quick summary of the reasoning provided below* > The LHS is behavior that embedded_H is allowed to report on. There is no restrictions on what embedded_H is allowed to report on. The only reauirement is that embedded_H has the same transition rules as H. Therefore embedded_H reports the same as H, whether allowed or not. > The RHS is behavior that embedded_H NOT is allowed to report on. > The LHS and the RHS specify different behaviors. You have not shown anything with behaviours as LHS and RHS. > Please to not reply here instead reply at the end of my proof > after all of the steps have been presented. Not a reasonable request. Correctness of a step of proof does not depend on what follows. If one step is erroneous the rest is irrelevant. -- Mikko