Machines de Turing

Présentation

Ces machines (théoriques) permettent de résoudre tous les problèmes qui peuvent être décrits sous forme algorithmique.

Leur mémoire peut être représentée par des cases et des pions (cailloux, pièces de monnaie...) et un pointeur (bâtonnet, trombone...).

Machine de Turing

Il suffit alors de suivre scrupuleusement les instructions, sans chercher à penser, pour que le résultat soit garanti. Ci-dessous, l'algorithme à utiliser pour multiplier par 2.

Démonstration d'une machine en JAVA

Cliquez sur une opérande pour lancer la machine :

Algorithme de la multiplication par 2

états	Il n'y a pas de pion en face du pointeur	Il y a un pion en face du pointeur
1	FIN	Enlevez le pion - Déplacez le pointeur d'une case vers la gauche - Passez à l'état 2
2	Mettez un pion - Déplacez le pointeur d'une case vers la gauche - Passez à l'état 3	Déplacez le pointeur d'une case vers la gauche - Restez à l'état 2
3	Mettez un pion - Déplacez le pointeur d'une case vers la droite - Passez à l'état 4	Déplacez le pointeur d'une case vers la gauche - Restez à l'état 3
4	Déplacez le pointeur d'une case vers la droite - Passez à l'état 1	Déplacez le pointeur d'une case vers la droite - Restez à l'état 4

http://www.histoire-informatique.org/technologie/machines_turing.html
Dernière mise à jour le 07/12/2007. ©1996-2007 ~ François GUILLIER