# What's the simplest noncontroversial 2-state universal Turing machine?

I'm wanting to encode a simple Turing machine in the rules of a card game. I'd like to make it a universal Turing machine in order to prove Turing completeness.

So far I've created a game state which encodes Alex Smith's 2-state, 3-symbol Turing machine. However, it seems (admittedly based on Wikipedia) that there's some controversy as to whether the (2, 3) machine is actually universal.

For rigour's sake, I'd like my proof to feature a "noncontroversial" UTM. So my questions are:

1. Is the (2,3) machine generally regarded as universal, non-universal, or controversial? I don't know where would be reputable places to look to find the answer to this.

2. If the (2,3) machine isn't widely accepted as universal, what's the smallest N such that a (2,N) machine is noncontroversially accepted as universal?

Edited to add: It'd also be useful to know any requirements for the infinite tape for mentioned machines, if you happen to know them. It seems the (2,3) machine requires an initial state of tape that's nonperiodic, which will be a bit difficult to simulate within the rules of a card game.

-
BTW, I can't tell whether Turing machine questions would be better posted here or on MathOverflow. I'm trying here first because cs has a "turing-machines" tag and MO doesn't. I'm not simul-crossposting as per the policy, but I'm happy for this question to be migrated if that'd be a better place for it. –  AlexC Feb 14 '12 at 16:13
I think this is a reasonable place for this question. –  Suresh Venkat Feb 14 '12 at 17:28
in general the very small machines require sophisticated "translations" or "conversions" of the inputs into a form that works for the machine, and (usually) vice versa the output into the original tape formulation. so its really more a question of whether you accept these sophisticated translations/conversions. think some conversions might even assume a periodic input tape (as you mention). maybe you are asking for the smallest machine that does not require a periodic input encoding? –  vzn Feb 14 '12 at 18:32
Added "universal" to title. (The simplest 2-state Turing machine halts from either state on reading any symbol.) –  JɛﬀE Feb 14 '12 at 19:17
@Jeff: Heh, thanks. –  AlexC Feb 15 '12 at 0:51

