What are the simplest turing-complete systems? [closed]

Question

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

Answer 1

The Rule 110 cellular automaton (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 2

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.

Answer 3

If by simple you mean "easy to define" then I would advise semi-Thue systems, 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.

Answer 4

It depends how you define simplest. One of the simplest languages I know are Iota and Jot. A detailed description can be found here. 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 5

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 6

the classic 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. the 1st commercial electric typewriters appeared in the ~1920s and the TM 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 7

the question of whether there are integer solutions to Diophantine (ie simple algebra) equations is a simple mathematical question, aka Hilberts 10th 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 (building on earlier work by Davis/Robinson/Putnam).

Answer 8

the Game of Life cellular automaton, which has very simple update rules and was an early scientific/mathematical/computational example that exhibits/demonstrates emergence, is Turing complete, with the proof initially credited to Conway but it seems to be unpublished. Paul Rendell has constructed versions of a TM running inside of Life.