Where it is accepted that a language has to be Turing complete to be any good, is it actually possible to have a 'useful' programming language that isn't Turing complete?

I should clarify that this is quite specifically about 'programming' languages in the traditional sense, and not markup or query languages.

  • 3
    @PhonicUK SQL wasn't turing complete at first
    – Ryathal
    Commented Oct 30, 2012 at 15:10
  • 4
    @Ryathal SQL isn't a programming language, it's a query language.
    – yannis
    Commented Oct 30, 2012 at 15:11
  • 2
    @PhonicUK your question in comment is actually worthwhile, change the posted question to that or it's going to get closed as not constructive. There are actually useful non-turing complete languages, and I would be interested to hear details of them. Commented Oct 30, 2012 at 15:11
  • 5
    regex isn't turing complete yet it is widely used Commented Oct 30, 2012 at 15:40
  • 3
    @DavidHammen Actual implementations are limited, yes, because of the limits of our physical universe (can only build finite memory, can only run the machine for a limited time before it malfunctions). But that does not mean the languages are limited. IOW a turing complete language's spec does not require an implementation from imposing such limits on an program, whereas a non-TC language requires, for instance, a proof of termination.
    – user7043
    Commented Oct 30, 2012 at 17:05

8 Answers 8


Coq, Agda, HOL and ACL2 are very useful and extremely powerful languages, although they're not Turing-complete.

A common feature that renders them non-Turing-complete is the fact that it is always possible to prove termination. A very simple limitation is enough: recursive calls are only allowed on provably structurally smaller terms. Therefore while it is not possible to implement an interpreter for a Turing-complete language or even for the language itself many other useful things are still possible, like a certified C compiler.

  • 2
    For those not familiar with those languages, could you go into more detail about what they're missing that makes them not Turing complete, and some examples of things built with those languages?
    – PhonicUK
    Commented Oct 30, 2012 at 15:17
  • 9
    @PhonicUK: a C compiler is not a C implementation. It's a tool that transforms code in one language (C) into another one (usually machine code). That does not mean that the C compiler itself is equivalent to any random C program. Commented Oct 30, 2012 at 15:52
  • 9
    @PhonicUK, you cannot implement an interpreter for a Turing-complete language in a non-Turing-complete one. But you can implement a compiler, of course (since a Turing-complete CPU will do an actual evaluation).
    – SK-logic
    Commented Oct 30, 2012 at 15:52
  • 12
    @SK-logic: "Of course?" It's only possible for C because that's a fairly simple language. It's not possible for C++ because a compiler has to interpret template code (which is Turing-complete at compile time).
    – MSalters
    Commented Oct 30, 2012 at 15:58
  • 13
    @MSalters Yes, if compiling the language is turing complete, a compiler for it must be written in a turing complete language. Which is also kinda obvious (not to say tautological). However note that the C++ standard permits limits on the input programs, such as a maximum evaluation depth for template instantiations (and existing implementations take this liberty). If I'm not mistaken this means a non-turing complete C++ compiler may be possible (barring unrelated issues, of course).
    – user7043
    Commented Oct 30, 2012 at 16:03

I would think Yegge's term "mini-language" refers to the fact that it is often useful to use a language for specific problems where the language doesn't require turing-completeness to accomplish the task, and this goes to the heart of how non-turing complete languages can be useful. https://sites.google.com/site/steveyegge2/language-grubbing

Wikipedia answers this very well, right in line with what my gut said. First I was thinking pure math then I remembered regexp, and Wikipedia lists Epigram which I believe would be in the 'pure math' vein.


Non-Turing-complete languages

Many computational languages exist which are not Turing complete. One such example is the set of regular languages, most commonly regular expressions, which are generated by finite automata. A more powerful but still not Turing-complete extension of finite automata is the category of pushdown automata and context-free grammars, which are commonly used to generate parse trees in an initial stage of program compiling. Further examples include some of the early versions of the pixel shader languages embedded in Direct3D and OpenGL extensions, or a series of mathematical formulae in a spreadsheet with no cycles.[citation needed] In total functional programming languages, all functions are total, and must terminate, such as Charity and Epigram. Charity uses a type system and control constructs based on category theory, whereas Epigram uses dependent types.

Data languages

The notion of Turing-completeness does not apply to languages such as XML, JSON, YAML and S-expressions, because they are typically used to represent structured data, not describe computation. These are sometimes referred to as markup languages, or more properly as "data description languages".

It also mentions data structure representations are not languages, but I would think XSLT should count as a representation of computation, XPath perhaps not based on what Yannis said above about SQL being a query language and not a computation language. Perhaps T-SQL or PL/SQL count as computation languages though since you can do a great deal of computations using their aggregates, where the generalized form of SQL doesn't specify aggregates perhaps.


