La machine de Turing

Objectif

  • Découvrir ce qu'est une machine de Turing.

Mise en situation

L'ordinateur possède une base théorique qui sous-tend la majorité des développements scientifiques et technologiques en informatique : la machine de Turing.

Ce modèle a été imaginé par Alan Turing en 1936 afin de donner une définition rigoureuse de la manipulation automatique de l'information.

L'idée générale de ce modèle est qu'un acteur modifie ce qui est inscrit sur un ruban découpé en plusieurs cases, en appliquant des règles mécaniques, sans réfléchir. Par exemple une règle pourrait être : « si il y a un A dans la case que tu lis, alors écrit à la place Z et va à la case suivante ». Une telle machine pourrait servir à remplacer les A par des Z dans un texte.

FondamentalLa machine de Turing

La machine de Turing est un modèle abstrait du fonctionnement d'une machine (mécanique) à calculer (type ordinateur). Ce modèle pensé par Alan Turing permet d'apporter une définition précise au concept d'algorithme (appelé alors « procédure mécanique »).

Description d'une machine de Turing

Une machine de Turing est un objet abstrait composé de quatre éléments :

  • Un ruban infini divisé en cases contenant chacune un symbole issu d'une liste finie (un alphabet).

  • Une tête de lecture/écriture pouvant lire et écrire sur le ruban, et pouvant se déplacer vers la gauche ou la droite du ruban.

  • Un registre d'état qui retient l'état actuel de la machine. Pour un être humain faisant du calcul mental, on pourrait comparer cela au fait de retenir l'état d'avancement du calcul (par exemple les retenues).

  • Une table d'actions qui lie (en fonction de l'état courant) un symbole lu à une action à effectuer par la tête de lecture/écriture (déplacement et/ou écriture).

États

Une machine de Turing possède un registre permettant de retenir son état. Il existe trois types d'états :

  • L'état initial : état lors du lancement de l'algorithme

  • Les états intermédiaires : états transitoires permettant de faire avancer le calcul.

  • Les états acceptants : états correspondant à une fin possible de l'algorithme

Démonstration

Pour mieux comprendre le concept de machine de Turing, voici une application Web qui simule très bien son fonctionnement.

Choisir le programme "Ajouter 1", entrer la valeur "1" comme valeur de départ et cliquer sur "Commencer".

Le ruban contiendra "10" en fin de programme (soit le nombre 2 en binaire). Le tableau en haut à droite fait office de table d'actions en ayant un curseur pointant sur l'état courant. Ce curseur est le registre d'état. L'alphabet est : 1, 0, VIDE.

Simulation d'une machine de TuringInformations[1]

Attention

Une telle machine peut sembler un peu simpliste mais les algorithmes les plus complexes ne sont qu'une succession d'un très grand nombre d'opérations de base.

FondamentalMachine de Turing universelle

Alan Turing nomme Machine de Turing universelle une machine de Turing capable de « simuler » n'importe quel autre machine de Turing. Dans la mesure où il est possible de construire une machine de Turing pour n'importe quel algorithme, machine de Turing universelle peut calculer tout ce qui est considéré comme calculable.

Pour ce faire, une machine de Turing universelle doit recevoir le « codage » de la machine de Turing simulée ainsi que ses données.

Un ordinateur peut être vu comme une machine de Turing universelle.

ComplémentAller plus loin que le calcul arithmétique

Ainsi, ce modèle abstrait proposé par Turing changea totalement la notion même de calcul. Avant lui, le mot calcul ne signifiait que calcul arithmétique (additionner, soustraire, etc.). Après Turing, la notion de calcul est redéfinie et englobe des opérations bien plus abstraites, englobant tous les algorithmes. Elle ouvre la voie à des domaines nombreux comme l'intelligence artificielle qui fut le sujet d'un de ses articles.

À retenir

  • Une machine de Turing est un modèle abstrait à l'origine de la notion d'algorithme.

  • Tout algorithme peut être représenté par une machine de Turing.

  • L'ordinateur s'apparente à une machine de Turing universelle pouvant exécuter tous les algorithmes.