Modèles de calcul, TD numéro 10

Natacha Portier vendredi 14 avril 2000

Par convention une machine de Turing qui travaille en espace S(n) est une machine de Turing qui utilise au plus max(1, ⌈S(n)⌉) de chacun de ses rubans de travail. De même une machine de Turing qui travaille en temps T (n) est une machine qui effectue au plus max(n + 1, ⌈T (n)⌉) pas de calcul. L’alphabet utilisé est fini mais quelconque.

Question 1,1 : réduction du nombre de rubans pour la complexité en temps : 1 ruban

Montrer que si L est dans DT IME(T (n)) alors L est accepté par une machine de Turing à un ruban en temps T^{2}(n).

Question 1,2

Montrer que si L est dans NT IME(T (n)) alors L est accepté par une machine de Turing non déterministe à un ruban en temps non déterministe T^{2}(n).

Question 2: réduction du nombre de rubans pour la complexité en temps : 2 rubans

Nous allons montrer que si L est accepté par une machine de Turing M_{1} à k rubans alors L est accepté par une machine de Turing M_{2} à 2 rubans de travail en temps T (n) log T (n).

Question 2,1

Le premier ruban de M_{2} est constitué de 2k pistes. Nous allons voir comment simuler les calculs du premier ruban de M_{1} à l’aide des 2 premières pistes et du deuxième ruban. L’idée est qu’au lieu de déplacer la tête de lecture c’est le ruban qui se déplace.

Le premier ruban de M_{2} est découpé en blocs B_{i} avec i entier relatif. Le bloc B_{0} est constitué d’une case, le bloc B_{i}(i > 0) de 2^{i−1} cases ainsi que le bloc B_{−i}(i > 0).

Montrer, sur un exemple puis en donnant l’algorithme, comment simuler le déplacement de la tête de lecture de M_{1} en respectant les conditions suivantes :

1. B_{0} a toujours une lettre sur sa piste basse et sa piste haute contient un élément spécial qui permet de le repérer.

2. Pour i < j, B_{i} représente des cases à gauche de celles de B_{j}.

3. Le contenu de B_{i} représente des cases consécutives du ruban de M_{1}. Pour i > 0, la piste du haut représente les cases qui sont à la gauche de celles de la piste du bas. Pour i < 0 c’est l’inverse.

4. Pour tout i > 0

– soit les deux pistes de B_{i} sont pleines et B_{−i} est vide,

– soit l’inverse,

– soit les pistes basses de B_{i} et B_{−i} sont pleines et les hautes sont vides.

Question 2,2

Estimer le temps nécessaire si on doit aller jusqu’au bloc B_{i}. Combien doit-on faire de pas de calcul pour en arriver là ? En déduire le temps de calcul de M_{2} en fonction de celui de M_{1}. Considérer le cas des k rubans et conclure.

Question 2,3

Montrer que si L est accepté par une machine de Turing non déterministe à k rubans alors L est accepté par une machine de Turing non déterministe à 2 ruban en temps T (n) log T (n).

Question 3

Une fonction f est constructible en temps s’il existe une machine de Turing telle que sur l’entrée 1^{n} la machine s’arrête après f(n) pas de calcul.

Question 3,1

Est-ce que toute fonction calculable en temps est calculable en espace? Est-ce que la réciproque est vraie?

Question 3,2

Montrer que les fonctions suivantes sont constructibles en temps : (a) si p est un entier, la fonction constante égale à p

(b) f : n ↦ n

(c) si p est un entier, f : n ↦ n^{p}

(d) f : n ↦ 2^{n} si f et g sont constructibles en temps :

(e) f + g

(f) fg

Question 4

Montrer que DT IME(2^{n}) ⊊ DT IME(n2^{n}).