Enseignement scientifique ch13 L'intelligence artificielle
Essayons de faire quelque chose de paradoxal : montrer concrètement comment marche une machine abstraite !
Cet article est issu du site https://interstices.info. Je l'ai adapté à l'exercice n°13 p.320 du manuel Nathan.
Des précisons se trouvent sur la page https://interstices.info/comment-fonctionne-une-machine-de-turing/
Car c'est bien une machine abstraite qu'Alan Turing a inventée pour expliquer la notion de « procédure mécanique » : on parle d'algorithme. Cette machine est la plus élémentaire possible destinée à mettre en œuvre ces mécanismes de calcul, numériques ou symboliques, comme le font notamment les ordinateurs. Ne perdons pas de vue que lorsqu'Alan Turing décrit sa machine dans un article en 1936, les ordinateurs n'existent pas encore !
Essayons de la découvrir... en l'utilisant
La machine imaginée par Turing comporte un ruban divisé en cases, dans lesquelles elle peut écrire des symboles. La machine ne peut lire qu'une seule case à la fois, de même elle écrit dans une seule case et décale le ruban d'une seule case vers la gauche ou vers la droite. Les symboles sont en nombre fini. Pour que sa machine fonctionne comme une machine à calculer en binaire, Turing envisage le cas particulier où les symboles utilisés sont 0 et 1. C'est une telle machine que nous vous proposons de tester sur l'animation interactive suivante. Vous pourrez y suivre l'exécution de six « programmes ».
L'entrée du programme est une liste de symboles binaires, écrits sur le ruban, matérialisé par les cases successives (en bas de l'animation). Une fois le calcul effectué, c'est sur ce ruban que sera écrit le résultat du calcul, la sortie du programme. À chaque instant, le ruban mémorise l'état du calcul. Voilà la forme la plus simple de mémoire mécanique !
À chaque programme correspond une description sous forme de table (à droite de l'animation). Chacune des lignes de cette table est associée à un état et spécifie les actions à effectuer quand la machine est dans cet état, en fonction du symbole présent sous la tête de lecture. Ces actions peuvent être l’écriture d’un symbole (ici un 0 ou un 1) et le déplacement du ruban d’une case à droite ou à gauche. La ligne spécifie également le nouvel état après l’exécution des actions.
La machine s’arrête quand un état marqué comme final est atteint.
Turing a également prévu que les programmes, tels qu'ils sont décrits par la table, puissent eux aussi être codés en binaire et inscrits sur un deuxième ruban. Chaque code correspond alors à une instruction possible. Le calcul se déroule automatiquement en passant d'une instruction à une autre. Comme il est possible d'inscrire sur ce deuxième ruban toutes sortes de programmes et de les exécuter, ce mécanisme va pouvoir faire (avec beaucoup de patience !) tout ce qu'un ordinateur peut faire. On parle de machine de Turing universelle.
Six « programmes » au choix
À vous ! Choisissez d'abord un « programme » parmi les six que nous vous proposons ici. Vous trouverez sur la page ci-dessous une description détaillée de chacun d'eux, mais les codes d'état sont appelés e0, e1, e2... et non q0, q1... comme dans l'exercice du manuel Nathan.
https://interstices.info/comment-fonctionne-une-machine-de-turing/