HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Clear, complete, proof that a language is Turing Compete?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
competelanguagecompletethatclearturingproof

Problem

I have seen web sites that purport to "prove" that HTML5+CSS is Turing Complete.

I have seen web sites that purport to "prove" that SQL is Turing Complete.

I have seen a bunch of web sites that purport to "explain" what it means to be Turing Complete.

Enough!

Where can I find a book (written by an expert in computability theory) or a peer-reviewed article (in a reputable journal) that shows a proof of, "This language XYZ is capable of describing a computational machine which has the same computational power as a Turing Machine"?

Solution

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

Context

StackExchange Computer Science Q#14697, answer score: 12

Revisions (0)

No revisions yet.