Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Chapitre 14 Machines de Turing Dans ce chapitre on présente un modèle de calcul

Chapitre 14 Machines de Turing Dans ce chapitre on présente un modèle de calcul introduit dans les années 30 par Turing, les ma- chines de Turing. Ces machines formalisent la notion de calculabilité. La thèse de Church afﬁrme que tout calcul par un algorithme effectif peut-être effectué par une machine de Turing. 14.1. DÉFINITION ET FONCTIONNEMENT Les automates représentent un modèle de calcul utilisant une mémoire ﬁnie correspondant à l’en- semble des états de la machine. Les machines de Turing sont également des machines “ﬁnies” (corres- pondant à des algorithmes effectifs), mais elles utilisent une mémoire plus élaborée. Elles utilisent un (ou des) ruban “inﬁni” de cases mémoires qu’elles lisent et réécrivent. Le fonctionnement d’une machine de Turing peut se représenter de manière informelle par une tête de lecture se trouvant sur un ruban qui à la lecture de la case mémoire correspondante change d’état, modiﬁe la case mémoire et se déplace sur le ruban à droite ou à gauche Exemple. Machine qui lisant un b dans l’état p, passe à l’état q, écrit un a à la place du b et déplace sa tête de lecture à gauche. ... a b b c a ... ∆ p ... a b a c a ... ∆ q 14.1.1. Déﬁnition. Une machine de Turing (à un ruban) est la donnée – d’un alphabet ﬁni Σ auquel l’on ajoute un symbole 2 représentant les cases vides, formant ainsi un alphabet Σ+; – d’un ensemble ﬁni d’états Q auquel l’on ajoute deux états ﬁnaux, un état acceptant ⊤et un état refusant ⊥, formant ainsi un ensemble d’états Q+; – d’une fonction de changement d’état δ : Q × Σ+ →Q+; – d’une fonction d’écriture σ : Q × Σ+ →Σ+; – d’une fonction de déplacement ∆: Q × Σ+ →{G, D} ; – d’un état initial q0 ∈Q. 187 14.1.2. Exemple. Le tableau ci-dessous représente les transitions d’une machine de Turing d’alphabet {(, ), $} et d’états {0, 1, 2}. ( ) 2 $ → 0 0, (, D 1, $, G 2, 2, G 0, $, D 1 0, $, D ⊥ ⊥ 1, $, G 2 ⊥ ⊥ ⊤ 2, $, G Cette machine de Turing permet en fait de reconnaître le langage bien parenthésé L. Voici son fonc- tionnement sur le mot (()) : ... ( ( ) ) ... ... ( ( ) ) ... ∆ 0 ∆ 0 ... ( ( ) ) ... ... ( ( $ ) ... ∆ 0 ∆ 1 ... ( $ $ ) ... ... ( $ $ ) ... ∆ 0 ∆ 0 ... ( $ $ $ ... ... ( $ $ $ ... ∆ 1 ∆ 1 ... ( $ $ $ ... ... $ $ $ $ ... ∆ 1 ∆ 0 ... $ $ $ $ ... ... $ $ $ $ ... ∆ 0 ∆ 0 ... $ $ $ $ ... ... $ $ $ $ ... ∆ 0 ∆ 2 ... $ $ $ $ ... ... $ $ $ $ ... ∆ 2 ∆ 2 ... $ $ $ $ ... ... $ $ $ $ ... ∆ 2 ∆ 2 ... $ $ $ $ ... ∆ ⊤ Son fonctionnement sur le mot ())( : ... ( ) ) ( ... ... ( ) ) ( ... ∆ 0 ∆ 0 ... ( $ ) ( ... ... $ $ ) ( ... ∆ 1 ∆ 0 ... $ $ ) ( ... ... $ $ $ ( ... ∆ 0 ∆ 1 ... $ $ ) ( ... ... $ $ $ ( ... ∆ 1 ∆ 1 ... $ $ ) ( ... ∆ ⊥ 14.2. UTILISATION : DÉCIDABILITÉ ET CALCULABILITÉ Aﬁn de formaliser le fonctionnement d’une machine de Turing, on utilise la notation u ↑v pour représenter la conﬁguration du ruban sur lequel est écrit le mot uv avec sa tête de lecture placée au début du mot v et où toutes las autres cases du ruban sont vides. On note (p, u ↑v) ⊢(q, u′ ↑v′) la transition de l’état p avec la conﬁguration de ruban u ↑v à l’état q avec la conﬁguration de ruban (q, u′ ↑v′). 14.2.1. Mots acceptés, mots refusés. Soient M une machine de Turing d’alphabet Σ et u un mot sur Σ. On dit M accepte (respectivement refuse) u si le fonctionnement de M à partir de la conﬁguration (p0, ↑u) mène en un nombre ﬁni de transitions à l’état acceptant ⊤(respectivement l’état refusant ⊥). Remarque. Une machine de Turing peut ni accepter, ni refuser un mot donné, mais ne pas s’arrêter de fonctionner à partir de la conﬁguration associée à ce mot. Voici un exemple de machine qui accepte les mots formés d’un nombre impair de a mais ne s’arrête pas sur les mots formés d’un nombre pair de a. a 2 → 0 1, a, D 2, a, G 1 0, a, D ⊤ 2 2, a, G 1, a, D 14.2.2. Langages (ou ensembles) décidables et semi-décidables. Soit L un langage sur Σ. On dit que L est décidable s’il existe une machine de Turing d’alphabet Σ qui accepte tous les mots de L et refuse tous les mots qui ne sont pas dans L. On dit que L est semi-décidable s’il existe une machine de Turing qui n’accepte que les mots de L. Exemples. Les langages rationnels sont tous décidables (un automate ﬁni est une machine de Turing particulière). Nous verrons plus loin que les langages algébriques sont également décidables. Le com- plémentaire de tout langage décidable est décidable. La langage non-algébrique {anbncn : n ∈N} est décidable. 14.2.3. Fonctions calculables. Une fonction partielle f : Σ →Σ est calculable s’il existe une machine de Turing d’alphabet Σ qui n’accepte que les mots du domaine de déﬁnition de f et qui à partir de la conﬁguration (p0, ↑w) où w est un mot du domaine de déﬁnition termine son calcul avec le mot f(w) sur son ruban. On étend cette déﬁnition aux fonctions de plusieurs variables en représentant les éléments (u1, .., uk) ∈ Σk par le mot u12u22...2uk ∈Σ+. Exemples. Toutes les fonctions calculées par des machines séquentielles sont calculables. La fonction de concaténation qui à (u1, u2, ..., uk) associe u1u2..uk est calculable. La somme, le produit de nombres représentés dans une base donnée sont calculables. Pour la somme en base unaire, il sufﬁt d’utiliser la concaténation. De manière générale, pour calculer ces fonctions il est plus pratique d’utiliser plusieurs rubans mémoires. On se convaincra ensuite que l’on peut simuler de telles machines avec une machine à un seul ruban. 14.3. GÉNÉRALISATIONS Une généralisation naturelle des machines ci-dessus est l’utilisation de plusieurs rubans. Chaque ruban possède alors une tête de lecture et à chaque pas de calcul la transition dépend de la lecture des caractères sur chaque ruban. 14.3.1. Machines de Turing à plusieurs rubans. Une machine de Turing à k rubans est la donnée – d’un alphabet ﬁni Σ auquel l’on ajoute un symbole 2 représentant les cases vides, formant ainsi un alphabet Σ+; – d’un ensemble ﬁni d’états Q auquel l’on ajoute deux états ﬁnaux, un état acceptant ⊤et un état refusant ⊥, formant ainsi un ensemble d’états Q+; – d’une fonction de changement d’état δ : Q × Σk + →Q+; – d’une fonction d’écriture σ : Q × Σk + →Σk +; – d’une fonction de déplacement ∆: Q × Σk + →{G, S, D}k (S correspondant à l’absence de dépla- cement la tête de lecture) ; – d’un état initial q0 ∈Q. Notons σ1, ..., σk et ∆1, ..., ∆k les fonctions coordonnées de σ et ∆. La transition à partir d’une conﬁguration (p, u1 ↑a1v1, u2 ↑a2v2, ..., uk ↑akvk) consiste donc à : – passer à l’état δ(p, a1, .., ak), – remplacer chaque ai par σi(p, a1, .., ak), – déplacer la tête de lecture du i-ème ruban suivant la valeur de ∆i(p, a1, .., ak). 14.3.2. Exemples. 1. Automates à pile : Les automates à piles déterministes peuvent être représentées par des machines à deux rubans, le second ruban utilisé par la pile. 2. Addition en représentation binaire : on considère une machine de Turing à deux rubans. Cette machine commence par placer ses têtes de lectures à la ﬁn des représentations binaires de deux nombres placés sur ces rubans. Ensuite elle fonctionne comme l’algorithme classique de l’addition posée. Elle lit les chifres sur chaque ruban, les additionnent avec la retenue et écrit le résultat correspondant sur le premier ruban et utilise son état pour conserver la retenue qui vaut 0 ou 1. (Rappelons que ceci peut également s’effectuer par une machine séquentielle). 3. Multiplication en représentation binaire : on utilise une machine à trois rubans. Le premier sert au résultat, les deux autres aux donnés. On simule alors l’algorithme clssique de la multiplication posée, en utilisant l’addition à chaque étape. 4. Passage d’une base à une autre pour la réprésentation d’un nombre : il sufﬁt pour uploads/Industriel/ machine-de-turing-universelle.pdf