[FOM] Simple Turing machines, Universality, Encodings, etc.

[Rob van Glabbeek]

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