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

Calculabilité - Décidabilité (LI347)oCours n 11Stef GraillatUniversité Pierre et Marie Curie (Paris 6)S. Graillat (Univ. Paris 6) LI347 (cours n˚11) 1 / 35Résumé du cours précédentVariante de machines de Turing : MT multi-pistes, MT multi-rubans,MT non déterministe, MT à ruban semi-infini, machines multi-piles,machines à compteurs (à 2 compteurs). Toutes ses machines ont lamême « possibilité » de calcul que la MTLangages recursifs et récursivement énumérables : les langagesacceptés par une machine de Turing (MT) sont dits récursivementénumérables (RE). Un langage RE qui est reconnu par une MT quis’arrête toujours est dit récursif.Le langage L : c’est le langage des mots sur {0,1} tels que,dinterprété comme une MT, ne sont pas dans le langage reconnu parcette MT. C’est un exemple de langage non RE.S. Graillat (Univ. Paris 6) LI347 (cours n˚11) 2 / 35Langages récursifs et classes de langagesDéfinition 1Un langage L est récursif si L = L(M) pour une MT M telle quesi w ∈ L alors M accepte w (et s’arrête)si w ∈/ L alors M n’accepte pas w mais s’arrêteUne telle machine de Turing correspond à notre notion informelled’algorithmeClasses de langages :récursif = décidable : la MT reconnaisant le langage s’arrete toujoursrécursivement énumerable mais pas récursive : la MT reconnaisant lelangage s’arrête si elle accepte un motExemple : Lunon récursivement énumerable : il n’existe pas de MT reconnaissant celangageExemple : LdS. Graillat (Univ. Paris 6) ...