Reading a recent question: Is it actually possible to have a 'useful' programming language that isn't Turing complete?, I've come to wonder whether non Turing-complete programming languages are considered programming languages at all.

Since Turing-completeness means a language has to have variables to store values as well as control structures ( for, while )... Is a language that lacks these features considered a programming language ?

closed as primarily opinion-based by user40980, user22815, Kilian Foth, durron597, Dan Pichelman Oct 28 '15 at 18:42

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question.

up vote 18 down vote accepted

Whether or not you want to call them "programming languages" depends on your definition, but it my view the answer is yes: you can regard a non-turing complete language as a programming langauge.

Consider the following definition (from Wikipedia):

A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely.

A non-turing complete DSL could easily meet all of these requirements. You can't necessarily express all algorithms (this would require Turing completeness), but you could express enough algorithms to be useful in the given domain.

Also as a slightly pedantic but philosophically important point - modern computers are actually finite state machines so are not strictly turing complete (Turing completeness actually requires infinite memory....). So in some sense, no language as currently implemented on a modern computer is Turing complete.

  • 2
    +1 for the last paragraph. It's good to remember this from time to time. – h0b0 Oct 31 '12 at 7:57
  • 8
    You have to distinguish between the language and its implementation. It is not physically possible to have Turing-completeness in the real world because (as far as we know) the universe is finite. However, you can still have a language that is Turing-complete, you just cannot faithfully implement it. But, for example, C is not even theoretically Turing-complete: the language specification guarantees that you can take the address of an arbitrary piece of memory, and it guarantees that you can store this address in a pointer of finite size. Yet, C is considered a programming language. – Jörg W Mittag Nov 2 '12 at 15:50
  • @Jörg W Mittag: Very good point. Do you know if there is a formal way to distinguish between languages that we consider intuitively as Turing complete (like C or Lisp), and those that we don't? – Giorgio Feb 22 '13 at 11:21
  • Can you provide an example of a language which can express some algorithm but not all? – JacquesB May 18 '15 at 7:06
  • For example, you cannot calculate the Ackermann function in a programming language where you have no recursion and where you can only have loops where the maximum number of iterations must be calculated before the loop starts. – gnasher729 Oct 28 '15 at 15:50

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