<p>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 "<a href="http://www.dm.unito.it/~cerruti/ac/paperpm1.pdf" rel="noreferrer">Small Turing machines and generalized busy beaver competition</a>". I quickly read it some time ago, and it has a nice graph with the borderlines between the 4 types of small TMs:</p>

<ul>
<li>decidable </li>
<li>open Collatz-like problem</li>
<li>$3x + 1$ simulation</li>
<li>universal</li>
</ul>

<p><img src="https://i.sstatic.net/gkMpP.jpg" alt="picture from the paper"></p>

<p>(perhaps some results have been improved).</p>

<p>The notion of TM used in the paper is the <em>standard</em> definition of TM used in papers on small universal Turing machines :</p>

<p><em>... 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. ...</em></p>

CC BY-SA 3.0
2012-02-14T20:06:50.337Z
The link goes to Alex Smith's paper, not the paper I think you intended.
Jeffε
CC BY-SA 3.0
2012-02-15T01:02:13.023Z
Very useful link. Thanks. Looks like I may be best going for a (2, 18) machine.
AlexC
CC BY-SA 3.0
2017-07-04T16:40:15.657Z
Reading that paper, it says that 2 state 3 symbol Turing machines have a decidable halting problem, so the Wolfram 2 state 3 symbol Turing machine cannot be universal.
Craig Feinstein
CC BY-SA 3.0
2017-07-04T18:11:12.783Z
@CraigFeinstein: the Wolfram (2,3) TM is slightly different from usual TMs: it doesn't have an halting state and it requires and infinite non-repeating tape support. It cannot even be considered weakly universal (a weakly universal TM requires an infinite *repeated* pattern in both directions)
Marzio De Biasi
CC BY-SA 3.0
2012-02-14T18:33:04.277Z
2012-02-14T20:46:51.080Z
2012-02-14T20:46:51.080Z
Marzio De Biasi
<p>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 <a href="http://11011110.livejournal.com/104656.html">http://11011110.livejournal.com/104656.html</a> and <a href="http://www.complex-systems.com/abstracts/v15_i01_a01.html">http://www.complex-systems.com/abstracts/v15_i01_a01.html</a></p>

<p>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.</p>

CC BY-SA 3.0
2012-02-14T19:06:10.257Z
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
CC BY-SA 3.0
2012-02-15T01:07:26.120Z
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
CC BY-SA 3.0
2012-02-14T18:32:57.333Z
2012-02-14T18:32:57.333Z
David Eppstein
<p>Choose a universal Turing machine with $S$ states ($0\leq s &lt; S$) and $C$ colors ($0\leq c&lt; 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.</p>

<p>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.</p>

<p>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}$.</p>

<p>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.</p>

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