This is not a real answer to your question (I don't know much about the (2,3) machine debate); but I suggest you the paper "Small Turing machines and generalized busy beaver competition". I quickly read it some time ago, and it has a nice graph with the borderlines between the 4 types of small TMs:

• decidable
• open Collatz-like problem
• $3x + 1$ simulation
• universal

(perhaps some results have been improved).

The notion of TM used in the paper is the standard definition of TM used in papers on small universal Turing machines :

... They have a unique one-dimensional tape infinite in both directions, and a unique twoway read–write head. There is a blank symbol denoted by 0. Initially, a finite word, the input, is written on the tape, other cells contain the blank symbol, the head reads the leftmost symbol of the input, and the state is the initial state. At each step, according to the current state of the machine and the symbol read by the head, the symbol is modified, the head moves left or right (and cannot stay reading the same cell), and the state is modified. The computation stops when a special halting state is reached. ...

-
The link goes to Alex Smith's paper, not the paper I think you intended. –  JɛﬀE Feb 14 '12 at 20:06
@JɛﬀE: thank you! I corrected it –  Marzio De Biasi Feb 14 '12 at 20:48
Very useful link. Thanks. Looks like I may be best going for a (2, 18) machine. –  AlexC Feb 15 '12 at 1:02

It's also possible to achieve universality with 7 states and 2 symbols, although many of the same objections apply (non-uniform initial conditions on the infinite tape and unusual termination conditions). See http://11011110.livejournal.com/104656.html and http://www.complex-systems.com/abstracts/v15_i01_a01.html

These are based on simulating the Rule 110 cellular automaton, proved universal by Matthew Cook, and Cook also found a 2-state 5-symbol simulation of Rule 110, if you are wedded to the restriction that there be only two states.

-
The 2-state restriction will be a heck of a lot easier to simulate than TMs with more states. At the moment I think it'll be easier for me to make a 2-state, 18-colour TM than one with 3 states and even a small number of colours. –  AlexC Feb 14 '12 at 19:06
The (2, 5) is interesting, and may be a useful intermediate step for me. But it looks from these links like I'll have to go up to (2, 18) to find one that allows me to start with only finitely many nonblack cells on the initial tape. Thanks! –  AlexC Feb 15 '12 at 1:07

There have been some new results since the work cited in the previous answers. This survey describes the state of the art (see Figure 1). The size of the smallest known universal Turing machine depends on the details of the model and here are two results that are of relevance to this discussion:

• There is a 2-state, 18-symbol standard universal machine (Rogozhin 1996. TCS, 168(2):215–240). Here we have the usual notion of blank symbol in one or both directions of a single tape.
• There is a 2-state, 4-symbol weakly universal machine (Neary, Woods 2009. FCT. Springer LNCS 5699:262-273). Here we have a single tape containing the finite input, and a constant (independent of the input) word $r$ repeated infinitely to the right, with another constant word $l$ repeated infinitely to the left. This improves on the weakly universal machine mentioned by David Eppstein.

It sounds like the (2,18) is most useful for you.

Note that it is now known that all of the smallest universal Turing machines run in polynomial time. This implies that their prediction problem (given a machine $M$, input $w$ and time bound $t$ in unary, does $M$ accept $w$ within time $t$?) is P-complete. If you are trying to make a (1-player) game this might be useful, for example to show that it is NP-hard to find an initial configuration (hand of cards) that leads to a win within t moves. For these complexity problems we care only about a finite portion of the tape, which makes the (extremely small) weakly universal machines very useful.

The figure shows the smallest known universal machines for a variety of Turing machine models (taken from Neary, Woods SOFSEM 2012), the references can be found here.

-

Choose a universal Turing machine with $S$ states ($0\leq s < S$) and $C$ colors ($0\leq c< C$) operating on a one-dimensional tape (we'll call stuff relating to this machine "true"). Let us build together a $2$-state Turing machine (states $\text{L}$ and $\text{R}$) with $C+4SC$ colors: the true colors, and "enhanced" colors which carry info about states. We add the constraint that the initial state should be identical to the initial state of the true machine, except possibly for the cell in which we start.

At all times, only the current cell, or the two cells involved in a transition, may have enhanced colors: all other cells have their true color. We want our machine to behave as follows: check what true transition to perform, move the "true state" information from the cell we want to leave to the target cell (this involves a lot of back-and-forth), clean up the cell we left (giving it a true color), repeat.

Before a transition, the current cell has the enhanced color $(c,s)$ encoding the true color, and the true state, and all others have their true color. Look up what transition the true machine would do --- we can assume it is going to the right (flip $\text{L}$ and $\text{R}$ everywhere to go left). Change the enhanced color to $(c_{\text{new}}, s_{\text{new}}, \text{emit})$, move to the right, and change the current state to $\text{L}$.

Then the machine sees a normal color $c$ and is in state $\text{L}$. It changes $c$ to $(c,0, \text{L},\text{receive})$, and goes back left, in state $\text{R}$. We thus have the cells $$\cdots \quad c \quad \quad c \quad (c,s,\text{emit}) \quad (c,0,\text{L},\text{receive}) \quad c \quad c \quad \cdots$$ where the various true colors are of course independent, but irrelevant. The goal is to move $s$ to the target cell. We do that by decrementing the left state, and incrementing the right state, going back and forth between the two. The end is easy to detect in the left cell ($s$ has become $0$), but harder to detect in the right cell. This is what the $\text{L}$ label is for: as long as the state matches that, continue the decrement/increment loop, but if it does not, we are done, and we clean up.

Here are the transitions to implement that. In almost all cases, move in the direction specified by the current state, then flip the state

1. $c \to (c,0,\langle dir\rangle,\text{receive})$ where $\langle dir\rangle$ is the current state; move, flip the state.

2. $(c,s) \to (c_{\text{new}},s_{\text{new}},\text{emit})$ according to the true machine's transitions; ignore current state, set it to the direction in which we want to move; move, flip the state.

3. $(c,s,\text{emit}) \to (c,s-1,\text{emit})$ for $s>0$; move, flip the state.

4. $(c,0,\text{emit}) \to c$; move, don't change the state.

5. $(c,s, \langle dir\rangle, \text{receive}) \to (c, s+1, \langle dir\rangle, \text{receive})$ if the state is $\langle dir\rangle$; move, flip the state.

6. $(c,s, \langle dir\rangle, \text{receive}) \to (c,s)$ if the state is not $\langle dir\rangle$; don't move, do whatever you like with the state. This could be combined with 2. if you want to always move.

Combining 6 and 2 reduces the number of colors to $C+3SC$. I believe that it is possible to make the initial configuration have no enhanced color at all, but it is probably messy.

-

unless you carefully define "noncontroversial" in some technical way theres not a precise answer. here's another small machine based on rule 110 proved universal in a sense but my understanding is that it requires infinite periodic input tape formulations (and likewise extraction at the end when the machine halts). havent seen the "periodic vs nonperiodic" tape issue described in the literature although its been discussed on eg math mailing lists [Foundations of Mathematics mailing list]

-