Reading
None.
Homework
Study for your Exam!

The concept of "Turing Complete"
The Church-Turing thesis basically says that a Turing machine can be taken as the definition of computation: if a Turing machine can do it, it's computable; otherwise, it's not. Any theoretical computational model, real-world computing device or programming language that can simulate a Turing machine is, therefore, as powerful as a computer can be --- though some are faster, and some are slower. We call such computational devices or programs Turing complete.

Perhaps you've heard people say that HTML is not really a programming language. We can now make that precise: HTML is not Turing complete. You cannot simulate a Turing machine in HTML.

If you're with some computer nerds and one starts spouting off that language X is so much more powerful than language Y, you can shut him up by saying: "They're both Turing complete, so neither is more powerful than the other."


Christopher W Brown