Calculabilité - Décidabilité (LI347) [0.3cm] Cours no10

Calculabilité - Décidabilité (LI347)oCours n 10Stef GraillatUniversité Pierre et Marie Curie (Paris 6)S. Graillat (Univ. Paris 6) LI347 (cours n˚10) 1 / 20Résumé du cours précédentMachine de Turing : une machine de Turing est un modèle decalculateur qui a la même puissance de calcul que les ordinateursactuels et que les autres définitions mathématiques de calculateurs.Une MT consiste en un automate fini, un ruban infini composé decellules et d’une tête de lecture qui est au dessus d’une cellule. Unmouvement de la MT dépend de l’état de l’automate et du symbolecontenu dans la cellule sous la tête de lecture. Lors d’un mouvement,la MT change d’état, écrit dans la cellule sous la tête de lecture etdéplace la tête de lecture vers la gauche ou vers la droiteAcceptation par une MT : une MT est initialisée en mettant le mot enentrée sur le ruban et toutes les autres cellules du ruban contiennent lesymbole blanc. Le mot en entrée est accepté sur la MT rentre dans unétat acceptantS. Graillat (Univ. Paris 6) LI347 (cours n˚10) 2 / 20Résumé du cours précédent (suite)Langages récursivement énumerables : les langages acceptés par uneMT sont appelé les langages récursivement énumerablesConfiguration d’une MT : on peut décrire l’état d’une MT par unechaine de symbole de longueur finie incluant le contenu de toutes lescellules du symbole non blanc le plus à gauche à celui le plus à droite.L’état et la position de la tête de lecture sont donnés en placant l’étatdans ...