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