21

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?

Improve this question
6
  • 10
    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, 2013 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, 2013 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, 2013 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, 2013 at 8:15
  • 1
    @Aviv the language has just to be general-purpose enough to implement 99% of all programs we ever need. Of course it's not going to be simple all the time, but there are not many programs which have to be nonterminating (interpreters for Turing-complete langoages for instance, or certain theorem solving procedures)
    – MauganRa
    Oct 11, 2016 at 15:41

2 Answers 2

Reset to default
28

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
10
  • 6
    @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, 2013 at 9:10
  • 2
    @Mike, that's a broken analogy. CSS3 semantics is closely tied to the presentation language semantics.
    – SK-logic
    Jun 24, 2013 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, 2016 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, 2019 at 19:45
  • 1
    @JörgWMittag I think clearly what is meant here is "Turing complete in spirit", or "Turing complete in practice". C is Turing complete in practice because you can declare memory of unbounded size, and many of those DS languages are T-C only technically (i.e. one doesn't use this algorithmic capability in practice because of verbosity inefficiency and complexity).
    – Real
    May 22, 2020 at 5:32
-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
4
  • 7
    Really? Mind implementing Coq from scratch, on your own, if it's that easy?
    – SK-logic
    Mar 4, 2014 at 13:28
  • is this only your opinion or you can back it up somehow?
    – gnat
    Mar 4, 2014 at 13:32
  • 1
    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, 2016 at 15:51
  • 2
    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, 2016 at 15:57

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