<p>The <a href="http://en.wikipedia.org/wiki/Rule_110" rel="noreferrer">Rule 110 cellular automaton</a> (often simply <strong>Rule 110</strong>) is an elementary cellular automaton with interesting behavior on the boundary between stability and chaos. In this respect it is similar to Game of Life. <em>Rule 110 is known to be Turing complete</em>. This implies that, in principle, any calculation or computer program can be simulated using this automaton.</p>

<p>Another simple example is a <strong>Bitwise Cyclic Tag System</strong>:</p>

<p>The "program" is a sequence of instructions $0, 01, 11$ (i.e. $C = p_{n} p_{n-1} ... p_2 p_1; \; p_i \in (0|01|11)^+$)
; the "data" is a binary string (i.e. $w \in \{0,1\}^+$).</p>

<p>If $p_1$ is the "current instruction" and the data is $w = a_1 a_2 ... a_m$; you can put the program and the data side by side ($p_{n}...p_2 p_1 \leftrightarrow a_1 a_2 ...a_m$), and the "execution" of $p_1$ is:</p>

<ul>
<li>if $a_1 = 1$ and $p_1 = x1$ then append $x$ to $w$</li>
<li>delete $a_1$ from $w$</li>
<li>rotate $C$ ($p_1$ is moved to the left of $C$ and $p_2$ becomes the current instruction)</li>
</ul>

<p>The universality can be proved by simulating the more general cyclic-tag system.</p>

CC BY-SA 3.0
2013-07-03T10:38:02.627Z
2013-07-03T12:53:54.930Z
2013-07-03T12:53:54.930Z
Marzio De Biasi
<p>Conway's FRACTRAN comes to mind: 
<a href="http://en.wikipedia.org/wiki/FRACTRAN">http://en.wikipedia.org/wiki/FRACTRAN</a></p>

<p>A FRACTRAN program is a list $q_1 , \ldots,  q_k$ of positive rational numbers.
The current state is a natural number $n$, and a computation step consists in multiplying $n$ by the first $q_i$ whose denominator divides $n$. 
Starting from the input, the computation step is repeated until no longer possible, i.e., until no $q_i$ has a denominator dividing $n$. The curent state at that point is the output.</p>

CC BY-SA 3.0
2015-08-18T05:43:28.553Z
This doesn't look simple at all. I can't imagine the shortest implementation of that would be smaller than of RULE 110 in any reasonable turing machine, or on the lambda calculus. But I might be wrong.
MaiaVictor
CC BY-SA 3.0
2013-07-03T11:22:48.940Z
2013-07-03T11:22:48.940Z
Jan Johannsen
<p>It depends how you define <em>simplest</em>. One of the simplest languages I know are <a href="https://en.wikipedia.org/wiki/Iota_and_Jot" rel="nofollow noreferrer">Iota and Jot</a>. A detailed description can be found <a href="https://www.nyu.edu/projects/barker/Iota/" rel="nofollow noreferrer">here</a>. Both are Turing-complete languages that use just two symbols (no variables etc.).</p>
<p>Iota programs can be viewed as binary trees with <span class="math-container">$*$</span> at nodes and <span class="math-container">$i$</span> at leafs. So the whole program is solely determined by the shape of its binary tree. Any such a binary tree forms a valid program.</p>
<p>Jot is similar, but slightly different. Programs in Jot are (arbitrary) sequences of 1's and 0's. Any such a binary sequence forms a grammatically valid program.</p>

CC BY-SA 4.0
2013-07-03T09:56:21.050Z
2020-08-14T14:09:21.407Z
2020-08-14T14:09:21.407Z
Petr
<p>If by simple you mean "easy to define" then I would advise <a href="http://en.wikipedia.org/wiki/Semi-Thue_system" rel="noreferrer">semi-Thue systems</a>, a simple family of string rewrite systems.</p>

<p>I often use semi-Thue systems in hardness proofs since they are much simpler to define than lambda-calculus or Turing machines.</p>

