La programmatique comportementale de la machine de Turing

L’axiomatique (qui remonte au moins à Euclide) désigne des propositions non démontrables permettant de fonder une logique mathématique. Dès le xviii^e siècle, Leibniz interroge la valeur d’un énoncé mathématique. En imaginant une machine capable de manipuler des symboles, il pose les bases de ce que serait un « langage formel », c’est-à-dire une syntaxe articulée à un vocabulaire symbolique univoque. Tout système formel comporte des thèses, dont certaines sont posées « par principe » (les axiomes) et d’autres comme des énoncés à démontrer. Au début des années 30, Kurt Gödel démontre que tout système formel comporte au moins une thèse qui n’est pas démontrable dans ce système (à l’exception des axiomes qui sont là par principe). Cette démonstration lui permet d’établir que tout système formel est « incomplet » : c’est le théorème d’incomplétude. Dans cette mise en doute de la faculté des mathématiques à parvenir à une valeur de vérité universelle, Gödel nous intéresse parce qu’il désespère d’avance tout « programmeur » de parvenir à réaliser un système formel parfaitement automatisé (un programme) : il y aura toujours une thèse (un bug) qui ne pourra pas être démontrable (envisagée) au sein de ce système.

À la suite de Gödel, Alan Turing va formaliser sa « Machine universelle », qui démontre l’incomplétude résidant dans tout énoncé mathématique. Dans son article « Théorie des nombres calculables, suivi d’une application au problème de la décision³⁵ », il se demande s’il existe une méthode calculable pour savoir si une proposition mathématique peut être démontrable. Turing parvient à rendre visible le fait qu’il existe toujours une thèse indémontrable au sein d’un système : il formalise la démonstration de Gödel sur le principe d’incomplétude. Ainsi, la « machine de Turing » démontre « l’indécidabilité³⁶ » de l’arrêt d’une autre machine du même type. Il n’y a pas de fonction permettant de savoir si une autre Machine de Turing est ou n’est pas éteinte. Ce problème de logique va se résoudre par des opérations de type binaire (oui/non).

Un homme en train de calculer la valeur d’un nombre réel peut être comparé à une « machine » susceptible de se trouver dans un nombre fini d’états […] La machine est alimentée avec une « bande » (analogue au papier qu’utilise l’homme), divisée en sections (appelées « cases »), dans chacune desquelles peut être inscrit un « symbole³⁷ » […] le seul dont la machine est pour ainsi dire « directement consciente³⁸ ».

Concrètement, la Machine de Turing se compose d’un « ruban » contenant des cases dans lesquelles une « tête de lecture / écriture » se déplace de droite à gauche, et inscrivant des symboles alphabétiques. Avec Turing, on passe de la calculabilité (ce qui peut être calculé) au calcul (comment calculer effectivement quelque chose). Grâce à un « registre », la machine peut mémoriser des « états », dont un « spécial » qui indique son démarrage. La machine peut, sur un temps infini, inscrire sur le ruban un nombre réel tel que pi. Le mode d’écriture de la Machine de Turing est constitué d’un ensemble de « symboles » délimités, qui, agencés dans un certain ordre, permettent à la machine de fonctionner en autonomie. Elle garde trace de ses anciennes interventions afin de continuer sa route implacable selon un mode séquentiel (lecture linéaire et totale de gauche à droite). Afin de gagner de la place sur le ruban, les symboles peuvent aussi pointer vers des « tables abrégées³⁹ », des abréviations d’opérations récurrentes. La variable est un symbole qui renvoie à un ensemble de symboles. Cependant, la variable est plus qu’une abréviation (quelque chose qui redirige toujours vers un même terme). La variable a la possibilité de renvoyer, comme son nom l’indique, à quelque chose qui peut varier. Par exemple, comme le dit Turing, la variable peut pointer vers un « traitement » (« process »), vers une opération de calcul. Elle sert à accomplir une tâche précise. En écrivant ligne par ligne (case par case) des résultats d’opérations, la Machine de Turing s’apparente structurellement à un ordinateur. Comme la machine de Turing peut exécuter n’importe quel calcul, elle va être capable de simuler une autre Machine de Turing. La machine « universelle » peut simuler n’importe quelle machine tout en restant elle-même. Chaque machine universelle peut donc, sous réserve de disponibilité matérielle du ruban, contenir toutes les autres machines⁴⁰. Cette possibilité de pouvoir simultanément calculer plusieurs choses et de les imbriquer sur le mode des « variables⁴¹ » est à la base des langages numériques, ceux qui quittent le support papier :

