[FOM] a taxonomy to help with 2-3 controversies

[Thomas Lord]

Let me preface this by saying that I don't address the issue
of "halting conditions" -- to which I think a similar style
of taxonomic think would add clarity:

I was thinking about the difference between Turing tapes
that are infinite 0s (or any constant) in both directions,
outside of a finite initialized region, and Turing tapes that
have some other computed pattern, infinite in either or both
directions.

I think there is an important difference and that that difference
undermines the claim that the 2-3 machine's universality has
been proved.  The difference I observe can be described in
terms of communications theory:

Whether or not the initial tape is 0s at both ends, there is
a designated starting cell -- the initial condition of the tape
is defined relative to that starting cell.

Here is one difference:  an arbitrary finite region of an
all-0 semi-tape contains no information at all about the
position of the start cell.   But, if you compute semi-tapes
by a regular process, then there is some minimum K
such that every region of the semi-tape contains at least
phase information about the relative position of the start
cell.    And in general (and somewhat handwavingly at
this point) -- any "interesting" non-universal way of
initializing semi-tapes will have the same effect:  there
will be some reliably finite K such that K-sized and larger
regions of the semitapes -- everywhere on the semitapes --
all contain information about the relative position of
the start cell.   There is some non-trivial sense in which
the non-0 same tapes contain an infinite amount of information
that characterizes the input problem.

And again: all-0 (all-any-constant) and truly random
semi-tapes do not share that property.   There is no "K"
such that every K-sized region of such a semi-tape gives
a clue about the relative position of the start state.

In essence, all non-0/non-random ways of initializing
tapes are one collection of things, the 0/random semi-tapes
are another.   "Universal" is a good and traditional name
for machines that can compute on 0/random semi-tapes.
The 2-3 machine is only so far proved for that other
kind of tape -- the kind that, even if not explicitly
repeating the input question again and again, is at least
repeatedly signaling the subject 2-3 machine to keep
trying harder.

(Personally, I like the name "general purpose computer"
for the kind of thing a 2-3 has been proved to be (they
say).  All universal machines are general purpose computers
but general purpose computers aren't all universal.)

(Also, there's a related rates problem in all of this.  If
the speed of a tape initializer is not linear in the speed
of its general purpose computer, does that meant that the
general purpose computer can be computationally weaker
yet the whole system still be computationally complete?
And again -- you could frame halt conditions in similar ways.)


-t