30
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – AlexC Feb 14 '12 at 16:13
  • 12
    $\begingroup$ I think this is a reasonable place for this question. $\endgroup$ – Suresh Venkat Feb 14 '12 at 17:28
  • $\begingroup$ 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? $\endgroup$ – vzn Feb 14 '12 at 18:32
  • 4
    $\begingroup$ Added "universal" to title. (The simplest 2-state Turing machine halts from either state on reading any symbol.) $\endgroup$ – Jeffε Feb 14 '12 at 19:17
  • 1
    $\begingroup$ 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. $\endgroup$ – vzn Feb 15 '12 at 2:43
12
$\begingroup$

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.

Neary, Woods SOFSEM 2012, Smallest known universal Turing machines

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.

$\endgroup$
13
$\begingroup$

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

picture from the paper

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

$\endgroup$
  • 1
    $\begingroup$ The link goes to Alex Smith's paper, not the paper I think you intended. $\endgroup$ – Jeffε Feb 14 '12 at 20:06
  • $\begingroup$ @JɛffE: thank you! I corrected it $\endgroup$ – Marzio De Biasi Feb 14 '12 at 20:48
  • $\begingroup$ Very useful link. Thanks. Looks like I may be best going for a (2, 18) machine. $\endgroup$ – AlexC Feb 15 '12 at 1:02
  • $\begingroup$ 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. $\endgroup$ – Craig Feinstein Jul 4 '17 at 16:40
  • 1
    $\begingroup$ @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) $\endgroup$ – Marzio De Biasi Jul 4 '17 at 18:11
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – AlexC Feb 14 '12 at 19:06
  • $\begingroup$ 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! $\endgroup$ – AlexC Feb 15 '12 at 1:07
5
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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]

$\endgroup$
-3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – András Salamon Nov 12 '16 at 18:16
  • $\begingroup$ 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. $\endgroup$ – user2230103 Sep 13 '17 at 18:01

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.