[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


More information about the FOM mailing list