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.
“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.
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).
It is not. sql depends on axioms of relational algebra and not turing axioms, in order to be correct.
if you can put “if” statements and “goto”, yes, it’s only what it takes.
Someone implemented a raytracing renderer in SQL…
@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.
Please, take a look into my Kialo discussion about it.
https://www.kialo.com/is-html-a-programming-language-29611?path=29611.0~29611.1&active=~29611.1