Lambda Calculus is very simple. Are there even simpler turing-complete systems? Which is the simplest of them all?
$\begingroup$
$\endgroup$
8
-
5$\begingroup$ How do you define "simple"? $\endgroup$– Dave ClarkeJul 3, 2013 at 9:32
-
1$\begingroup$ 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 for more information on what is meant by this. Your question might be suitable for Computer Science which has a broader scope. $\endgroup$– KavehJul 3, 2013 at 17:50
-
1$\begingroup$ 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. $\endgroup$– KavehJul 3, 2013 at 17:52
-
1$\begingroup$ 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 $\endgroup$– vznJul 3, 2013 at 18:31
-
1$\begingroup$ 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. $\endgroup$– vznJul 11, 2013 at 22:42
|
Show 3 more comments
8 Answers
$\begingroup$
$\endgroup$
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.
answered Jul 3, 2013 at 10:38
$\begingroup$
$\endgroup$
1
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.
answered Jul 3, 2013 at 11:22
-
1$\begingroup$ 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. $\endgroup$ Aug 18, 2015 at 5:43
$\begingroup$
$\endgroup$
1
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.
-
3$\begingroup$ Consider adding some more details to improve the quality of your answer. $\endgroup$ Jul 3, 2013 at 9:49
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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).
$\begingroup$
$\endgroup$
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.