I've never been happy with the hand-wavy, almost circular definition of Turing completeness. We all know the "simulating a Turing machine/computing any function" bit, but what does that really mean? From a practical standpoint, what does a language need to be Turing complete? What key concept separates things like HTML and regular expressions from "real" programming languages?
I believe Petzold said this concept was controlled repetition. Conditionals and loops/jumps/recursion. This example, while nifty, doesn't show that HTML+CSS is Turing complete, because the user still has to provide the looping.
This example, while nifty, doesn't show that HTML+CSS is Turing complete, because the user still has to provide the looping.
That's like saying that my computer isn't a Turing machine (modulo finiteness of memory) because I need to plug it into a socket to run it. Turing machines are a very abstract notion of computation (and one of the most general ones we know of), and a lot of things can be used to simulate one. Turns out HTML+CSS3 is yet another such thing.
Comments
I've never been happy with the hand-wavy, almost circular definition of Turing completeness. We all know the "simulating a Turing machine/computing any function" bit, but what does that really mean? From a practical standpoint, what does a language need to be Turing complete? What key concept separates things like HTML and regular expressions from "real" programming languages?
I believe Petzold said this concept was controlled repetition. Conditionals and loops/jumps/recursion. This example, while nifty, doesn't show that HTML+CSS is Turing complete, because the user still has to provide the looping.
If you don't like `Turing complete', use `Lambda-calculus isomorph', or `Post-correspondence-system isomorph'.
Turing completeness is not hand-wavy, or circular.
Or look up SKI-calculus (http://en.wikipedia.org/wiki/SKI_calculus), if you want to be gob-smacked.
This example, while nifty, doesn't show that HTML+CSS is Turing complete, because the user still has to provide the looping.
That's like saying that my computer isn't a Turing machine (modulo finiteness of memory) because I need to plug it into a socket to run it. Turing machines are a very abstract notion of computation (and one of the most general ones we know of), and a lot of things can be used to simulate one. Turns out HTML+CSS3 is yet another such thing.