News for hackers. Stuff that matters.
Re:HTML + CSS3 is Turing complete by msarnoff on Tuesday March 08, 2011 @01:16PM (#2301922)
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.

Re:HTML + CSS3 is Turing complete by eru on Tuesday March 08, 2011 @05:28PM (#2302857)
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.

Re:HTML + CSS3 is Turing complete by sid0 on Tuesday March 08, 2011 @01:43PM (#2302039)
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.