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 ?


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.