Machines de Turing

En quoi consiste au juste un algorithme et quelles sont les opérations qui peuvent, en principe, être effectuées de manière algorithmique ? C’est pour répondre à cette question qu’Alan Turing proposa, en 1935-36, une « machine » suffisamment simple pour que des théorèmes sur le type de fonctions qu’elle peut calculer puissent être prouvés, et assez puissante pour simuler n’importe quel ordinateur digital. Une machine de Turing comporte une bande infinie dans les deux sens, constituée de cellules de mémoire et un alphabet fini de symboles qui peuvent être lus et écrits par une tête sur les cellules. Les cellules contenant un symbole sont toujours en nombre fini. Il n’y a qu’une seule cellule active : c’est celle où se trouve la tête. La machine peut se trouver dans différents états qui sont en nombre fini. Chaque état est caractérisé par un nombre. Pour exécuter une instruction, une machine de Turing lit le symbole se trouvant sous la tête, modifie (ou non) le contenu de la cellule, laisse en place ou déplace la tête d’une cellule vers la gauche ou vers la droite et adopte (ou non) un nouvel état.


Quelle est la machine de Turing universelle la plus simple ?

Lettre précédente
Lettre suivante

Voir en ligne : Lettre au format pdf