I understand SQL is quite popular among business types

  • 3
    SQL is a query language, not a programming language.
    – PhonicUK
    Commented Oct 30, 2012 at 15:47
  • 4
    @PhonicUK: and what exactly is the difference between a query language and a programming language? Commented Oct 30, 2012 at 15:52
  • 9
    @PhonicUK - Tex is a text markup language and it's Turing complete Commented Oct 30, 2012 at 15:54
  • 4
    modern sql implementations, as far as I know, are turing complete.
    – shabunc
    Commented Oct 30, 2012 at 16:03
  • 6
    @shabunc IIRC only with stored procedures. The arguement does get a bit circular, if it's not Turing complete then it's not a programming language - therefore all "programming" languages are TC Commented Oct 30, 2012 at 16:07

Turing completeness is necessary for a language to be fit for use as a general purpose language. But it is not sufficient, i.e. just because it is Turing complete, it is not suited for every problem domain:

  • Whitespace is proven to be Turing complete but is obviously unsuited for any problem domain outside of programmer entertainment.
  • C++ templates have been proven Turing complete, still you wouldn't actually ever write whole programs with them.

Conversely a DSL is suited for the problem domain it was designed for (assuming it was in fact decently designed), even without Turing completeness:

  • HTML* provides a concise way to describe a DOM tree. While JavaScript is Turing complete and can be used to do just the same, it is far more noisy and unclear
  • XPath and other query languages, PCRE without embedded code and such are all powerful tools for the single job they were designed for

* IIRC it was proven that HTML with CSS animations is Turing complete by using them to implement Conway's Game of Life on an array of checkboxes. But the usefulness of HTML holds even in browsers that do not support CSS animations.

  • 2
    Do you have a link to Conway's Life implemented in CSS?
    – RBerteig
    Commented Oct 30, 2012 at 19:10
  • I don't know of a CGOL implementation in CSS, but I know that Rule 110 was implemented. Can't seem to find it though, it appears to have been moved. Commented Oct 30, 2012 at 20:22
  • 2
    @ChristianMann, this one? raw.github.com/elitheeli/stupid-machines/master/rule110/…
    – SK-logic
    Commented Oct 30, 2012 at 20:59
  • -1 Very interesting but does not address the asked question
    – mattnz
    Commented Oct 31, 2012 at 3:43
  • 2
    @mattnz: Wrong. I give concrete examples of non-Turing-complete languages that are useful, which I think is an appropriate response to "Is it actually possible to have a 'useful' programming language that isn't Turing complete?", not unlike another answer here
    – back2dos
    Commented Oct 31, 2012 at 9:48

There actually do exist programming languages, where you can only write "efficient" programs. Efficient in this sense means that every program written in such a language represents a language in P. Bellantoni, Niggl and Schwichtenberg describe such a language here.


The C preprocessor is not Turing-complete (by design), yet it can still implement an interpreter for a language that is Turing complete (Order-the-language, as described in the documentation, is basically just a run-of-the-mill purely functional ML/Scheme type thing, and would be relatively unremarkable - probably quite nice to use - if it weren't for the unusual implementation).

The trick behind it is similar to the arguments above about implementing any Turing machine in a finite physical universe: the C preprocessor can't provide an infinite number of steps, or data cells, to the language, but it can:

  1. provide an unreasonably large dynamic number (2^64 or so by default), large enough for solving most realistic problems using an exponential expansion process (mumble mumble lifetime of the universe mumble).

  2. use an arbitrary static cap for the above number, i.e. while the number of steps must be some finite number, you can change what the specific cap is at "compile"-time by changing the static settings of the interpreter engine. Since there is no (theoretical) limit on the actual value of this cap, it can (theoretically) be extended to fit the space requirement for any terminating program.

Not to argue that Order is necessarily "useful" in itself, or that any CPP-implemented engine would be, but it's an interesting proof of concept. It's also supposedly dynamically typed, which is unusual for this area.

  • Upvote for mumbling in the middle of the lecture.
    – jpaugh
    Commented Feb 7, 2018 at 23:45

Yes, indeed it is possible to have a useful language that isn't Turing complete. See here: http://tkatchev.bitbucket.org/tab/examples.html

Another example of a useful Turing incomplete language is SQL. (And yet another is spreadsheets like Gnumeric or Excel, though they aren't really programming languages.)

As to why you would want a language that isn't Turing complete: because that allows you to make some strong guarantees about runtime behavior.

Turing completeness, put plainly, means having a capacity for recursion. Having recursion means having potentially unbounded structures in memory. Since in the real world memory is not infinite, Turing completeness requires memory management and/or garbage collection.

Banning recursion is a great way to avoid the really, really hard problem of resource management.

Nota bene! Being Turing incomplete doesn't necessarily imply that any program will necessarily terminate. A Turing incomplete language could allow evaluating an infinite lazy list.


One interesting "sub-Turing programming language" wasn't mentioned until now so I'll add it.

It's called "Crema". It describes itself as:

Crema is a LLVM front-end that aims to specifically execute in sub-Turing Complete space. Designed to be simple to learn, and practical for the majority of programming tasks needed, Crema can restrict the computational complexity of the program to the minimum needed to improve security.

It's quite minimalistic and rather low level.

It should look kind of familiar to C developers.

It was initially funded by the Defense Advanced Research Projects Agency (DARPA) but looks quite unmaintained at the moment of writing. But maybe someone is interested nevertheless.

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