Les langages de Turing

Si les machines de Turing sont réputées inutilisables, c'est parce qu'on prête souvent davantage attention à la rudimentaire description initiale proposée par leur inventeur qu'à son souci constant d'adapter la syntaxe de leur description aux objectifs poursuivis.

Nous décrirons chacun des langages successivement adoptés par Turing en en explicitant la grammaire, en justifiant chaque innovation syntaxique et en confrontant aux déclarations d'intention de Turing sa pratique effective. L'exposition de ces langages sera également éclairée, à titre pédagogique, par la théorie moderne des langages de programmation.

Nous verrons ainsi que Turing a proposé trois familles de langages pour décrire le fonctionnement de ses machines : d'abord tout une pyramide de langages explicatifs (« tables complètes » et « tables abrégées »), voués à rendre intelligible au lecteur humain le fonctionnement des machines ; puis un langage calculatoire, seul véritable « langage de programmation », permettant notamment l'exécution d'une description de machine par une autre machine ; enfin un langage démonstratif, réservé au mathématicien pour la mise au jour de propriétés des nombres calculables.