11
$\begingroup$

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"?

Improve this question
$\endgroup$
6

2 Answers 2

Reset to default
12
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ "Don't forget that a programming language can be considered Turing complete only if it supports access to infinite memory " Hence there cannot exist an implementation of a Turing Complete language? Is this your conclusion? Or did you want to say that all(most) of the languages we use are Turing Complete because that requirement is easy to achieve? Both conclusions are valid from your answer, as it stands now. $\endgroup$
    – Bakuriu
    Commented Sep 30, 2013 at 16:20
  • $\begingroup$ bakuriu see TM complete & computational power $\endgroup$
    – vzn
    Commented Sep 30, 2013 at 16:26
  • $\begingroup$ @Bakuriu: indeed the sentence is a little bit ambiguous; I only mean that a computational model can be considered Turing complete if - in some form - it allows to use an unbounded storage. Most programming languages are Turing complete because in their (syntax) specifications they don't have limits on the size of variables or pointers, but their implementations are limited; see for example C's <limits.h>. So even if you have a computer with unbounded memory that runs a C implementation, you cannot use that memory unless you provide an "extra mechanism" that is not part of the language. $\endgroup$
    – Vor
    Commented Sep 30, 2013 at 17:00
  • $\begingroup$ Technically, programming language implementations on real computers aren't even a true embodiment of linear-bounded automata, in that they can't accept arbitrary CSLs... for the same reason computers aren't equivalent to Turing machines, i.e., not enough memory. How much memory would a machine need to accept the context-sensitive language $\{w.w \mid w \in \{0, 1\}\}$? I suppose you might object that you'd be able to solve it provided you had enough room to write down the question, but that doesn't change the fact that we can't make a physical model equivalent to LBAs... $\endgroup$
    – Patrick87
    Commented Sep 30, 2013 at 22:43
3
$\begingroup$

The two most widely used text books on computability and complexity theory are:

Michael Sipser: Introduction to the Theory of Computation, 2/e, Cengage, 2005.

John E Hopcroft; Jeffrey D Ullman: Introduction to Automata Theory, Languages and, Computation, Addison-Wesley, 1979.

There is also a beautiful philosophy monograph for lay-people that works through the technical details of computability theory without the formal proofs.

Douglas Hoftstadter: Gödel, Escher, Bach, Basic Books, 1979.

Finally, the best introduction to computability may be a puzzle book by a famous logician:

Raymond Smullyan: The Lady or the Tiger and Other Logic Puzzles, Penguin, 1983. (Now in an inexpensive Dover edition, 2009.)

(He starts with a bunch of puzzles based on the Liar's paradox, and then works you through the construction of a self-referential statement in the guise of a Sherlock Holmes-style puzzle about a mysterious locked box.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.