XPost: comp.theory, sci.logic, sci.math
On 12/29/2021 11:18 PM, André G. Isaak wrote:
On 2021-12-29 21:51, olcott wrote:
On 12/29/2021 10:44 PM, Richard Damon wrote:
On 12/29/21 11:02 PM, olcott wrote:
On 12/29/2021 1:16 PM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:
*My criterion measure with Ben's notational conventions*
H.q0 wM w ⊢* H.qy iff UTM(wM, w) halts
H.q0 wM w ⊢* H.qn iff UTM(wM, w) does not halt
It's not your criterion, it's mine. It's also Linz's. If yours is >>>>> not
the same as his (and mine), it should be different in some way.
(And we
can safely ignore it, since no one cares about your alternative
criteria.)
It has always been my criterion measure that halt deciders base
their halt status decision on the pure simulation of their inputs.
That your notational conventions very cleanly express this idea as
applied to the Linz H is a good breakthrough.
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
As soon as people understand that this same criterion measure
applies recursively to every embedded_H at Ĥ.qx, then they will see
how this criterion measure provides the means for embedded_H to
correctly compute the mapping from ⟨Ĥ⟩ ⟨Ĥ⟩ to Ĥ.qn.
Yes each level can use the test to determine if the halt decider at
that level got the right answer or not.
The issue is that when we are doing this check, you check JUST that
level, and not lower levels.
No you are wrong.
No, he isn't.
The specification you give above (where YET AGAIN you omit the
conditions)
The conditions are provided by H, because H is copied to Ĥ.qx we need
not state them again.
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
To make things simple we name the copy of H at Ĥ.qx embedded_H.
Because the criterion measure is applied as if the embedded_H at Ĥ.qx
was replaced by a UTM and the TM description of Ĥ would include a TM description of this UTM the execution of Ĥ applied to ⟨Ĥ⟩ would
endlessly repeat:
copy its input ⟨Ĥ⟩ to ⟨Ĥ⟩ and then simulate this input with the UTM...
In order for embedded_H to see what this machine would do it must
actually perform a pure simulation of N steps of its input ⟨Ĥ⟩ ⟨Ĥ⟩. This
may or may not include simulating embedded_H.
As soon as embedded_H sees that these steps would otherwise endlessly
repeat it aborts its simulation and transitions to Ĥ.qn.
Because it is applying a criterion measure that we know is correct:
A halt decider is always correct when it bases its halt status decision
on the behavior of the UTM simulation of its inputs.
We know that this transition to Ĥ.qn is correct.
is for a case where the input to Ĥ is a description of
itself, but the actual specification of the machine can't make that assumption. So really we should be using:
The criterion measure is merely provided to humans so that humans can understand that the basis of the halt status decision of embedded_H is
sound.
Because it is obvious that the basis is sound when applied to H then
this same sound basis carries over to embedded_H.
Ĥ.q0 ⟨wM⟩ ⊢* Ĥ.qx wM wM⟩ ⊢* Ĥ.qy ∞ iff UTM(wM, wM) halts
Ĥ.q0 ⟨wM⟩ ⊢* Ĥ.qx wM wM⟩ ⊢* Ĥ.qn iff UTM(wM, wM) does not halt
Ĥ has absolutely no knowledge of what it will be given as an input. In
For purposes of discussion we are simply ignoring every other input and
only focusing on the one input.
It is simpler for the human mind to see all the relevant details in one
place and not have to imagine all of the changes to see the case-at-hand.
The way that you specify the criterion measure is vague. When I define
the criterion measure for H this applies the criterion measure at the
point where H is copied Ĥ.qx.
the case we considered above wM was ⟨Ĥ⟩, but wM could have been a description of any machine. Ĥ has no way of knowing if wM is a
description of itself, or a description of some TM which simply prints
its input string to the tape in reverse order (which wouldn't involve simulating its input at all).
H thus embedded_H only makes its halt status decision on the basis of
the simulation of its input. H can only see what its input does by
simulating its input.
So the conditions given above cannot
possibly apply to any 'lower level' since Ĥ knows nothing about any of
those 'lower levels'.
André
It only applies to lower levels when there is actual pathological self-reference(Olcott 2004) as there is with the definition of Ĥ. Ĥ is
asking itself whether or not it stops running and then looping if it
says yes.
--
Copyright 2021 Pete Olcott
Talent hits a target no one else can hit;
Genius hits a target no one else can see.
Arthur Schopenhauer
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)