Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
1  
@PhonicUK SQL wasn't turing complete at first –  Ryathal Oct 30 '12 at 15:10
3  
@Ryathal SQL isn't a programming language, it's a query language. –  Yannis Rizos Oct 30 '12 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. –  Jimmy Hoffa Oct 30 '12 at 15:11
3  
regex isn't turing complete yet it is widely used –  ratchet freak Oct 30 '12 at 15:40
2  
@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. –  delnan Oct 30 '12 at 17:05

5 Answers 5

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.

share|improve this answer
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 Oct 30 '12 at 15:17
7  
@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. –  Joachim Sauer Oct 30 '12 at 15:52
8  
@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 Oct 30 '12 at 15:52
8  
@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 Oct 30 '12 at 15:58
7  
@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). –  delnan Oct 30 '12 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.

http://en.wikipedia.org/wiki/Turing_completeness#Non-Turing-complete_languages

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.

share|improve this answer

I understand SQL is quite popular among business types

share|improve this answer
3  
SQL is a query language, not a programming language. –  PhonicUK Oct 30 '12 at 15:47
3  
@PhonicUK: and what exactly is the difference between a query language and a programming language? –  Joachim Sauer Oct 30 '12 at 15:52
5  
@PhonicUK - Tex is a text markup language and it's Turing complete –  Martin Beckett Oct 30 '12 at 15:54
3  
modern sql implementations, as far as I know, are turing complete. –  shabunc Oct 30 '12 at 16:03
5  
@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 –  Martin Beckett Oct 30 '12 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.

share|improve this answer
2  
Do you have a link to Conway's Life implemented in CSS? –  RBerteig Oct 30 '12 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. –  Christian Mann Oct 30 '12 at 20:22
2  
@ChristianMann, this one? raw.github.com/elitheeli/stupid-machines/master/rule110/… –  SK-logic Oct 30 '12 at 20:59
    
-1 Very interesting but does not address the asked question –  mattnz Oct 31 '12 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 Oct 31 '12 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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