Return to Answer

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

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 computational model (in your case a programming language + a device that executes programs written in that language) can be considered Turing complete only if it supports access to an unbounded amount of memory (i.e. space) or can store (in some form) arbitrarily large integers. A programming language implementation on a real computer is equivalent to a Linear Bounded Automaton.

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

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.

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

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)

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.