Machine de Turing - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Introduction

Une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur et 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 (L´informatique - contraction d´information et automatique - est le domaine...) théorique, en particulier pour résoudre les problèmes de complexité (La complexité est une notion utilisée en philosophie, épistémologie (par...) algorithmique (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées...) et de calculabilité (La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est une branche...), on lui adjoint pour cela un oracle.

La thèse (Une thèse (du nom grec thesis, se traduisant par « action de poser ») est...) Church-Turing postule que tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou...) problème de calcul fondé sur une procédure algorithmique peut être résolu par une machine de Turing (Une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques...). Cette thèse n'est pas un énoncé mathématique, puisqu'elle ne suppose pas une définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la...) 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).

À l'origine, le concept de machine de Turing, inventé avant l'ordinateur (Un ordinateur est une machine dotée d'une unité de traitement lui permettant...), était censé représenter une personne virtuelle exécutant une procédure bien définie, en changeant le contenu des cases d'un tableau (Tableau peut avoir plusieurs sens suivant le contexte employé :) infini (Le mot « infini » (-e, -s ; du latin finitus,...), en choisissant ce contenu parmi un ensemble fini (En mathématiques, un ensemble E est dit fini si et seulement s'il existe un entier n et une...) de symboles. D'autre part, la personne doit mémoriser un état particulier parmi un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection...) 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 case que vous regardez est '0', alors remplacer ce symbole par un '1', passer (Le genre Passer a été créé par le zoologiste français Mathurin Jacques...) dans l'état 17, et regarder une case adjacente (droite ou gauche) ».

Définition

La mise en œuvre concrète (La concrète est une pâte plus ou moins dure obtenue après extraction d’une...) d'une machine de Turing est réalisée avec les éléments suivants :

  1. Un « ruban » divisé en cases consécutives. Chaque case contient un symbole parmi un alphabet fini. L'alphabet contient un symbole spécial « blanc » ('0' dans les exemples qui suivent), et un ou plusieurs autres symboles. Le ruban est supposé être de longueur (La longueur d’un objet est la distance entre ses deux extrémités les plus...) infinie vers la gauche ou vers la droite, en d'autres termes la machine doit toujours avoir assez de longueur de ruban pour son exécution. On considère que les cases non encore écrites du ruban contiennent le symbole « blanc ».
  2. Une « tête de lecture/écriture » qui peut lire et écrire les symboles sur le ruban, et se déplacer vers la gauche ou vers la droite du ruban.
  3. Un « registre d'état » qui mémorise l'état courant de la machine de Turing. Le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre...) d'états possibles est toujours fini, et il existe un état spécial appelé « état de départ » qui est l'état initial de la machine avant son exécution.
  4. Une « table d'actions » qui indique à la machine quel symbole écrire, comment déplacer la tête de lecture ('G' pour une case vers la gauche, 'D' pour une case vers la droite), et quel est le nouvel état, en fonction du symbole lu sur le ruban et de l'état courant de la machine. Si aucune action n'existe pour une combinaison (Une combinaison peut être :) donnée (Dans les technologies de l'information, une donnée est une description élémentaire,...) d'un symbole lu et d'un état courant, la machine s'arrête.

Exemple

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 :

Ancien état Symbole lu Symbole écrit Mouvement Nouvel état
e1 0 (Arrêt)
1 0 Droite e2
e2 1 1 Droite e2
0 0 Droite e3
e3 1 1 Droite e3
0 1 Gauche e4
e4 1 1 Gauche e4
0 0 Gauche e5
e5 1 1 Gauche e5
0 1 Droite e1

L’exécution de cette machine pour une série de deux '1' serait (la position de la tête de lecture/écriture sur le ruban est inscrite en caractères gras et rouges) :

Étape État Ruban
1 e1 11
2 e2 01
3 e2 010
4 e3 0100
Étape État Ruban
5 e4 0101
6 e5 0101
7 e5 0101
8 e1 1101
Étape État Ruban
9 e2 1001
10 e3 1001
11 e3 10010
12 e4 10011
Étape État Ruban
13 e4 10011
14 e5 10011
15 e1 11011
  (Arrêt)

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 elle utilise l’état e2 pour se déplacer vers la droite, en sautant les 1 (un seul dans cet exemple) jusqu'à rencontrer un 0 (ou un blanc), et passer dans l'état e3.
  • 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.
  • L'état e4 permet de revenir vers la gauche jusqu’à trouver un 0, et passer dans l’état e5.
  • L'état 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.

Page générée en 0.064 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique