Sign up ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

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 ?

share|improve this question

closed as primarily opinion-based by MichaelT, Snowman, Kilian Foth, durron597, Dan Pichelman Oct 28 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.

Ok then, define "programming language" ;) Is Latex a programming language? (see: – Yannis Oct 31 '12 at 3:23
Did you follow the link? Here's another one: – Yannis Oct 31 '12 at 3:26
@Vatine: Lambda Calculus and Combinator Calculus have neither looping constructs nor branching constructs, yet they are Turing-complete. Lambda Calculus only has function abstraction and function application. It doesn't even have named recursion! – Jörg W Mittag Nov 2 '12 at 15:52
@JörgWMittag Yes, but it also has "lazy semantics", and that (combined with and/or) is enough to get you a choice. Looping constructs then come trivially with the help of the Y-combinator. – Vatine Nov 5 '12 at 11:54

1 Answer 1

up vote 17 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.

share|improve this answer
+1 for the last paragraph. It's good to remember this from time to time. – h0b0 Oct 31 '12 at 7:57
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 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 at 15:50

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