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.

“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

Is SQL Turing complete? I doubt it.

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?

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.

The SQL standard itself is Turing complete.

Just what I was thinking.

It is not. sql depends on axioms of relational algebra and not turing axioms, in order to be correct.

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

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

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

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 🙂

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

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

@Siah @Jakob

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

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

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

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?

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

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

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

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

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

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