Path: ...!3.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.theory
Subject: Re: Simulating termination analyzers by dummies --- What does halting
 mean?
Date: Fri, 21 Jun 2024 08:19:28 -0500
Organization: A noiseless patient Spider
Lines: 110
Message-ID: <v53ul0$35vak$5@dont-email.me>
References: <v4oaqu$f9p5$1@dont-email.me> <v4os9e$i70m$1@dont-email.me>
 <v4p9mb$lavj$1@dont-email.me> <v4qe53$a0nm$1@i2pn2.org>
 <v4qn65$10qh6$1@dont-email.me> <v4qnkf$a0nm$5@i2pn2.org>
 <v4qpvo$10qh6$2@dont-email.me> <v4qrmd$a0nm$6@i2pn2.org>
 <v4qrr8$15beg$1@dont-email.me> <v4qsav$a0nn$3@i2pn2.org>
 <v4qtaa$15gc5$1@dont-email.me> <v4qu3p$a0nm$7@i2pn2.org>
 <v4quti$15nn8$1@dont-email.me> <v4rrge$bivn$1@i2pn2.org>
 <v4s1l0$1boeu$6@dont-email.me> <v4seq5$cbcu$1@i2pn2.org>
 <v4sfuo$1enie$1@dont-email.me> <v4shpp$cbcu$2@i2pn2.org>
 <v4st0g$1hjnp$1@dont-email.me> <v4sull$2f03$1@news.muc.de>
 <v4svmn$1i267$1@dont-email.me> <v4u8cu$1o15$1@news.muc.de>
 <v4uoj9$1vpm0$10@dont-email.me> <v50ena$2ecrp$1@dont-email.me>
 <v50fcc$2efr5$1@dont-email.me> <v51gli$2kgr3$1@dont-email.me>
 <v51hgt$2kigj$1@dont-email.me> <v5393g$3286d$3@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 21 Jun 2024 15:19:28 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="d3e479354f6c59f79625e93d556f5bfb";
	logging-data="3341652"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/opW4RzJWAdh8YGaM8GZyk"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:kIEnTjkBiLeC+GlOb9CGpDp+UMQ=
In-Reply-To: <v5393g$3286d$3@dont-email.me>
Content-Language: en-US
Bytes: 6356

On 6/21/2024 2:11 AM, Mikko wrote:
> On 2024-06-20 15:23:09 +0000, olcott said:
> 
>> On 6/20/2024 10:08 AM, Mikko wrote:
>>> On 2024-06-20 05:40:28 +0000, olcott said:
>>>
>>>> On 6/20/2024 12:29 AM, Mikko wrote:
>>>>> On 2024-06-19 14:05:29 +0000, olcott said:
>>>>>
>>>>>> On 6/19/2024 4:29 AM, Alan Mackenzie wrote:
>>>>>>> olcott <polcott333@gmail.com> wrote:
>>>>>>>> On 6/18/2024 4:36 PM, Alan Mackenzie wrote:
>>>>>>>>> [ Followup-To: set ]
>>>>>>>
>>>>>>>>> In comp.theory olcott <polcott333@gmail.com> wrote:
>>>>>>>>>> On 6/18/2024 12:57 PM, joes wrote:
>>>>>>>>>>> Am Tue, 18 Jun 2024 12:25:44 -0500 schrieb olcott:
>>>>>>>>>>>> On 6/18/2024 12:06 PM, joes wrote:
>>>>>>>>>>>> void DDD()
>>>>>>>>>>>> {
>>>>>>>>>>>> H0(DDD);
>>>>>>>>>>>> }
>>>>>>>>>>>> DDD correctly simulated by any H0 cannot possibly halt.
>>>>>>>>>>>>> DDD halts iff H0 halts.
>>>>>>>
>>>>>>>>>>> So H0 returns "doesn't halt" to DDD, which then stops running,
>>>>>>>>>>> so H0 should have returned "halts".
>>>>>>>
>>>>>>>>>> This was three messages ago.
>>>>>>>>>> I had to make sure that you understood that halting
>>>>>>>>>> does not mean stopping for any reason and only includes
>>>>>>>>>> the equivalent of terminating normally.
>>>>>>>
>>>>>>>>> No.  You're wrong, here.  A turing machine is either running or 
>>>>>>>>> it's
>>>>>>>>> halted.  There's no third alternative.  If your C programs are 
>>>>>>>>> not in one
>>>>>>>>> of these two states, they're not equivalent to turing machines.
>>>>>>>
>>>>>>>> Although I agree with this there seems to be nuances of
>>>>>>>> disagreement across the experts.
>>>>>>>
>>>>>>> I doubt that very much.  The whole point of turing machines is to 
>>>>>>> remove
>>>>>>> ambiguity and unneeded features from the theory of computation.  
>>>>>>> A third
>>>>>>> alternative state is unneeded.
>>>>>>>
>>>>>>
>>>>>> Some people say that a TM can halt in a non-final state.
>>>>>
>>>>> People may use different words to express the same facts. What some
>>>>> people call "halting in a non-final state" is called "rejecting" by
>>>>> some other people. But the facts are what they are independently of
>>>>> the words used to express them.
>>>>
>>>> Ambiguity and vagueness make communication less effective.
>>>
>>> As does use of common words and expressions for uncommon meanings.
>>>
>>>> I use C because there are zero gaps in exactly what it means.
>>>
>>> THere are lont of gaps in C. Some are mistakes that are corrected in
>>> technical corrigenda. Others are undefined and implementation defined
>>> behaviour. Your program uses non-standard extensions to C so it does
>>> not communicate well. If also is too big to be a part of a publishable
>>> article.
>>>
>>
>> *There are zero gaps in the behavior of DDD correctly simulated by HH0*
>> https://liarparadox.org/HH0_(DDD)_Full_Trace.pdf
>>
>> _DDD()
>> [00002093] 55               push ebp
>> [00002094] 8bec             mov ebp,esp
>> [00002096] 6893200000       push 00002093 ; push DDD
>> [0000209b] e853f4ffff       call 000014f3 ; call HH0
>> [000020a0] 83c404           add esp,+04
>> [000020a3] 5d               pop ebp
>> [000020a4] c3               ret
>> Size in bytes:(0018) [000020a4]
>>
>> Whereas the Linz specification of Ĥ says that embedded_H
>> does something or other that is totally unspecified:
>>
>> When Ĥ is applied to ⟨Ĥ⟩
>> Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
>> Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
> 
> Linz Ĥ is fully defined in terms of H, so its behaviour can be inferred
> from the behaviour of H. Therefore Linz can prove about the behaviour of
> both Ĥ and H what needs be proven.
> 

(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) with one more level of simulation

Two complete simulations show a pair of identical TMD's are simulating a 
pair of identical inputs.  We can see this thus proving recursive 
simulation.

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