CC BY-SA 3.0
2013-07-03T09:49:38.427Z
Consider adding some more details to improve the quality of your answer.
Dave Clarke
CC BY-SA 3.0
2013-07-03T09:47:29.997Z
2013-07-03T09:47:29.997Z
phs
<p>A <em>Turing Machine</em>, informally, consists of a set of states along with an infinite tape with a read head, and a set of rules: When you read symbol $x$ and are in state $q$, write symbol $y$, go to state $q'$, and move either left or right. I do not know of any Turing-complete system of computation that is simpler to explain to, say, a layperson, than that.</p>

<p>The formal definition of a Turing Machine seems to me at least as brief as the formality required to define, say, the $\lambda$-calculus, the $\mu$-recursive functions, or the Game of Life.</p>

CC BY-SA 3.0
2013-07-03T17:41:30.773Z
2013-07-03T17:41:30.773Z
usul
<p>the classic <a href="http://en.wikipedia.org/wiki/Post_correspondence_problem" rel="nofollow">Post Correspondence Problem</a> is Turing complete and remarkable in its simplicity, its just a string matching question albeit with potentially very long strings. </p>

<p>but on the other hand, the Turing Machine itself is a very simple theoretical concept. some have said that Turing was inspired by [electric] <a href="https://en.wikipedia.org/wiki/Typewriter" rel="nofollow">typewriters</a>. the 1st commercial electric typewriters appeared in the ~1920s and the <a href="https://en.wikipedia.org/wiki/Turing_machine" rel="nofollow">TM</a> was invented in 1936. also stock teletype machines, originally invented by Edison, had been in widespread use at the time.</p>

<p>some plausible case can be made that all Turing complete systems are exactly as/equally simple.</p>

CC BY-SA 3.0
2013-07-03T16:23:09.923Z
2013-07-03T16:23:09.923Z
vzn
<p>the <a href="http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life" rel="nofollow">Game of Life</a> cellular automaton, which has very simple update rules and was an early scientific/mathematical/computational example that exhibits/demonstrates <a href="http://en.wikipedia.org/wiki/Emergence" rel="nofollow">emergence</a>, is Turing complete, with the proof initially credited to <a href="http://en.wikipedia.org/wiki/John_Horton_Conway" rel="nofollow">Conway</a> but it seems to be unpublished. <a href="http://rendell-attic.org/gol/tm.htm" rel="nofollow">Paul Rendell</a> has constructed versions of a TM running inside of Life.</p>

CC BY-SA 3.0
2013-07-03T17:34:40.490Z
2013-07-03T17:34:40.490Z
vzn
<p>the question of whether there are integer solutions to Diophantine (ie simple algebra) equations is a simple mathematical question, aka <a href="http://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem" rel="nofollow">Hilberts 10th problem</a>. the Greeks pondered variations on diophantine equations two millenia ago [and Egyptians even earlier], also suggesting its a relatively simple concept. the <em>proof</em> that it is Turing complete on the other hand is complex and took ~¾ century to resolve after posed by Hilbert as completed by <a href="http://en.wikipedia.org/wiki/Yuri_Matiyasevich" rel="nofollow">Matiyasevich</a> (building on earlier work by Davis/Robinson/Putnam).</p>

CC BY-SA 3.0
2013-07-03T16:47:17.403Z
2013-07-03T16:47:17.403Z
vzn
<p>Lambda Calculus is very simple. Are there even simpler turing-complete systems? Which is the simplest of them all?</p>

