Re: Simulating termination analyzers by dummies --- criteria is met

On 6/22/2024 8:27 AM, Richard Damon wrote:

On 6/22/24 9:04 AM, olcott wrote:

On 6/22/2024 3:05 AM, Mikko wrote:

On 2024-06-21 13:19:28 +0000, olcott said:
>

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

>
Linz says nothing about simulations

>
I am the sole inventor of the simulating halt decider.
>
Ben Bacarisse contacted professor Sipser to verify that he
really did says this. The details are in this forum about
the same date.
>
https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X/
>
<MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022>
   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.
</MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022>

 And, as I remember, he also verified that he disagrees with your definition of correct simulation.
 

>
*Ben also verified that the criteria have been met*
On 10/14/2022 7:44 PM, Ben Bacarisse wrote:
 > I don't think that is the shell game. PO really /has/ an H
 > (it's trivial to do for this one case) that correctly determines
 > that P(P) *would* never stop running *unless* aborted.

 Right, Ben was willing to do what I am not that you can prove that, by your definition, H can show that it "must" abort its simulation or the input will run forever.
 But, just like me, he also agrees that this is NOT the defintion of Halting, so H is just shown to be a correct (partial) POOP decider but ot a Halt Decider, not even for that one input.
 

On 10/14/2022 7:44 PM, Ben Bacarisse wrote:
 > I don't think that is the shell game. PO really /has/ an H
 > (it's trivial to do for this one case) that correctly determines
 > that P(P) *would* never stop running *unless* aborted.
 >
 > He knows and accepts that P(P) actually does stop. The
 > wrong answer is justified by what would happen if H
 > (and hence a different P) where not what they actually are.
 >
*Ben agrees that the criteria is met for the input*
Computable functions are the formalized analogue of the
intuitive notion of algorithms, in the sense that a function
is computable if there exists an algorithm that can do the
job of the function, i.e. *given an input of the function*
*domain it can return the corresponding output*
https://en.wikipedia.org/wiki/Computable_function
*Ben disagrees that the criteria is met for the non-input*
Yet no one here can stay focused on the fact that non-inputs
*DO NOT COUNT*
void DDD()
{
   HHH0(DDD);
}
int main()
{
   Output("Input_Halts = ", HHH0(DDD));
   Output("Input_Halts = ", HHH1(DDD));
}
It is a verified fact that the behavior that finite string DDD
presents to HH0 is that when DDD correctly simulated by HH0
calls HH0(DDD) that this call DOES NOT RETURN.
It is a verified fact that the behavior that finite string DDD
presents to HH1 is that when DDD correctly simulated by HH1
calls HH0(DDD) that this call DOES RETURN.
*I don't get why people here insist on lying about verified facts*
--
Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer