3 ms·
SQL is actually Turing-complete; using recursive CTEs, you can build a cyclic tag system, which has been proven to be Turing-complete.
by icebraining 11y ago
SQL is actually Turing-complete; using recursive CTEs, you can build a cyclic tag system, which has been proven to be Turing-complete.
- colanderman 11y agoYou are very correct. I think there is still much to gain even from Turing-complete languages, where the Turing-completeness is relegated to one particular rarely needed construct. Beside the rest of the language being completely analyzable, that one piece that isn't easily stands out as a code smell.
- Avshalom 11y agoYeah the reason there aren't many sub-turing-complete languages is because it's actually really hard to prevent turing completeness.
- Retra 11y agoSQL in its original incarnations is not Turing complete. It's mainly the bastardized, enterprised, heavily-extended versions built by people who have to sell it that are Turing complete.
- colanderman 11y agoTo be fair, recursive CTEs are somewhat a blessing when you need to compute transitive closures. It is just unfortunate that they were designed as generative constructs (= you can create and recur on rows out of thin air rather than only products of other finite relations).
- bordercases 11y agoTuring-hard then?
- mappu 11y agoRecursive CTE's aren't universally present in SQL engines (e.g. MySQL doesn't have them)