Turing Languages

Mélès Baptiste
Language of the article : French
DOI: 10.3406/intel.2020.1947
Product variations: 


Paper format

to download freely

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.

Pour citer cet article :

Mélès Baptiste (2020/1). Turing Languages. In De Glas Michel & Lassègue Jean (Eds), Looking Back at Turing: His Heritage Today, Intellectica, 72, (pp.81-110), DOI: 10.3406/intel.2020.1947.