Turing Languages

Turing machines are probably told to be impractical because of the initial description given by their author, which is accordingly rudimentary. However, at each step, Turing modifies the syntax in accordance with his goals.

We shall describe each of the languages successively used by Turing by making explicit its grammar, justifying every new syntactical feature, confronting Turing’s statements with his practice. The modern theory of programming languages will be used as a pedagogical tool to explain these languages.

We will thus see that Turing used three families of languages to describe the behaviour of his machines: first a pyramid of explanatory languages (“complete tables” and “abbreviated tables”), which make the behaviour of the machines understandable for the human reader; then a computing language, which is the only “programming language” and allows in particular for the execution of a machine description by another machine; finally a proving language, for the mathematician to highlight properties of computable numbers.