[FOM] Simple Turing machines, Universality, Encodings, etc.
Rob van Glabbeek
rvg at cs.stanford.edu
Tue Oct 30 05:45:48 EDT 2007
Todd Rowland <rowland at wolfram.com> writes:
> It is a challenge to explicitly construct a machine with initial
> conditions similar in spirit to Smith's, that is obviously too simple
> to be considered universal, and which is performing a universal
> computation with those infinite initial conditions.
A challenge?? OK:
Claim 1: The following construction of a non-periodic semi-infinite
tape is similar in spirit to Smith's.
Take universal Turing machine U. We are going to write a
right-infinite tape by traversing once from left to right.
By means of any standard function f embedding NxN in N, we enumerate
all pairs (i,t) in NxN and let U run for t steps on input i.
Here input strings of U are seen as integers i in a standard way.
If U halts, we write the number i in unary as i a's,
followed by a b. Otherwise, we write i+1 dummy symbols d.
Arguments for claim 1:
The value of any cell n of the semi-infinite tape can be computed
by an algorithm with low complexity in n. [I could have left out the
writing of the dummy symbols, but then the complexity of computing
the value of the nth cell wouldn't be so obviously low.]
Producing the input tape involves calling an universal TM. Smith
uses a cyclic tag system, that is also universal, in the very same
way. He states that the tape is written "by an obviously
non-universal algorithm". This because to write a section of tape,
the universal system is run a finite and pre-determined amount of
steps at a time.
Claim 2: It is trivial to construct a TM that
(a) starts with initial conditions similar in spirit to Smith's
(b) is obviously too simple to be considered universal
(c) is performing a universal computation with those infinite initial
In support of claim 2(a):
My TM starts with a left end-marker a on its tape,
followed by k c's, followed by the semi-infinite tape that's fixed
once-and-for-all and calculated above. Here k is a number (represented
in unary on our tape) that describes a possible input (not in unary) of U.
In support of claim 2(c):
My TM halts iff the original TM U halts on input k.
In support of claim 2(b):
All my TM does is to perform a simple look-up function.
It checks whether or not somewhere on the tape is a sequence of
a's, preceded by a non-a and followed by a b, that is equally long as
the given sequence of c's.
As the construction of such a TM is trivial, this concludes the
argument. However, inspired by Stephen Wolfram, I have constructed
one that only uses 3 states and 5 tape symbols. :^)
1-> <-2 <-3
a |d/2 b/1 Halt By default we stay in the same state.
b |d/3 b/1 a/1 /1 means go to state 1 and move right.
c |c e/1 c/1 /2 means go to state 2 and move left.
d |d d d /3 means go to state 3 and move left.
e |e e c We start in state 1 on the first field
of the permanent part of the input
(just right of all the c's)
or equivalently on any of the c's.
Rob van Glabbeek
More information about the FOM