Une machine de Turing

Présentation de la machine
L'algorithme
Le matériel

Présentation de la machine

Pour mettre en action la machine, il faut quatre pièces de monnaie, ou, à défaut, quatre cailloux ( calculi en latin) et un trombonne qui servira de pointeur.

Cette machine permet de multiplier par deux une quantité initiale (ici deux, mais vous pouvez essayer avec trois, quatre, mille, ...). L'algorithme permettant de résoudre ce problème est décrit ci-dessous. Il faut suivre scrupuleusement les instructions, sans chercher à les interpréter. Vous serez récompensé par l'obtention certaine du résultat.

La bande (A) est la situation de départ [les données] et la bande (C) la situation d'arrivée [l'état de sortie]. La bande du milieu (B) vous permet d'effectuer toutes les opérations intermédiaires [les traitements]. (Patience, il en a beaucoup pour ce simple calcul).

Commencer par reproduire la situation initiale (A). Appliquer ensuite l'algorithme de la manière suivante : en commençant par l'état 1, exécuter l'instruction de la première ou seconde colonne selon qu'il y a une pièce ou non, exécuter alors l'instruction de l'état indiqué, etc. Vous devez finir par la case 'Stop'.

L'algorithme

Etat	Il n'y a pas de pièce en face du trombonne	Il y a une pièce en face du trombonne
1	Stop.	Retirer la pièce - déplacer le trombonne d'une case vers la gauche - passer à l'état 2.
2	Mettez une pièce en face du trombonne - déplacer le trombonne d'une case vers la gauche - passer à l'état 3.	Déplacer le trombonne d'une case vers la gauche - revenez à l'état 2.
3	Mettez une pièce en face du trombonne - déplacer le trombonne d'une case vers la droite - passer à l'état 4.	Déplacer le trombonne d'une case vers la gauche - passer à l'état 3.
4	Déplacer le trombonne d'une case vers la droite - passer à l'état 5.	Déplacer le trombonne d'une case vers la droite - passer à l'état 4.
5	Stop.	Retirer la pièce - déplacer le trombonne d'une case vers la gauche - passer à l'état 2.

Le matériel