Université d'Orléans Année M1 Info Calculabilité Complexité TD n

Alan Turing

Description

Niveau: Supérieur, Master, Bac+4
Université d'Orléans Année 2011-2012 M1 Info — Calculabilité & Complexité TD n? 2 Machines de Turing [Alan Turing, 1936] Quelques petites machines pour commencer. . . Exercice 1 : Que fait cette machine ? On considère une machine de Turing à une seule bande bornée à gauche et infinie à droite. L'alphabet de la bande contient d (début de bande), $ (fin de bande), _ (séparateur) et 1 (codage de données). L'état q0 est l'état initial et l'état qf est l'état final. La fonction de transition ? est définie comme suit : ?(q0, d) = (q1, d,?) ?(q1, 1) = (q1, 1,?) ?(q1,_) = (q1,_,?) ?(q1, $) = (q2, $,?) ?(q2, 1) = (q3, $,?) ?(q3, 1) = (q3, 1,?) ?(q3,_) = (q4,_,?) ?(q4,_) = (q4,_,?) ?(q4, 1) = (q1,_,?) ?(q2,_) = (q5,_,?) ?(q5,_) = (q5,_,?) ?(q5, 1) = (qf ,_,?) 1.

• exécution de la machine sur la configuration initiale


• codage en unaire


• langage l2n des mots unaires


• bande bi-infinie


• construire


• complexité td


• langage l2n

Sujets

• Turing (homonymie)
• Construction

Informations

• Publié par: larec
• Nombre de lectures: 64
• Langue: Français

Extrait

UniversitÉ d’OrlÉans M1 Info— CalculabilitÉ & ComplexitÉ

Machines de Turing [Alan Turing, 1936]

Quelques petites machines pour commencer.. .

Exercice 1: Quefait cette machine ?

AnnÉe 2011-2012 ◦ TD n2

On considÈre une machine de Turing À une seule bande bornÉe À gauche et infinie À droite. L’alphabet de la bande contientd(dÉbut de bande),$(fin de bande), # (sÉparateur) et1 (codage de donnÉes).L’Étatq 0 est l’État initial et l’Étatq f est l’État final.La fonction de transitionδest dÉfinie comme suit :

δ(q 0 , d) = (q 1 , d,→) δ(q 1 ,#) = (q 1 ,#,→) δ(q 2 ,1) = (q 3 ,$,←) δ(q 3 ,#) = (q 4 ,#,←) δ(q 4 ,1) = (q 1 ,#,→) δ(q 5 ,#) = (q 5 ,#,←)

δ(q 1 ,1) = (q 1 ,1,→) δ(q 1 ,$) = (q 2 ,$,←) δ(q 3 ,1) = (q 3 ,1,←) δ(q 4 ,#) = (q 4 ,#,←) δ(q 2 ,#) = (q 5 ,#,←) δ(q 5 ,1) = (q f ,#,→)

1. Simulerl’exÉcution de la machine sur la configuration initiale suivante :

5q 0 d 1 1 1 1 # 1 1 $ .. .

2. Quelleest la fonction calculÉe par cette machine ? 3. Existe-t-ildes configurations d’entrÉe non gÉrÉes par la table de transition ? Si oui, proposez des solutions pour gÉrÉr ces cas (en imposant une condition sur les entrÉes, puis en complÉtant la table de transition).

Exercice 2: Lelangage des nombres pairs (encore).

1. Codageen binaire. i) Construireune machine de TuringM 1 qui s’arrteuniquementlorsque l’entier codÉ en binaire sur la bande est pair. ◦ ii) Quelleest la diffÉrence avec la machineM P de l’exercice 3 du1TD n?

1

2. Codageen unaire. i) Construireune machine de TuringM 2 qui s’arrte uniquement lorsque l’entier codÉ en unaire sur la bande est pair. 0 ii) Modifierla machineM 2 en une machineMpour qu’elle s’arrte toujours. 2 3. Calculde la fonctionn7→2n. Ecrire une machineM 3 qui prend un entiernen unaire et rend l’entier2n. 0 Quelle est la diffÉrence avec la machineM? 2

Exercice 3: Unemachine simple.

Construire une machine de Turing qui efface son entrÉe et revient en dÉbut de bande.

Exercice 4: OpÉrationsarithmÉtique ÉlÉmentaires sur machines de Turing. Construire des machines de Turing permettant de : i) additionnerdeux nombres unaires. ii) incrÉmenterde un en binaire. iii) multiplierdeux nombres unaires. iv) reconnatrele langageL 2 des mots unaires dont la longueur est une puissance de deux n n 2 i.e.le langageL 2 ={1|n∈N}. n

Un peu plus compliquÉ maintenant.. .

Exercice 5: Variantesde machines de Turing Montrer que les variantes suivantes de machines de Turing sont toutes Équivalentes entre ellesi.e.elles calculent les mmes objets : i) lesmachines avec une seule bande infinie À droite et bornÉe À gauche. ii) lesmachines avec une seule bande bi-infinie. iii) lesmachines avec deux bandes bornÉes À gauche. iv) lesmachines avecnbandes bornÉes À gauche (n≥2).

2

Exercice 6: LeCastor AffairÉ, ou Busy Beaver [Tibor Rad, 1962] . On considÈre des machines de Turing À une bande bi-infinie et ÀnÉtats, plus un État d’arrt notÉH. L’alphabet estΣ ={0,1}, oÙ0fait Également office de symbole blanc.La tte de lecture ne peut pas rester sur place. On appelleCastor Affairela fonction qui Ànassocie le nombre maximal de1qu’il est possible d’obtenir par une machine de Turing ÀnÉtats dont la bande ne contient initialement que des0etqui s’arrte(et telle que dÉfinie ci-dessus).On noteBB(n) cette fonction.On peut Également dÉfinirS(n)le nombre maximal possible de transitions. 1. Combienexiste-t-il de machines À2symboles etnÉtats (plus l’État d’arrtH) ? 2. OnaBB(2)= 4et queS(2)= 6 [Rad, 1962] . Combien existe-t-il de machines À2symboles et À2États ? Construire une (ou des) machines qui atteignent ces scores. 3. Onsait queBB(3)= 6et queS(3)= 21 [Lin et Rad, 1965] . Proposer des machines candidates pour atteindre ces valeurs (ou pour s’en rapprocher le plus possible). Actuellement, nous connaisons les valeurs exactes deBB(n)etS(n)uniquement pour quelques petites valeurs den: mmepourn= 5, nous ne connaissons pas le nombre maximal de1qu’une machine À5On peut constaterÉtats peut Écrire avant de s’arrter. gráce aux valeurs donnÉes par la Table 1 que ces fonctions croissent trÈs vite, plus vite que n’importe quelle fonction calculable par une machine de Turing. ◦ Nous verrons dans la feuille deTD n3que les fonctionsBB(n)etS(n)ne sont en fait pas calculables par machine de Turing. n BB(n)S(n) 2 46 3 621 4 13107 5≥4098≥47 176 870 18276 36534 6≥3,5×10≥7,4×10 Table 1:Les premiÈres valeurs deBBetS.

3