CC BY-SA 3.0
2013-07-03T09:32:58.550Z
How do you define "simple"?
Dave Clarke
CC BY-SA 3.0
2013-07-03T17:36:58.657Z
see also [simplest noncontroversial 2-state TM](http://cstheory.stackexchange.com/questions/10207/whats-the-simplest-noncontroversial-2-state-universal-turing-machine)
vzn
CC BY-SA 3.0
2013-07-03T17:50:57.847Z
Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a **research-level** question in TCS. Please see the [FAQ](http://cstheory.stackexchange.com/help/on-topic) for more information on what is meant by this. Your question might be suitable for [cs.se] which has a broader scope.
Kaveh
CC BY-SA 3.0
2013-07-03T17:52:16.443Z
Moreover, as Dave noted, it is not clear what you are looking for unless you clarify what you mean by a system being simpler than another one.
Kaveh
CC BY-SA 3.0
2013-07-03T18:31:08.773Z
not every word used in TCS has a strict technical defn, eg the word "natural". think "simple" is fairly interpreted in the answers. instead of closing, how about just migrate it to cs.se
vzn
CC BY-SA 3.0
2013-07-11T22:42:58.267Z
one might argue that part of the question, or hidden in it, is the natural challenge to come up with some technical definition of "simple" that can discriminate different TM complete systems from each other based on some apparent measure of complexity.
vzn
CC BY-SA 3.0
2014-01-30T10:59:22.823Z
A [related question](http://cs.stackexchange.com/q/991/55) on CS.SE
Artem Kaznatcheev
CC BY-SA 4.0
2018-07-09T23:22:51.003Z
[Wang B-machines](https://en.wikipedia.org/wiki/Wang_B-machine) are very minimalist.
user76284
<fl.formal-languages><turing-machines><lambda-calculus><functional-programming>
What are the simplest turing-complete systems?
Dokkat
# What are the simplest turing-complete systems?

(Asked by: username_0 on 2013-07-03)

Lambda Calculus is very simple. Are there even simpler turing-complete systems? Which is the simplest of them all?

**Tags:** fl.formal-languages, turing-machines, lambda-calculus, functional-programming
> **Comments:**
> **username_1**: How do you define "simple"?  
> **username_2**: see also [simplest noncontroversial 2-state TM](http://cstheory.stackexchange.com/questions/10207/whats-the-simplest-noncontroversial-2-state-universal-turing-machine)  
> **username_3**: Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a **research-level** question in TCS. Please see the [FAQ](http://cstheory.stackexchange.com/help/on-topic) for more information on what is meant by this. Your question might be suitable for [cs.se] which has a broader scope.  
> **username_3**: Moreover, as Dave noted, it is not clear what you are looking for unless you clarify what you mean by a system being simpler than another one.  
> **username_2**: not every word used in TCS has a strict technical defn, eg the word "natural". think "simple" is fairly interpreted in the answers. instead of closing, how about just migrate it to cs.se  
> **username_2**: one might argue that part of the question, or hidden in it, is the natural challenge to come up with some technical definition of "simple" that can discriminate different TM complete systems from each other based on some apparent measure of complexity.  
> **username_4**: A [related question](http://cs.stackexchange.com/q/991/55) on CS.SE  
> **username_5**: [Wang B-machines](https://en.wikipedia.org/wiki/Wang_B-machine) are very minimalist.  

---

## 8 answers

### Answer by username_6 on 2013-07-03. Score: 7

The [Rule 110 cellular automaton](http://en.wikipedia.org/wiki/Rule_110) (often simply **Rule 110**) is an elementary cellular automaton with interesting behavior on the boundary between stability and chaos. In this respect it is similar to Game of Life. *Rule 110 is known to be Turing complete*. This implies that, in principle, any calculation or computer program can be simulated using this automaton.

Another simple example is a **Bitwise Cyclic Tag System**:

The "program" is a sequence of instructions $0, 01, 11$ (i.e. $C = p\_{n} p\_{n-1} ... p\_2 p\_1; \; p\_i \in (0|01|11)^+$)
; the "data" is a binary string (i.e. $w \in \{0,1\}^+$).

If $p\_1$ is the "current instruction" and the data is $w = a\_1 a\_2 ... a\_m$; you can put the program and the data side by side ($p\_{n}...p\_2 p\_1 \leftrightarrow a\_1 a\_2 ...a\_m$), and the "execution" of $p\_1$ is:

* if $a\_1 = 1$ and $p\_1 = x1$ then append $x$ to $w$
* delete $a\_1$ from $w$
* rotate $C$ ($p\_1$ is moved to the left of $C$ and $p\_2$ becomes the current instruction)

The universality can be proved by simulating the more general cyclic-tag system.


---

### Answer by username_7 on 2013-07-03. Score: 6

Conway's FRACTRAN comes to mind:
<http://en.wikipedia.org/wiki/FRACTRAN>

A FRACTRAN program is a list $q\_1 , \ldots, q\_k$ of positive rational numbers.
The current state is a natural number $n$, and a computation step consists in multiplying $n$ by the first $q\_i$ whose denominator divides $n$.
Starting from the input, the computation step is repeated until no longer possible, i.e., until no $q\_i$ has a denominator dividing $n$. The curent state at that point is the output.

> **Comments:**
> **username_8**: This doesn't look simple at all. I can't imagine the shortest implementation of that would be smaller than of RULE 110 in any reasonable turing machine, or on the lambda calculus. But I might be wrong.  

---

### Answer by username_9 on 2013-07-03. Score: 5

It depends how you define *simplest*. One of the simplest languages I know are [Iota and Jot](https://en.wikipedia.org/wiki/Iota_and_Jot). A detailed description can be found [here](https://www.nyu.edu/projects/barker/Iota/). Both are Turing-complete languages that use just two symbols (no variables etc.).

Iota programs can be viewed as binary trees with $\*$ at nodes and $i$ at leafs. So the whole program is solely determined by the shape of its binary tree. Any such a binary tree forms a valid program.

Jot is similar, but slightly different. Programs in Jot are (arbitrary) sequences of 1's and 0's. Any such a binary sequence forms a grammatically valid program.


---

### Answer by username_10 on 2013-07-03. Score: 5

If by simple you mean "easy to define" then I would advise [semi-Thue systems](http://en.wikipedia.org/wiki/Semi-Thue_system), a simple family of string rewrite systems.

I often use semi-Thue systems in hardness proofs since they are much simpler to define than lambda-calculus or Turing machines.

> **Comments:**
> **username_1**: Consider adding some more details to improve the quality of your answer.  

---

### Answer by username_11 on 2013-07-03. Score: 1

A *Turing Machine*, informally, consists of a set of states along with an infinite tape with a read head, and a set of rules: When you read symbol $x$ and are in state $q$, write symbol $y$, go to state $q'$, and move either left or right. I do not know of any Turing-complete system of computation that is simpler to explain to, say, a layperson, than that.

The formal definition of a Turing Machine seems to me at least as brief as the formality required to define, say, the $\lambda$-calculus, the $\mu$-recursive functions, or the Game of Life.


---

### Answer by username_2 on 2013-07-03. Score: 0

the classic [Post Correspondence Problem](http://en.wikipedia.org/wiki/Post_correspondence_problem) is Turing complete and remarkable in its simplicity, its just a string matching question albeit with potentially very long strings.

but on the other hand, the Turing Machine itself is a very simple theoretical concept. some have said that Turing was inspired by [electric] [typewriters](https://en.wikipedia.org/wiki/Typewriter). the 1st commercial electric typewriters appeared in the ~1920s and the [TM](https://en.wikipedia.org/wiki/Turing_machine) was invented in 1936. also stock teletype machines, originally invented by Edison, had been in widespread use at the time.

some plausible case can be made that all Turing complete systems are exactly as/equally simple.


---

### Answer by username_2 on 2013-07-03. Score: 0

the [Game of Life](http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life) cellular automaton, which has very simple update rules and was an early scientific/mathematical/computational example that exhibits/demonstrates [emergence](http://en.wikipedia.org/wiki/Emergence), is Turing complete, with the proof initially credited to [Conway](http://en.wikipedia.org/wiki/John_Horton_Conway) but it seems to be unpublished. [Paul Rendell](http://rendell-attic.org/gol/tm.htm) has constructed versions of a TM running inside of Life.


---

### Answer by username_2 on 2013-07-03. Score: 0

the question of whether there are integer solutions to Diophantine (ie simple algebra) equations is a simple mathematical question, aka [Hilberts 10th problem](http://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem). the Greeks pondered variations on diophantine equations two millenia ago [and Egyptians even earlier], also suggesting its a relatively simple concept. the *proof* that it is Turing complete on the other hand is complex and took ~¾ century to resolve after posed by Hilbert as completed by [Matiyasevich](http://en.wikipedia.org/wiki/Yuri_Matiyasevich) (building on earlier work by Davis/Robinson/Putnam).


---

