Path: ...!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: olcott Newsgroups: comp.theory Subject: =?UTF-8?Q?Re=3A_A_simulating_halt_decider_applied_to_the_The_Peter_?= =?UTF-8?Q?Linz_Turing_Machine_description_=E2=9F=A8=C4=A4=E2=9F=A9?= Date: Fri, 31 May 2024 10:35:18 -0500 Organization: A noiseless patient Spider Lines: 192 Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Fri, 31 May 2024 17:35:19 +0200 (CEST) Injection-Info: dont-email.me; posting-host="08a73d0f9257967986a8324b25ade22a"; logging-data="2408884"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19xHFcuBt4FY2kUqrqAuhEE" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:Y8PbEmbrY4RY1ol8kRdChCJI3so= In-Reply-To: Content-Language: en-US Bytes: 9518 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 *Formalizing the Linz Proof structure* ∃H ∈ Turing_Machines ∀x ∈ Turing_Machine_Descriptions ∀y ∈ Finite_Strings such that H(x,y) = Halts(x,y) That what Linz is claiming is false. *Here is the same claim with 100% complete specificity* such that H(⟨Ĥ⟩, ⟨Ĥ⟩) != Halts(⟨Ĥ⟩, ⟨Ĥ⟩) *A quick summary of the reasoning provided below* The LHS is behavior that embedded_H is allowed to report on. The RHS is behavior that embedded_H NOT is allowed to report on. The LHS and the RHS specify different behaviors. ========== REMAINDER OF ARTICLE TRUNCATED ==========