13

Non-Turing complete languages offer a great advantage over Turing-complete languages as they are much more analyzable and, thus, offer much broader optimization possibilities. Yet they are barely used and Turing-completeness is actually sold as a good feature.

Are there any mainstream non-Turing-complete languages available today that are made for general-purpose programming?

  • 8
    I think the two things you're looking for are mutually incompatible. If it's non-turing complete, then it can't be turned to any arbitrary use. – Bobson Jun 24 '13 at 1:21
  • @Dokkat I've re-opened the question and removed the Meta discussion from the comments. Please note that if you happen to disagree with one of the site's guidelines, the proper way to contest it is to post a Meta discussion; not just ignore it. Furthermore, for subjective questions, the key to success is prior research and rigorous definition. The more you research, the more specific (and answerable) your question becomes, and the further away you get from the notorious "not constructive" space. – yannis Jun 24 '13 at 2:04
  • Also, why do you consider "broader optimization possibilities" to be a "great advantage"? This is not to say that optimization is not worthwhile, but I certainly wouldn't call the inherent optimizability of a language a "great advantage" given the power of modern computers. – Bobson Jun 24 '13 at 5:01
  • 2
    Coq can be regarded as pretty "mainstream" in its domain, with competitors (HOL, Agda, ACL and such) being much less visible. – SK-logic Jun 24 '13 at 8:15
  • Perhaps I don't actually understand what turing-completeness is, but how can a language be general purpose and non-Turing complete? I thought the meaning of being non-Turing complete, is not being able to perform any computational task, thus being aimed at a specific purpose..? – Aviv Cohn Mar 4 '14 at 16:28
25

There are no mainstream multi-purpose non Turing complete languages today. There are, however, several non Turing complete domain specific languages. ANSI SQL, regular expressions, data languages (HTML, CSS, JSON, etc), and s-expressions are some notable examples.

There isn't really a benefit for multi-purpose non Turing complete languages. The "much more analyzable" aspect, which I'm assuming is a nod to Rice's theorem, does apply but it doesn't make much sense for languages that target several different application domains, other requirements take precedence. The flexibility of Turing completeness is a lot more important than its complexity. Programming languages, as every other piece of software, are all about trade offs.

For domain specific languages, on the other hand, it might just be the other way around. If you aren't building "one language to rule them all", you are free to implement only the features that make sense for the very specific purpose of your language. And more often than not, Turing completeness is not one of them.

| improve this answer | |
  • CSS3 is Turing-complete. – SK-logic Jun 24 '13 at 8:14
  • 5
    @SK-logic CSS does make sense without HTML, it can be applied to any kind of XML and nothing stops you from implementing it for any other format with roughly compatible shape (trees with named nodes, sibling order, etc). I've personally written CSS rules for a SVG file. It's just far more common for HTML because HTML is far more common than the other formats. – user7043 Jun 24 '13 at 9:10
  • 2
    @Mike, that's a broken analogy. CSS3 semantics is closely tied to the presentation language semantics. – SK-logic Jun 24 '13 at 16:32
  • 2
    Note that SQL with Windowing and CTEs (i.e. SQL:2003) is also Turing-complete. – Jörg W Mittag Oct 8 '16 at 23:13
  • 1
    "There are no mainstream multi-purpose non Turing complete languages today." – C without external storage is not Turing-complete, yet it is very much general-purpose and mainstream. (Well, I personally would argue that it is a Domain-Specific Language for writing Unix kernels, and isn't even particularly good at that, but the world disagrees.) – Jörg W Mittag Oct 31 '19 at 19:45
-3

The reason Turing incomplete languages are not mainstream is that it is easy to implement your own whenever you need it and however you need it. An interesting example is bitcoin-script: https://github.com/bitcoin/bitcoin/blob/master/src/script.cpp

| improve this answer | |
  • 5
    Really? Mind implementing Coq from scratch, on your own, if it's that easy? – SK-logic Mar 4 '14 at 13:28
  • is this only your opinion or you can back it up somehow? – gnat Mar 4 '14 at 13:32
  • Examples are all domain-specific languages which don't need recursion, unbounded iteration or other Turing tarpits. Also, I'm sure most of us have implemented some kind of simple calculators processing basic arithmetic. – MauganRa Oct 11 '16 at 15:51
  • 1
    I agree though that it's not trivial to keep the language Turing-incomplete. Even without obvious Turing tarpits, it could always contain a compiler bug which makes it possible to use one of the underlying platform. – MauganRa Oct 11 '16 at 15:57

Not the answer you're looking for? Browse other questions tagged or ask your own question.