Breaking news: HTML+CSS is Turing complete

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.

HTML5 + CSS3 is also Turing complete because it can be used to program a Rule 110 automaton.

Source: Thanks to Jakob Voß for the pointer.

Published by

Daniel Lemire

A computer science professor at the University of Quebec (TELUQ).

29 thoughts on “Breaking news: HTML+CSS is Turing complete”

  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:

    1. Yes, it is. You can have variables, you have if-else structure, you can define loops, even functions and methods. What else would you need?

      1. It is not purely SQL but it is PL/SQL or T-sql which has all the features you mentioned. So, SQL is not Turing complete but pl/SQL and T-sql are.

        1. Yes, and I also remember PL/SQL and even T-SQL not supporting recursion, which isn’t such a big hindrance because it can be provided for by implementing a Y-combinator.

          I have a long-term goal of implementing a mini/micro-Kanren using SQL-PL (under IBM DB2) to perform deductive reasoning over records without incurring the performance penalty imposed by moving data out (and back into) of the database to be reasoned with using something like Datalog (or even Prolog).

  2. @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 .

  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.



  4. 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 🙂

  5. 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).

  6. @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).

  7. 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.”.

  8. 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.

  9. 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?

  10. @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.

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

  12. @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.

  13. @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.

  14. @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.

Leave a Reply to balping Cancel reply

Your email address will not be published.

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    Markdown is turned off in code blocks:
     [This is not a link](

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see

You may subscribe to this blog by email.