20

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?

yannis
  • 39,547
  • 40
  • 183
  • 216
MaiaVictor
  • 5,820
  • 7
  • 27
  • 45
  • 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 '13 at 01: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 02: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 05: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 08: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 04 '14 at 16:28
  • @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 '16 at 15:41

2 Answers2

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.

yannis
  • 39,547
  • 40
  • 183
  • 216
  • CSS3 *is* Turing-complete. – SK-logic Jun 24 '13 at 08:14
  • @SK-logic If you are talking about the [HTML5 + CSS3 Rule 110 automaton](https://github.com/elitheeli/stupid-machines), then that's proof that _the combination_ of HTML5 and CSS3 is Turing complete, not CSS3 on its own (which isn't any less impressive). If you are talking about something else, please give me a link, I'm extremely curious. – yannis Jun 24 '13 at 08:46
  • yes, I'm talking about rule110 in html+css. Anyway, css does not make any sense on its own without html. – SK-logic Jun 24 '13 at 08:48
  • 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. –  Jun 24 '13 at 09:10
  • @delnan, yes, and it should be possible to implement rule110 on css3 with nearly any xml renderer, including svg. CSS is meaningless on its own, it only makes sense when used with something like html, and in this case they're likely to be Turing-complete. – SK-logic Jun 24 '13 at 09:48
  • @SK-logic Wouldn't HTML then become meaningless without a web browser (or similar HTMl renderer)? As such wouldn't said browser be meaningless without the underlying operating system? so on and so on... – Mike Jun 24 '13 at 16:22
  • 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 08 '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
  • 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 '20 at 05: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

Adam Kurkiewicz
  • 101
  • 4
  • 7
    Really? Mind implementing Coq from scratch, on your own, if it's that easy? – SK-logic Mar 04 '14 at 13:28
  • is this only your opinion or you can back it up somehow? – gnat Mar 04 '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