Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
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_--_key_d?=
 =?UTF-8?Q?etails?=
Date: Sun, 2 Jun 2024 08:21:56 -0500
Organization: A noiseless patient Spider
Lines: 103
Message-ID: <v3hrlk$3bkv5$3@dont-email.me>
References: <v2nsvh$1rd65$2@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>
 <v3ek0l$2maau$1@dont-email.me> <v3fbme$2qsgd$1@dont-email.me>
 <v3fqkp$2o13h$7@i2pn2.org> <v3fsm0$2uah1$1@dont-email.me>
 <v3h7pv$38up4$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 02 Jun 2024 15:21:57 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="3e1a2626012d6c432c11247ed1bf0353";
	logging-data="3527653"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18wap53DXQCZ4GQ1fEEr2dC"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:jKFzfqB3MbWRTWEybXpeMs8UKqg=
In-Reply-To: <v3h7pv$38up4$1@dont-email.me>
Content-Language: en-US
Bytes: 6517

On 6/2/2024 2:42 AM, Mikko wrote:
> On 2024-06-01 19:26:55 +0000, olcott said:
> 
>> On 6/1/2024 1:52 PM, joes wrote:
>>> Am Sat, 01 Jun 2024 09:37:01 -0500 schrieb olcott:
>>>> On 6/1/2024 2:52 AM, Mikko wrote:
>>>>> On 2024-05-31 15:35:18 +0000, olcott said:
>>>
>>>>>> *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.
>>>>
>>>> embedded_H is only allowed to report on the behavior that its finite
>>>> string Turing Machine Description specifies to a UTM.
>>>>
>>>> embedded_H <is> a UTM except that it stops simulating and reports
>>>> non-halting as soon as it correctly recognizes a non-halting behavior
>>>> pattern that is specified by its input.
>>> "Except". So it is not an UTM.
>>>
>>>> When Ĥ is applied to ⟨Ĥ⟩
>>>> Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
>>>> Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>>>>
>>>> (a) Ĥ copies its input ⟨Ĥ⟩
>>>> (b) Ĥ invokes embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩
>>>> (c) embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩
>>>> (d) simulated ⟨Ĥ⟩ copies its input ⟨Ĥ⟩
>>>> (e) simulated ⟨Ĥ⟩ invokes simulated embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩
>>>> (f) simulated embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩
>>>> (g) goto (d)
>>>>
>>>> embedded_H is not allowed to be applied to Ĥ ⟨Ĥ⟩ because inputs can
>>>> only be finite strings and Ĥ is not a finite string. This means
>>>> that embedded_H is not allowed to report on its own actual behavior.
>>> I can't read that notation. What is H^ and what does it look like?
>>>
>>
>> *Here is the whole Linz proof*
>> I simplified the Linz notation at the bottom of page 2 of the proof.
>> https://www.liarparadox.org/Linz_Proof.pdf
> 
> You are right, that is a sufficient proof. You may change the presentation
> but then you must prove that your presentation is equivalent to Linz'.
> 

The proof was removed until Joe could understand what Linz was saying
Here is my actual proof.

When Ĥ is applied to ⟨Ĥ⟩
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn

(a) Ĥ copies its input ⟨Ĥ⟩
(b) Ĥ invokes embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩
(c) embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩
(d) simulated ⟨Ĥ⟩ copies its input ⟨Ĥ⟩
(e) simulated ⟨Ĥ⟩ invokes simulated embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩
(f) simulated embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩
(g) goto (d)

Linz H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ derives a different result than
embedded_H applied to ⟨Ĥ⟩ ⟨Ĥ⟩.

This is because the in the latter case embedded_H must determine that
⟨Ĥ⟩ ⟨Ĥ⟩ correctly simulated by embedded_H cannot possibly stop running
after 1 to ∞ steps of correct simulation. Thus (as we can all see) 
embedded_H meets its abort simulation criteria.

The input ⟨Ĥ⟩ ⟨Ĥ⟩ to embedded_H correctly simulated by adapted UTM
embedded_H remains stuck in recursive simulation until embedded_H
recognizes this and stops simulating its input.

Introduction to the Theory of Computation, by Michael Sipser
https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X/

On 10/13/2022 11:29:23 AM
MIT Professor Michael Sipser agreed that these verbatim words are correct
(He has neither reviewed nor agreed to anything else in this paper)

<Professor Sipser agreed>
If simulating halt decider H correctly simulates its input D until H 
correctly determines that its simulated D would never stop running 
unless aborted then

H can abort its simulation of D and correctly report that D specifies a 
non-halting sequence of configurations.
</Professor Sipser agreed>

Linz H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ can see that embedded_H has already aborted
its simulation, thus it never reaches its own abort criteria.

Thus embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ meets its abort status criteria and
H ⟨Ĥ⟩ ⟨Ĥ⟩ NEVER meets its abort status criteria, thus proving
that these are two different sequences of configurations.

It is only because everyone since 1936 has rejected simulation
OUT-OF-HAND without review that no one ever noticed this before.

-- 
Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer