A programming language is Turing complete if it equivalent to a Turing machine. In practice, it means that any algorithm can be implemented. Most programming languages are Turing complete, including SQL, ECMAScript, Java, C, and so on. For years, I have been telling my students that CSS is not Turing complete.

Maybe I need to change my story. Apparently, HTML5 + CSS3 is now also Turing complete because it can be used to program a Rule 110 automaton. I have not yet had time to investigate further. Does it rely on specific features of CSS3 and HTML5? Were previous versions of HTML+CSS also Turing complete?

On Wikipedia, there is a nice story about how when Matthew Cook proved that Rule 110 was Turing complete, Wolfram Research, the egotistical company behind Mathematica, censored the proof using a court order. Cook apparently had the last laugh, as his proof is now available online.  What kind of idiotic company uses court orders to censor the publication of a purely mathematical theorem?

Source: Thanks to Jakob Voß for the pointer.

19 Comments

  1. “Does it rely on specific features of CSS3 and HTML5? Were previous versions of HTML+CSS also Turing complete?”

    My guess: the CSS in the example uses the -nth-of-type(ax+b) pseudo class, which applies to every (ax+b) child, where a and b are constants and by taking x=0, 1, … So the CSS can count arbitrary numbers and even perform elementary arithmetic.

    This pseudo-class is new to CSS3, see:
    http://www.w3.org/TR/css3-selectors/#nth-of-type-pseudo

    Comment by Sylvain Hallé — 8/3/2011 @ 19:10

  2. Is SQL Turing complete? I doubt it.

    Comment by Siah — 9/3/2011 @ 1:23

  3. Well, I (personally) think the manners of the company reflect the owner and creator. A few months ago I read an article about some cellular automata (I don’t remember exactly what the details were, I was just curious, after all I’m in dynamical systems), and his view of the proof/result was… Well, along the lines of “it is not interesting as I have not done it”. This is only from memory, but that’s the impression I got, it can’t be too far off.

    Cheers,

    Ruben

    Comment by Ruben Berenguel — 9/3/2011 @ 6:15

  4. It also relies on human interaction every tick… so don’t get your hopes up about writing all javascript in Lisp anytime soon ;)

    Comment by Mr Speaker — 9/3/2011 @ 6:24

  5. Erm C is not turing complete (except, possibly, with file IO).

    A turing complete programming language would be able to handle unbounded memory. In C all memory must be directly addressable, and all pointers must be castable to a void* which must be of finite size.

    This results in C not being Turing complete :-)

    Comment by Ex — 9/3/2011 @ 6:58

  6. Ex,
    Clearly, no computer is strictly Turing complete, because the storage is always limited. The term TC, is used in a loose form, IMHO. That is, it the language is TC as long, it can simulate a TM with a limited size tape. Yet, there should be no principal limit: if we have a larger computer, we can simulate a larger Turing machine (without changing the program, IMHO).

    Comment by Itman — 9/3/2011 @ 9:13

  7. @Ex: That is incorrect. Obviously real machines are limited in memory and therefore cannot act like true Turing machines; they are technically speaking linear bounded automata. However, real machines are still “said to be” Turing complete if they can meet all requirements except that of unlimited memory. See the second paragraph of http://en.wikipedia.org/wiki/Turing_completeness#Overview .

    Comment by Billy O'Neal — 9/3/2011 @ 9:20

  8. @Siah The current SQL specification is a monster, every RDBMS implements his subset plus some proprietary goodies. So I bet that some dialects of SQL are turing complete. To answer the question, you should first define what you mean by SQL (the latest version of SQL that a test suite was provided for was SQL-92).

    Comment by Jakob — 9/3/2011 @ 10:17

  9. @Siah @Jakob

    By “SQL”, I meant either SQL 2003 or any of the popular dialects.

    Comment by Daniel Lemire — 9/3/2011 @ 16:39

  10. This post censored for violation of the terms of use: “You can criticize me or the other people who post on this blog, but being rude is likely to get your comment deleted. Go start your own blog if you want to be insulting.”.

    Comment by rvasques — 9/3/2011 @ 17:17

  11. About Cook’s proof: as I understand it, he was under NDA regarding the research he was doing for Wolfram (so Wolfram could publish it in his book). Silly NDA, but he should have respected it…

    Comment #3: based on what I’ve seen of Wolfram himself (I was a student at NKS Summer School 2010), that would surprise me. He seems to be extremely curious about what other people make of cellular automata.

    Comment by Marnen Laibow-Koser — 28/11/2011 @ 18:14

  12. Isn’t it scary that even important file formats which are the base of much of our computing world are now so complex they are Turing complete?

    Comment by Christian Berger — 3/3/2012 @ 7:43

  13. @Christian: Yes, but we should keep in mind that the Postscript format, dating back from the 1980s, was already a full-fledged programming language.

    Comment by Sylvain Hallé — 3/3/2012 @ 8:17

  14. This thread may be of interest (especially the comment by usr):
    http://stackoverflow.com/questions/5357725/how-does-this-implementation-of-turing-complete-rule-110-in-html5css3-work

    Comment by Simon — 3/3/2012 @ 14:04

  15. @EX: It is indeed true that their maybe no Turing *machine* due to the bounds on memory but we could easily image a Turing complete language that could scale to the memory size of any machine.

    Comment by Misha — 3/6/2012 @ 15:38

  16. @Misha: What looping construct exists in CSS and HTML? A turing machine needs such a construct.

    Comment by Billy O'Neal — 3/6/2012 @ 21:14

  17. @Billy O’Neal

    Or you need to implement the SKI-calculus, the one instruction processor, some cellular automata or certain rewrite systems. There are a lot of possibilities, you only need to show, that system A is equivalent to system B, which is turing complete and you have proved it.

    Comment by flip — 2/3/2013 @ 5:47

  18. @flip: My assertion is that showing equivalence to a Turing machine requires a looping construct. Or at least a “goto” construct which could be used to construct a looping construct. For instance, it is easy to build a Turing Machine that runs forever; this is not possible with HTML5 + CSS.

    Comment by Anonymous — 4/3/2013 @ 11:03

  19. @flip: My assertion is that showing equivalence to a Turing machine requires a looping construct. Or at least a “goto” construct which could be used to construct a looping construct. For instance, it is easy to build a Turing Machine that runs forever; this is not possible with HTML5 + CSS.

    Comment by Billy O'Neal — 4/3/2013 @ 11:03

Sorry, the comment form is closed at this time.

« Blog's main page

Powered by WordPress