Remerciez-le!

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

Machine de turing universelle

Chapitre Machines de Turing Dans ce chapitre on présente un modèle de calcul introduit dans les années par Turing les machines de Turing Ces machines formalisent la notion de calculabilité La thèse de Church af ?rme que tout calcul par un algorithme e ?ectif peut-être e ?ectué par une machine de Turing DÉFINITION ET FONCTIONNEMENT Les automates représentent un modèle de calcul utilisant une mémoire ?nie correspondant à l ? ensemble des états de la machine Les machines de Turing sont également des machines ?? ?nies ? correspondant à des algorithmes e ?ectifs 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 abbca ? p abaca ? q Dé ?nition Une machine de Turing à un ruban est la donnée ?? d ? un alphabet ?ni ? auquel l ? on ajoute un symbole 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 q ?? Q C Exemple Le tableau ci-dessous représente les transitions d ? une machine de Turing d ? alphabet et d ? états ? D G G D D ? ? G ? ? ? G Cette machine de Turing permet en fait de reconna? tre le langage bien parenthésé L Voici son fonctionnement sur le mot ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? CSon fonctionnement sur le mot ? ? ? ? ? ? ? ? ? ? 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