39

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.

PhonicUK
  • 1,047
  • 3
  • 11
  • 12
  • If it is Turing Complete, it is as "good" as any other (even [whitespace](http://en.wikipedia.org/wiki/Whitespace_(programming_language))). – Zenon Oct 30 '12 at 15:08
  • Is it actually possible to have a 'useful' programming language that isn't Turing complete? – PhonicUK Oct 30 '12 at 15:10
  • Assembly has no features and is still good for certain things, so omission can't make a language universally bad. What could a language have added that makes it universally bad? That doesn't sound like a constructive or rational question because all programming language features came about for a reason, somebody had a use for them. So the only language features that would be universally bad you'd have to make up, maybe the feature of compilation requiring blood sacrifice, that would be a pretty objectively bad language feature. – Jimmy Hoffa Oct 30 '12 at 15:10
  • 3
    @PhonicUK SQL wasn't turing complete at first – Ryathal Oct 30 '12 at 15:10
  • 4
    @Ryathal SQL isn't a programming language, it's a query language. – yannis 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
  • 1
    @Zenon That too depends entirely on the definition of "good". Yours seems to be "is turing complete" -- which, if you ask me, is an awful and entirely useless metric for anything except computability theory. For most sane definitions of "good" in the context of programming (such as tooling support, ease of producing the solution, maintainability of the resulting program, etc.), turing tarpits are decidedly not "good". –  Oct 30 '12 at 15:13
  • @delnan, I agree, but thanks to this first comment the question evolved in something way more interesting :) (IMHO). – Zenon Oct 30 '12 at 15:15
  • you might be interested in studying about [Malbolge](http://en.wikipedia.org/wiki/Malbolge) "it was specifically designed to be impossible to write useful programs in..." – gnat Oct 30 '12 at 15:24
  • 1
    In answer to your original question: I consider treating everything as a variable (rather than as keywords and constants) to be objectively bad. E.g., allowing assignments like `IF := 5;`, `True := False;`, or, worst of all, `2 := 1;` There are serious languages which allow such assignments. – Brian Oct 30 '12 at 15:37
  • 5
    regex isn't turing complete yet it is widely used – ratchet freak Oct 30 '12 at 15:40
  • What real programming language is Turing complete? Languages have implementation limits that essentially render them incomplete. – David Hammen Oct 30 '12 at 16:47
  • 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. –  Oct 30 '12 at 17:05
  • @delnan - IMO, as soon as a standard allows limits, the language is not Turing complete. A program that runs on a real computer is not Turing complete. It's a poor man's substitute for Turing completeness, just as `double` and `float` are poor man's substitutes for the reals. – David Hammen Oct 30 '12 at 17:50
  • 2
    @DavidHammen I disagree, as you might have guessed. One can write a program in such a programming language and *prove* that it emulates any turing machine perfectly. Whether there is an implementation which can act it out for *all* inputs is irrelevant. We now *know* that the language won't be the thing limiting us. Yes, we have actual limits due to unrelated issues, but you don't refuse to write numbers because you can't write out almost all of them, do you? ;) –  Oct 30 '12 at 18:12
  • Would you care to provide a source that defines programming languages in such a way that they exclude query languages? – back2dos Oct 30 '12 at 21:56
  • FWIW: All implementations of computer languages are not turing machines. That's because turning machines have infinite tapes. Well computers in the real world cannot have infinite memory. But they have enough memory to be useful and look like a turing machine for most cases. – Thomas Eding Oct 30 '12 at 22:08
  • Our computers are not Turing machines, but “bounded storage machines”, so Turing-completeness is technically irrelevant—every TC language can describe computations that no real machine can run. – Jon Purdy Oct 31 '12 at 06:35
  • Even though no Turing machine can really be implemented on a computer, it's still infinitely more practicable to analyse a computer as a Turing machine (or as a While machine or a beta-reducer for Lamda terms) than as an automata with about 2^(8*2^30) states (for a computer with 1 GiB of RAM and no registers) – MauganRa Oct 11 '16 at 16:11

8 Answers8

52

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.

Matteo Acerbi
  • 3
  • 1
SK-logic
  • 8,497
  • 4
  • 25
  • 37
  • 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
  • @PhonicUK, see an updated answer – SK-logic Oct 30 '12 at 15:21
  • If a Turing complete language can be implemented using a language that is (nominally) non-Turing-complete, could the argument not be made that this in fact makes it Turing-complete by extension? – PhonicUK Oct 30 '12 at 15:50
  • 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. – Joachim Sauer Oct 30 '12 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 Oct 30 '12 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 Oct 30 '12 at 15:58
  • @MSalters, true, a compiler for any language with powerful enough metaprogramming capabilities would require a Turing-complete evaluator. Fortunately, it is always possible to isolate such unclean Turing-complete fallback bits in most of the languages of this kind, keeping the rest of the code nice, clean and provable. – SK-logic Oct 30 '12 at 16:01
  • 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). –  Oct 30 '12 at 16:03
12

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.

Jimmy Hoffa
  • 16,039
  • 3
  • 69
  • 80
10

I understand SQL is quite popular among business types

Martin Beckett
  • 15,776
  • 3
  • 42
  • 69
  • 3
    SQL is a query language, not a programming language. – PhonicUK Oct 30 '12 at 15:47
  • 4
    @PhonicUK: and what exactly is the difference between a query language and a programming language? – Joachim Sauer Oct 30 '12 at 15:52
  • 9
    @PhonicUK - Tex is a text markup language and it's Turing complete – Martin Beckett Oct 30 '12 at 15:54
  • Other than the 'intended purpose' (In SQLs case, the retrieval and manipulation of data stored in a database) - not a right lot. – PhonicUK Oct 30 '12 at 15:55
  • @PhonicUK SQL is a query programming language. – Pieter B Oct 30 '12 at 15:59
  • 4
    modern sql implementations, as far as I know, are turing complete. – shabunc Oct 30 '12 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 – Martin Beckett Oct 30 '12 at 16:07
  • SQL:2003 is Turing-complete, versions before that are not. – Jörg W Mittag Oct 30 '12 at 17:43
  • 1
    I think if we say that SQL is not a *general-purpose* programming language, more of us can agree to that. AWK is another example of an extremely useful language that you'd be hard pressed to call general-purpose. xslt comes to mind as well. Any truly domain-specific language will probably no longer be general-purpose. – GlenPeterson Oct 31 '12 at 04:05
5

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.

back2dos
  • 29,980
  • 3
  • 73
  • 114
  • 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? https://raw.github.com/elitheeli/stupid-machines/master/rule110/rule110-full.html – SK-logic Oct 30 '12 at 20:59
  • -1 Very interesting but does not address the asked question – mattnz Oct 31 '12 at 03: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](http://programmers.stackexchange.com/a/172890/667) – back2dos Oct 31 '12 at 09:48
3

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.

SpaceTrucker
  • 1,462
  • 10
  • 13
1

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.

Community
  • 1
Alex Celeste
  • 841
  • 8
  • 15
-1

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.

tkatchev
  • 1
-1

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.

Mateusz Kowalewski
  • 1