Why is Turing completeness the criterion for determining whether a particular computer language is a ‘ programming language ‘?

With programming , we generally mean imperative programming, that is to say: capturing a set of instructions (the program) most of which are commands to be executed.But a series of such assignments is not usually called a program yet. We only speak of a program if tests can also be done and the executed sequence of assignments can be dependent on the test result. This means that an if or similar construction is present in the language. In addition, when talking about programs, we expect that repetitions of sequences of assignments are possible, such as a whileor forconstruction.

You already have a Turing full language, if at least one additional condition is met: the set of different values or objects that a program can work with must be infinitely large.For example, a language in which the only objects you can work with are natural numbers, only Turing can be complete if that collection is infinitely large. For most programming languages, this is not the case: in C for example, the data type int, which represents integers, is finite, Where maxint is the largest possible number. The set of C programs that only edit intS is strictly speaking not Turing completely.The same type of reservation is made for C programs that edit other types of data.

It’s just that you barely see that: most C-code that edits ints hardly shows that those ints are limited in size.That’s because most ints In practice are much Smaller Than maxint and also don’t threaten to become so big.C-code that edits ints therefore looks exactly like the C-code you would write if ints could be randomly large, except that in those places where it is (how much there is depends on the program) additional tests on the size of an int have been added, or certain operations that could make the used ints too large, for example, an average is not calculated with (A + B)/2, but for example with A/2 + b/2 + a% 2 + b % 2.

C programs look substantially like programs in a Turing full language, with some modifications here and there to overcome the finiteness of the values domains.The most essential elements for Turing completeness, namely conditional execution (if) and arbitrary repetition (while, for, Goto), are present in C.

In contrast, common Lisp, which actually allows arbitrarily large integers, is really Turing completely, although when executing a Common Lisp program integers will not be able to actually be randomly sized because the program memory on a certain monent overflows; That Istaan does not preclude the Turing completeness of the Common Lisp language, because it is not a limitation of the program, but of the machine it is running on.But in practice, of course, you have to take about the same kind of precautions in your program if you have to do in C.

With Turing completeness It is therefore usually meant: the possibility of conditional execution and arbitrary repetition, or something equivalents.The requirement to be able to work with infinitely large values collections is not always implied. (C can do that, by working with external data sources, for example tape drives; The length of a tape is not limited).

You also have all sorts of languages that are not strictly imperative in nature, such as SQL, Haskell, and Prolog.Also for such languages is that they are Turing complete, or at least have constructions that are as powerful as the conditional execution and arbitrary repetition of imperative languages. If they are less powerful, which some domain-specific languages may want to avoid, such as the original SQL, there is not a fast tendency to speak of a programming language, because you do not have the expression force that conditional execution and arbitrary repetition. The Makefiles that traditionally compile C programs for example are never called programs, and I think that would happen if the rules in makefiles Turing were complete.

Data description languages and text markers, such as JSON and HTML, are much less Turing complete: there is no conditional execution or random repetition in it at all.You could add that, and for example, extend HTML to a language that specifies how to generate HTML Web page content based on variable input. Such a language could be very useful in practice. I think that the tendency would arise to call that language a programming language if he is full, and otherwise not, and the tendency would be stronger if the language has an imperative character. This is also the fact that CSS (which does not have conditional execution and random repetition) is not called a programming language, and XSLT (which it does know but is not imperative) sometimes does.

All this far-sighted I think it can be argued that so few language resources are needed to make a Turing programming language complete that almost all programming languages are, and that non-Turing completeness the user of a language so serious restrictions in Expression Force, that the use of such a language does not feel like programming, and therefore is not so called.

Leave a Reply