Return to Revisions

Every language that can implement two counters $C_1, C_2$ (i.e. two registers that can store two arbitrarily large integers) and a program made with a labeled sequence of these two elementary instructions is Turing complete:

• ADD $1$ to counter $C_i$, GOTO instruction $I_j$
• SUBTRACT $1$ from counter $C_i$ if $C_i > 0$ and GOTO instruction $I_j$; otherwise (if $C_i = 0$) GOTO instruction $I_k$

The result is proved in:

Marvin L. Minsky, "Recursive Unsolvability of Post's Problem of Tag and other Topics in the Theory of Turing Machines" (1961)

Don't forget that a programming language can be considered Turing complete only if it supports access to infinite memory (i.e. space) or can store (in some form) arbitrarily large integers.