$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th
Dictionnaire de mathématiques > Applications > Algorithmique >
Dictionnaire de mathématiques > Fondements > Logique >

Machine de Turing

  La machine de Turing est le précurseur de tous les ordinateurs actuels. Mise au point par le mathématicien anglais Alan Turing, elle est une machine universelle qui formalise la notion d'algorithme. Elle est constituée d'un ruban, infini dans les 2 sens, d'une tête de lecture, qui lit un caractère imprimé sur le ruban et se déplace dans les deux sens, et d'un programme. Les instructions du programme sont de la forme suivante : Si on est dans l'état q et si on lit le caractère a sur le ruban, alors on passe dans l'état q', on écrit a' sur le ruban, et on déplace la tête de lecture à droite ou à gauche sur le ruban.

Exemple : la machine de Turing qui ajoute un à un nombre.
  Nous supposerons que nous écrivons un nombre sur la machine de Turing en unaire, c'est-à-dire que chaque nombre est représenté par sa valeur en batons (ex : 7=IIIIIII), et qu'après le dernier bâton, on écrit a sur le ruban. On part avec la tête de lecture sur le premier bâton, dans l'état initial q0. Le programme possède les instructions suivantes :
  • Si on lit un bâton et qu'on est dans l'état initial, on déplace la tête de lecture vers la droite.
  • Si on lit un a, et qu'on est dans l'état initial, on écrit un bâton sur le ruban, on passe dans l'état q1, et on se déplace vers la droite.
  • Si on est dans l'état q1, quel que soit le caractère sur le ruban, on écrit a, et on passe dans l'état final : le programme est terminé.
Et voici le résultat :
Consulter aussi...
Recherche alphabétique
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
Recherche thématique
  • Algèbre
  • Analyse
  • Applications
  • Arithmétique
  • Probabilité et statistiques
  • Géométrie
  • Fondements
  • Histoire
  • Mathématiques discrètes
  • Mathématiques interactives