7

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 ?

Community
  • 1
Tulains Córdova
  • 39,201
  • 12
  • 97
  • 154
  • Define "real programming language". – yannis Oct 31 '12 at 03:14
  • @YannisRizos I deleted the phrase "real programming language" to make the question better. – Tulains Córdova Oct 31 '12 at 03:17
  • 2
    Ok then, define "programming language" ;) Is Latex a programming language? (see: http://en.literateprograms.org/Turing_machine_simulator_(LaTeX)) – yannis Oct 31 '12 at 03:23
  • @YannisRizos Can you write programs in LaTeX ? – Tulains Córdova Oct 31 '12 at 03:24
  • 1
    Did you follow the link? Here's another one: http://www.haskell.org/wikiupload/8/85/TMR-Issue13.pdf – yannis Oct 31 '12 at 03:26
  • @YannisRizos I'm reading it. If the answers to this question correct a misconception of mine, then its purpose will be served. – Tulains Córdova Oct 31 '12 at 03:32
  • The definition of programming language is rather vague. Tex may be Turing-complete, but is it a programming language? If we go by mikera's definition, yes it is. But _most_ people would call Tex a typesetting system... – yannis Oct 31 '12 at 03:48
  • 1
    Related: [Measure of power other than Turing completeness](http://programmers.stackexchange.com/questions/812/measure-of-power-other-than-turing-completeness?rq=1) – yannis Oct 31 '12 at 04:19
  • I'd like to note that "All Turing-complete languages need to have variables control structures" does not imply "Non-Turing-complete languages don't have those features". There are languages that aren't Turing complete and that still have variables, for-loops and while-loops. Also it's not true that you need those features to be Turing-complete. There are languages that don't have a concept of variables and are still Turing-complete. And of course there are languages that don't have imperative looping statements and instead use recursion to iterate. Still Turing-complete. – sepp2k Oct 31 '12 at 11:11
  • I would say that there are "control structures" of different kinds. Immediate differences would be between "looping constructs" (for, while, until, ...) and branching constructs (if, switch, cond, ...). Of course, most looping constructs are "branch and transfer of control" under the hood. – Vatine Oct 31 '12 at 12:42
  • 5
    @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 02 '12 at 15:52
  • 1
    @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 05 '12 at 11:54

1 Answers1

18

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.

Tulains Córdova
  • 39,201
  • 12
  • 97
  • 154
mikera
  • 20,617
  • 5
  • 75
  • 80
  • 3
    +1 for the last paragraph. It's good to remember this from time to time. – h0b0 Oct 31 '12 at 07: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 02 '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 07: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
  • There's an example of a non Turing-complete language in the bitcoin transaction system. Each coin has an associated program associated with it which defines who can spend it (such as "the holder of my private key can spend me"). The language is intentionally not Turing complete so that miners, who must execute these scripts while mining, have a guarantee that the script can run in bounded time. – Cort Ammon Oct 29 '15 at 01:11