Skip to main content
3 of 4
added 483 characters in body
Vor
  • 12.7k
  • 1
  • 30
  • 62

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.

You can also find a lot of references on the Wikipedia pages on RAM model and RASP model.

Finally a nice book focused on the equivalence of different models of computation is:

"Models of Computation: An Introduction to Computability Theory", by Maribel Fernandez

Vor
  • 12.7k
  • 1
  • 30
  • 62