Re: Simulating termination analyzers by dummies --- What does halting mean?

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