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 ?
12
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.
6