# [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
conditions.

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.
Cheers,
Rob van Glabbeek
```