Page d'accueil
encyclopedie-enligne.com en page d'accueil| Page d'accueil |
encyclopedie-enligne.com en page d'accueil |
|||||
| Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées | ||||||
Une machine de Turing est un modèle abstrait du fonctionnement d'un ordinateur et de sa mémoire, créé par Alan Turing en vue de
donner une définition précise au concept d'algorithme ou « procédure
mécanique ». Ce modèle est toujours largement utilisé en informatique
théorique, en particulier pour résoudre les problèmes de complexité algorithmique et de calculabilité.
La thèse Church-Turing postule que tout problème de calcul basé sur une procédure algorithmique peut être résolu par une machine de Turing. Cette thèse n'est pas un énoncé mathématique, puisqu'elle ne suppose pas une définition précise de procédure algorithmique. En revanche, il est possible de définir une notion de « système acceptable de programmation » et de démontrer que le pouvoir de tels systèmes est équivalent à celui des machines de Turing (Turing-complet).
A l'origine, le concept de machine de Turing était censé représenter une personne virtuelle exécutant une procédure bien définie, en changeant le contenu d'une pile de feuilles de papier en nombre infini, en choisissant ce contenu parmi un ensemble fini de symboles. D'autre part la personne doit mémoriser un état particulier parmi un ensemble fini d'états. La procédure est formulée en termes d'étapes très simples du type : « si vous êtes dans l'état 42 et que le symbole contenu sur la feuille que vous regardez est '0', alors remplacer ce symbole par un '1', passer dans l'état 17, et regarder la feuille suivante dans la pile ».
Attention à ne pas confondre les machines de Turing avec le Test de Turing, destiné à évaluer l'intelligence artificielle d'une machine.
Une machine de Turing capable de simuler toute autre machine de Turing est appelée « machine de Turing universelle ».
| Sommaire |
La mise en œuvre concrète d'une machine de Turing est réalisée avec les élements suivants :
La machine de Turing qui suit possède un alphabet {'0', '1'}, '0' étant le « blanc ». On suppose que le ruban
contient une série de '1', et que la tête de lecture/écriture se trouve initialement au-dessus du '1' le plus à gauche. Cette
machine a pour effet de doubler le nombre de '1', en intercalant un '0' entre les deux séries. Par exemple, « 111 »
devient « 1110111 ».
L'ensemble d'états possibles de la machine est {e1, e2, e3, e4, e5} et l'état initial est e1.
La table d'actions est la suivante :
Anc. Sym. Sym. Nouv. état lu écr. Mouv. état - - - - - - - - - - - - e1 1 -> 0 D e2 e2 1 -> 1 D e2 e2 0 -> 0 D e3 e3 0 -> 1 G e4 e3 1 -> 1 D e3 e4 1 -> 1 G e4 e4 0 -> 0 G e5 e5 1 -> 1 G e5 e5 0 -> 1 D e1
L'exécution de cette machine pourrait être par exemple :
(la case en caractères gras indique la position de la tête de lecture/écriture)
Étape État Ruban Étape État Ruban - - - - - - - - - - - - - - - - - 1 e1 11 9 e2 1001 2 e2 01 10 e3 1001 3 e2 010 11 e3 10010 4 e3 0100 12 e4 10011 5 e4 0101 13 e4 10011 6 e5 0101 14 e5 10011 7 e5 0101 15 e1 11011 8 e1 1101 -- STOP --
Le comportement de cette machine peut être décrit comme une boucle : Elle démarre son exécution dans l'état e1, remplace le
premier 1 par un 0, puis utilise l'état e2 pour se déplacer vers la droite, en sautant les 1, et le premier 0 qu'elle rencontre.
L'état e3 est alors utilisé pour sauter la séquence suivante de 1 (initialement aucun) et remplacer le premier 0 rencontré par un
1. e4 permet de revenir vers la gauche jusqu'à trouver un 0, et passer dans l'état e5. e5 permet ensuite à nouveau de se déplacer
vers la gauche jusqu'à trouver un 0, écrit au départ par l'état e1.
La machine remplace alors ce 0 par un 1, se déplace d'une case vers la droite et passe à nouveau dans l'état e1 pour une nouvelle
itération de la boucle.
Ce processus se répète jusqu'à ce que e1 tombe sur un 0 (c'est le 0 du milieu entre les deux séquences de 1). À ce moment la
machine s'arrête.
Toute machine de Turing calcule le résultat d'une fonction partielle sur des chaînes de caractères composées des caractères de son alphabet. En ce
sens, une machine de Turing se comporte comme un ordinateur avec un programme déterminé.
Mais, comme Alan Turing le décrivit, on peut encoder la table d'actions d'une machine de Turing sous la forme d'une chaîne de
caractères. On peut donc tenter de construire une machine de Turing qui suppose l'existence sur son ruban d'une chaîne de
caractères encodant une table d'actions, suivie d'une chaîne de caractères constituant les données effectives du ruban, et
calcule le contenu du ruban que la machine de Turing encodée aurait calculé.
Comme Alan Turing le montra, il est possible de créer une telle machine de Turing et puisqu'elle peut simuler le comportement de
n'importe quelle autre machine de Turing, on l'appelle « machine de Turing universelle ».
Grâce à cet encodage des tables d'actions sous forme de chaînes de caractères, il devient en principe possible que les
machines de Turing répondent à des questions à propos du comportement d'autres machines de Turing. Cependant, la plupart de ces
questions sont indécidables, c'est-à-dire que la fonction en question ne peut pas être calculée par une machine de Turing.
Par exemple, la question de savoir si une machine de Turing atteint à un moment donné un état d'arrêt ou ne l'atteint jamais pour
une entrée particulière, ou pour toutes les entrées possibles, connu sous le nom de problème de l'arrêt, fut démontré comme étant indécidable
par Turing. Le théorème de Rice montre que toute question
non triviale sur le comportement ou la sortie d'une machine de Turing est indécidable.
Si on élargit la définition pour y inclure les machines de Turing qui simulent des modèles de calcul Turing-complets, et non plus seulement les machines de Turing qui simulent
directement d'autres machines de Turing, une machine de Turing universelle peut être relativement simple, et utiliser seulement
quelques états et symboles. Par exemple, il existe une machine de Turing universelle de taille 2×18 (c'est-à-dire 2 états, et 18
symboles).
La liste complète des machine de Turing universelles est : 2×18, 3×10, 4×6, 5×5, 7×4, 10×3, 22×2. Ces dernières simulent un
modèle appelé tag
system.
Une machine de Turing universelle est Turing-complète. Elle peut calculer toute fonction récursive, analyser tout langage récursif, et accepter tout langage partiellement décidable. Selon le théorème de Church-Turing, les problèmes solvables par une machine de Turing universelle sont exactement les problèmes solvables par un algorithme ou par une méthode concrète de calcul, en supposant une définition raisonnable de ces termes.
Il est assez aisé de simuler une machine de Turing sur un ordinateur moderne (hormis lorque la limitation de mémoire peut poser un problème).
Il est aussi possible de construire une machine de Turing purement mécanique. Le mathématicien Karl Scherer en construisit une en 1986 en utilisant des jeux de construction en métal et en plastique, et du bois. Sa machine, haute de un mètre et demi utilise des ficelles pour lire, déplacer et écrire les données (représentées à l'aide de roulements à billes).
La machine est actuellement exposée dans le hall du département d'informatique de l'Université d'Heidelberg en Allemagne.
De même, en utilisant environ 200 miroirs, il est possible de créer une machine de Turing universelle optique en utilisant la méthode dite du fer à cheval conçue par Stephen Smale.