Un langage de programmation est un langage qui est destiné à l’expression de programmes informatiques, et qui est capable d’exprimer n’importe quel programme informatique. Ceci n’est pas une définition floue. Il y a une manière théorique et précise de déterminer si un langage informatique peut être utilisé pour exprimer n’importe quel programme, c’est de montrer qu’il est équivalent à une machine de Turing universelle⁴².

Un système formel est donc constitué d’axiomes (les points de départ) et de programmes (les thèses démontrables au sein du système), c’est un mélange de règles et d’expressions de cette règle (les expressions « en actes »). Ce que nous apprennent Gödel et Turing, c’est qu’en tant que langage informatique, tout programme est voué à l’incomplétude : il finira par « planter » [ Fig. 2 ]. Fig. 2 S’il n’est pas possible de concevoir un langage complet, il est malgré tout possible de gérer et d’anticiper les bugs (erreurs) par l’ajout d’autres programmes. C’est là que le concept de machine prend son sens : elle est ce qui marche et se complète seule.

Cette façon de faire des programmes se donne ainsi comme impossible horizon de résoudre l’incomplétude par l’automatisation [ Fig. 3 ]. Fig. 3 La « machine universelle » de Turing joue comme modèle de programme informatique, un modèle de papier ramené à l’infini déroulé d’un ruban inscriptible. Séquentielle et linéaire, elle ne peut pas ne pas calculer. La machine est de type « procédural », au sens où elle fait strictement ce qui lui est assigné. Calculer, c’est symboliser, c’est effectuer des opérations sur des entités « discrètes » (au sens mathématiques du terme) pouvant se ranger dans des cases. Se pose alors la question du choix :

Pour certains besoins, nous devons utiliser des machines [à choix] dont le comportement ne dépend que partiellement de la configuration (d’où la notion de comportements possibles) : lorsqu’une telle machine atteint une configuration ambiguë, un opérateur extérieur doit intervenir et faire un choix arbitraire pour que la machine puisse continuer son travail⁴³.

L’utilisation (dans la traduction française) du mot « comportement » traduit la volonté de laisser de côté tout ce qui serait non défini, « ambigu ». L’humain ne conduit pas la machine mais se contente de « faire un choix arbitraire ». Ce choix n’est pas tout à fait un choix, au sens où choisir, au sens fort, consiste à distinguer consciemment entre deux situations différentes. L’arbitraire est le contraire du choix. Si l’humain n’était pas intelligent, il ne serait pas en mesure de faire des choix. Le choix humain, celui de l’intelligence, repose sur des principes situés en dehors du formalisme du calcul, au-delà du computationnel. Le programme pose un double choix à l’être humain : celui de pouvoir choisir un système qui se tromperait le moins possible, et celui de changer de système si ce dernier ne correspond pas à la première exigence. L’humain doit toujours être capable de changer de système si celui-ci devient instable et incohérent. Il n’y a pas de choix dans le calcul, ce qui explique qu’il n’y a pas lieu de parler ou de s’inquiéter d’objets ou de systèmes dits « intelligents ». Ce qui va caractériser l’humain par rapport à la machine dans le « test de Turing », c’est sa faculté à simuler l’autre comme humain. Plus précisément, l’autre m’apparaît comme un être intelligent si je ne suis pas en mesure d’établir une différence entre lui et une machine. La faculté de penser se déplace dans une imitation symbolique de la pensée.

De par ses « calculateurs universels programmables », Alan Turing est ainsi communément reconnu comme ayant conçu la structure de base de l’ordinateur tel qu’il existe encore aujourd’hui. Ce qui est notable dans le texte de Turing, c’est que sa machine annonciatrice des programmes informatiques est avant tout, comme le dit Jean-Yves Girard, une « machine de papier⁴⁴ », une tentative de donner forme à un théorème par le recours à des objets concrets (le ruban, etc.). L’intérêt du texte réside dans cette matérialité conceptuelle, qui ne s’apparente pas au typologies du mythe platonicien ou de la métaphore cartésienne du morceau de cire. De ce point de vue, cet objet paradoxal jeté dans le texte en quelques paragraphes fait écho à ce qu’écrira Vannevar Bush quelques années plus tard.