<ol>
<li><p>$c \to (c,0,\langle dir\rangle,\text{receive})$ where $\langle dir\rangle$ is the current state; move, flip the state.</p></li>
<li><p>$(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.</p></li>
<li><p>$(c,s,\text{emit}) \to (c,s-1,\text{emit})$ for $s&gt;0$; move, flip the state.</p></li>
<li><p>$(c,0,\text{emit}) \to c$; move, don't change the state.</p></li>
<li><p>$(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.</p></li>
<li><p>$(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.</p></li>
</ol>

<p>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.</p>

CC BY-SA 3.0
2012-02-14T22:19:35.787Z
2012-02-14T22:19:35.787Z
Bruno Le Floch
<p>unless you carefully define "noncontroversial" in some technical way theres not a precise answer. here's another <a href="http://en.wikipedia.org/wiki/Rule_110" rel="nofollow">small machine based on rule 110</a> 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]</p>

CC BY-SA 3.0
2012-02-14T18:43:33.650Z
2012-02-14T18:43:33.650Z
vzn
<p>Since the accepted answer was posted, there is now a universal <a href="https://codegolf.stackexchange.com/questions/111278/turing-complete-language-interpreter/265539">2-state, 14-symbol Turing machine</a>. (This is very new and has not been peer-reviewed yet, but doesn't rely on any controversial definitions of universality and works starting from a finitely initialised tape, with an explicit halt transition.)</p>
<p>I was inspired to put some work into small Turing machines by the Turing-completeness proof for <em>Magic: the Gathering</em> (is that what you're alluding to in the question?), which required a 2-state Turing machine in order to work, but also generally only worked starting from a finitely initialized tape (with blank cells everywhere outside the tape), and suspected that working with fewer than 18 states was possible. (The 2-state 3-symbol Turing machine does not work for the proof because it requires the tape to be initialized with an infinite nonperiodic pattern, which is hard to construct in <em>Magic</em>.)</p>
<p>Incidentally, if you're looking to prove <em>Magic</em> Turing-complete, there are much easier constructions than building a Turing machine directly; instead of starting with a specific computational model and trying to build it in <em>Magic</em>, simpler constructions can be produced by starting with a situation in <em>Magic</em> that has hard-to-predict behaviour and proving it Turing-complete. For example, the behaviour of combining <em>Coat of Arms</em>, two copies of <em>Arcbond</em>, and many token copies of <em>Bishop of Wings</em> (with their text changed by <em>Artificial Evolution</em>) is nontrivial; this combination was discovered in 2021, and I <a href="https://esolangs.org/wiki/Flooding_Waterfall_Model#Implementation_in_Magic:_the_Gathering" rel="nofollow noreferrer">proved it to be Turing-complete</a> recently.</p>

CC BY-SA 4.0
2023-09-27T21:06:51.383Z
2023-09-27T21:06:51.383Z
ais523
<p>Alex Smith's Turing-universality proof of Wolfram's-conjectured 2-state, 3-symbol Turing machine is definitely not controversial. The given universality proof (not the machine) requires an infinite pattern on the Turing tape, and the question was whether one should allow such configurations (you can think of the usually 'blank' tape as an infinite repetitive pattern of blank symbols too). The conclusion was that as long as the configuration on the machine tape is fixed (i.e. it does not change after your computation starts, and remains the same for any computation), then the universal computation is carried out by the Turing machine. Notice that this is NOT controversial for Wolfram's Elementary Cellular Automaton rule 110 that Wolfram and Cook proven universal. The universality proof of rule 110 also requires an infinite pattern on the initial configuration, one that is different on both sides, and so it is of the same nature for the 2-state, 3-symbol Turing machine. Another concern was that perhaps such a relaxation of the initial condition (blank) requirement would make some accepted non-Turing universal automata universal, such as finite-state, linear bounded or push down automata to mention some examples, but it does not and it respects the Chomsky hierarchy. So definitely it is not controversial whether the 2-state, 3-symbol Turing machine is universal, but its universality proof did require a variation of what usually is considered to be the cotents of a regular Turing machine tape. This does not imply directly, by the way, that the 2-state, 3-symbol Turing machine is not universal on a blank tape configuration, although it might be the case, but that the proof required such a configuration.</p>

CC BY-SA 3.0
2016-11-12T18:16:35.973Z
Trying to parse this long argument, I conclude that Smith's (2,3)-TM is clearly only universal in a weak sense.  However, several of the other answers have already discussed this in detail, with references to papers with classifications that attempt to make this narrative mathematically precise.  Also note that not all TM models assume an infinite blank tape to begin with.
András Salamon
CC BY-SA 3.0
2017-09-13T18:01:38.090Z
Your comment only demonstrates that you ignore the area. I did not use any difficult concepts for someone knowledgeable in the basics of Turing machines (e.g. initial configuration, blank symbol, etc). Again, the only difference, and already accepted for other kind of automata, is that the Smith-Wolfram Turing machine does not start from a blank tape.That the right answer has -3 clearly shows how democracy and popularity does not mean truth, a more relevant realization than anything else, given the kind of clowns that are now ruling the world under the umbrella of democracy.
user2230103
CC BY-SA 3.0
2016-11-03T23:32:34.473Z
2016-11-03T23:32:34.473Z
user2230103
<p>There have been some new results since the work cited in the previous
answers. This <a href="http://arxiv.org/abs/1110.2230" rel="noreferrer">survey</a>
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:</p>

<ul>
 <li> 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. </li>

 <li> There is a <a href="http://arxiv.org/abs/0707.4489" rel="noreferrer">2-state,
4-symbol</a> 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. </li>
</ul>

<p>It sounds like the (2,18) is most useful for you.</p>

<p>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.</p>

<p><img src="https://i.sstatic.net/rHRtV.png" alt="Neary, Woods SOFSEM 2012, Smallest known universal Turing machines"></p>

<p>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 <a href="http://arxiv.org/abs/1110.2230" rel="noreferrer">here</a>.</p>

CC BY-SA 3.0
2012-02-26T14:55:39.780Z
2012-02-26T14:55:39.780Z
Niall Murphy
<p>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. </p>

<p>So far I've created a game state which encodes <a href="http://en.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_Turing_machine">Alex Smith's 2-state, 3-symbol Turing machine</a>. However, it seems (admittedly based on Wikipedia) that there's some controversy as to whether the (2, 3) machine is actually universal.</p>

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

<ol>
<li><p>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.</p></li>
<li><p>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?</p></li>
</ol>

<p>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.</p>

CC BY-SA 3.0
2012-02-14T16:13:37.813Z
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
CC BY-SA 3.0
2012-02-14T17:28:18.023Z
I think this is a reasonable place for this question.
Suresh Venkat
CC BY-SA 3.0
2012-02-14T18:32:16.180Z
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
CC BY-SA 3.0
2012-02-14T19:17:14.330Z
Added "universal" to title.  (The simplest 2-state Turing machine halts from either state on reading any symbol.)
Jeffε
CC BY-SA 3.0
2012-02-15T02:43:01.470Z
ps yrs ago searched for a survey on the subj of turing universality in cellular automata to no avail. it seems not to have been integrated into the literature much. the concept is quite widespread in "folklore" at this pt but not much grounded in formal defns/proofs/theory. wolfram has done much in the field but as many have noted much of his style is more experimentalist.
vzn
CC BY-SA 4.0
2019-05-07T18:30:55.833Z
Heh. Co-worker puts the paper (https://arxiv.org/abs/1904.09828) on Slack and nerd-snipes me, I google "2,18 universal turning machine", and here we are. Congratulations!
Cyan
<computability><turing-machines><universal-computation>
What's the simplest noncontroversial 2-state universal Turing machine?
AlexC
# What's the simplest noncontroversial 2-state universal Turing machine?

(Asked by: username_0 on 2012-02-14)

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](http://en.wikipedia.org/wiki/Wolfram%27s_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.

**Tags:** computability, turing-machines, universal-computation
> **Comments:**
> **username_0**: 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.  
> **username_1**: I think this is a reasonable place for this question.  
> **username_2**: 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?  
> **username_3**: Added "universal" to title.  (The simplest 2-state Turing machine halts from either state on reading any symbol.)  
> **username_2**: ps yrs ago searched for a survey on the subj of turing universality in cellular automata to no avail. it seems not to have been integrated into the literature much. the concept is quite widespread in "folklore" at this pt but not much grounded in formal defns/proofs/theory. wolfram has done much in the field but as many have noted much of his style is more experimentalist.  
> **username_4**: Heh. Co-worker puts the paper (https://arxiv.org/abs/1904.09828) on Slack and nerd-snipes me, I google "2,18 universal turning machine", and here we are. Congratulations!  

---

## 7 answers

### Answer by username_12 on 2012-02-26. Score: 19 | Accepted answer

There have been some new results since the work cited in the previous
answers. This [survey](http://arxiv.org/abs/1110.2230)
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](http://arxiv.org/abs/0707.4489) 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.

![Neary, Woods SOFSEM 2012, Smallest known universal Turing machines](https://i.sstatic.net/rHRtV.png)

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](http://arxiv.org/abs/1110.2230).


---

### Answer by username_5 on 2012-02-14. Score: 16

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](http://www.dm.unito.it/~cerruti/ac/paperpm1.pdf)". 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

![picture from the paper](https://i.sstatic.net/gkMpP.jpg)

(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. ...*

> **Comments:**
> **username_3**: The link goes to Alex Smith's paper, not the paper I think you intended.  
> **username_0**: Very useful link. Thanks. Looks like I may be best going for a (2, 18) machine.  
> **username_6**: Reading that paper, it says that 2 state 3 symbol Turing machines have a decidable halting problem, so the Wolfram 2 state 3 symbol Turing machine cannot be universal.  
> **username_5**: @CraigFeinstein: the Wolfram (2,3) TM is slightly different from usual TMs: it doesn't have an halting state and it requires and infinite non-repeating tape support. It cannot even be considered weakly universal (a weakly universal TM requires an infinite *repeated* pattern in both directions)  

---

### Answer by username_7 on 2012-02-14. Score: 11

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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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!  

---

### Answer by username_8 on 2012-02-14. Score: 5

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.


---

### Answer by username_2 on 2012-02-14. Score: 0

unless you carefully define "noncontroversial" in some technical way theres not a precise answer. here's another [small machine based on rule 110](http://en.wikipedia.org/wiki/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]


---

### Answer by username_9 on 2023-09-27. Score: 0

Since the accepted answer was posted, there is now a universal [2-state, 14-symbol Turing machine](https://codegolf.stackexchange.com/questions/111278/turing-complete-language-interpreter/265539). (This is very new and has not been peer-reviewed yet, but doesn't rely on any controversial definitions of universality and works starting from a finitely initialised tape, with an explicit halt transition.)

I was inspired to put some work into small Turing machines by the Turing-completeness proof for *Magic: the Gathering* (is that what you're alluding to in the question?), which required a 2-state Turing machine in order to work, but also generally only worked starting from a finitely initialized tape (with blank cells everywhere outside the tape), and suspected that working with fewer than 18 states was possible. (The 2-state 3-symbol Turing machine does not work for the proof because it requires the tape to be initialized with an infinite nonperiodic pattern, which is hard to construct in *Magic*.)

Incidentally, if you're looking to prove *Magic* Turing-complete, there are much easier constructions than building a Turing machine directly; instead of starting with a specific computational model and trying to build it in *Magic*, simpler constructions can be produced by starting with a situation in *Magic* that has hard-to-predict behaviour and proving it Turing-complete. For example, the behaviour of combining *Coat of Arms*, two copies of *Arcbond*, and many token copies of *Bishop of Wings* (with their text changed by *Artificial Evolution*) is nontrivial; this combination was discovered in 2021, and I [proved it to be Turing-complete](https://esolangs.org/wiki/Flooding_Waterfall_Model#Implementation_in_Magic:_the_Gathering) recently.


---

### Answer by username_10 on 2016-11-03. Score: -3

Alex Smith's Turing-universality proof of Wolfram's-conjectured 2-state, 3-symbol Turing machine is definitely not controversial. The given universality proof (not the machine) requires an infinite pattern on the Turing tape, and the question was whether one should allow such configurations (you can think of the usually 'blank' tape as an infinite repetitive pattern of blank symbols too). The conclusion was that as long as the configuration on the machine tape is fixed (i.e. it does not change after your computation starts, and remains the same for any computation), then the universal computation is carried out by the Turing machine. Notice that this is NOT controversial for Wolfram's Elementary Cellular Automaton rule 110 that Wolfram and Cook proven universal. The universality proof of rule 110 also requires an infinite pattern on the initial configuration, one that is different on both sides, and so it is of the same nature for the 2-state, 3-symbol Turing machine. Another concern was that perhaps such a relaxation of the initial condition (blank) requirement would make some accepted non-Turing universal automata universal, such as finite-state, linear bounded or push down automata to mention some examples, but it does not and it respects the Chomsky hierarchy. So definitely it is not controversial whether the 2-state, 3-symbol Turing machine is universal, but its universality proof did require a variation of what usually is considered to be the cotents of a regular Turing machine tape. This does not imply directly, by the way, that the 2-state, 3-symbol Turing machine is not universal on a blank tape configuration, although it might be the case, but that the proof required such a configuration.

> **Comments:**
> **username_11**: Trying to parse this long argument, I conclude that Smith's (2,3)-TM is clearly only universal in a weak sense.  However, several of the other answers have already discussed this in detail, with references to papers with classifications that attempt to make this narrative mathematically precise.  Also note that not all TM models assume an infinite blank tape to begin with.  
> **username_10**: Your comment only demonstrates that you ignore the area. I did not use any difficult concepts for someone knowledgeable in the basics of Turing machines (e.g. initial configuration, blank symbol, etc). Again, the only difference, and already accepted for other kind of automata, is that the Smith-Wolfram Turing machine does not start from a blank tape.That the right answer has -3 clearly shows how democracy and popularity does not mean truth, a more relevant realization than anything else, given the kind of clowns that are now ruling the world under the umbrella of democracy.  

---

