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.

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
Ok then, define "programming language" ;) Is Latex a programming language? (see: en.literateprograms.org/Turing_machine_simulator_(LaTeX)) –  Yannis Oct 31 '12 at 3:23
Did you follow the link? Here's another one: haskell.org/wikiupload/8/85/TMR-Issue13.pdf –  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 15 down vote accepted

Whether or not you want to call them "programming langauges" 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

Your Answer


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.