MT

1 Construction de machines de Turing à 1 bande

Exercice 1

(a)

On construit

(b)

à finir

Exercice 2

Exercice 3

(a)

1. Remplacer le premier “a” par X
2. Aller à droite jusqu’à obtenir un “b” et le templacer par Y
3. Repartir en arrière pour trouver le premier “a” non coché

Exercice 4

(a)

Exercice 5

Exercice 6

Exercice 7

(a)

(b)

Exercice 8

2 Construction de machines de Turing multi-bandes

Exercice 9

Exercice 10

Exercice 11

Exercice 12

Preuve
Comme sont RE, il existe deux machines de Turing et telles que et . On construit une machine de Turing sur une entrée :
simule une étape de sur sur la bande , puis une étape de sur sur la bande , et ainsi de suite. accepte si ou accepte.

Montrons que alors

MQ si accepte , alors . Si accepte, c’est que ou accepte. Donc ou .

Conclusion:

Exercice 13

Langage fini => automate fini => complet et déterministe => MT qui s’arrète sur toutes ses entrées, cf exo 1

Soit tel que . Mq pour toute MT qui accepte il existe une infinité de mots d’entrée qur lesquels la mcahine ne s’arrête pas.

Soit une MT acceptant et l’ensemble des mots sur lequels ne s’arrête pas.

Par l’absurde, supposons fini. Alors il existe une machine de Turing qui s’arrête sur toutes ses entéres et qui accepte exactement les mots de (Les langages finis sont récursifs.)

commence par exécuter sur son mot d’entrée .

• Si accepte cad M’ rejette le mot.
• Sinon exécute sur et répond comme .

Mq s’arrête sur toutes ses entrées.
Soit un mot d’entrée. s’arrête sur . Si accepte, M’ s’arrête et rejette. Si rejette, alors et s’arrête sur . Ainsi aussi

Mq accepte
Soit un mot d’entrée.

• Si , alors s’arrête sur et accepte donc . Donc

rejette et donc exéxute sur et va accepter donc accepte aussi.

• Si . Il y a 2 cas possible.

  1. s’arrête sur en rejetant. Dans ce cas et donc rejette et va exécuter sur et M va rejeter dans aussi.
  2. ne s’arrête pas sur .
     Alors . Par conséquent, accepte . Donc rejette (par construction de )

Dans tous les cas . Finalement accepte .

On a montré l’existence d’une MT qui s’arrête sur toutes ses entrées et qui accepte , le langage est donc récursif

Contradiction donc ne peut pas être fini.

Exercice 14

Exercice 15

Exercice 16 15

Soit S une MT qui énumère en ordre lexicographique. On construiy un MT qui se comporte de la façon suivante:
Sur son entrée

1. M simule S sur sa bande de travail jusqu’à ce que finisse d’écrire un mot
2. compare et . Si ils sont égaux, s’arrête en acceptant

• Si w < v selon l’ordre lexicographique, M s’arrpete en rejettant
• Si w > v selon l’ordre lexicographique, on recommence à l’étape 1.

M s’arrête toujours.
L’ordre lexicographique étant un ordre total, il existe forcément un moment où et va s’arrêter.

M accepte L. Soit , alors va un jour être énuméré par . Comme énumère en ordre lexicographique, tous les mots V qui seront enumérés avant seront tels que V < w et donc ne sera pas arretée avant. Donc un jour aura écrit sur la bande et accepte.

Si . Alors S ne va jamais écrire sur sa bande et M n’acceptera pas

Donc est récursif

ne peut pas être énuméré en ordre lexicographique car l’ordre lexicographique n’est pas fondé: il existe une suite infinie décroissante:

Exemple:

Page incomplète ou erronée? Contribuez sur le repo