Modèles de calcul, TD numéro 9

Natacha Portier vendredi 7 avril 2000

Une fonction f est constructible en espace s’il existe une machine de Turing avec un ruban d’entrée et un ruban de travail tel que sur l’entrée 1^{n} la machine s’arrête avec sur son ruban de travail 1^{f(n)} et les autres cases n’ont pas été utilisées (les blancs lus à la fin et au début du ruban ne sont pas considérés comme utilisés.

Question 1

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

(b) f : n ↦ n

(c) f : n ↦ ⌈n/2⌉

(d) f : n ↦ n^{2}

(e) f : n ↦ 2^{n}

(f) f : n ↦ ⌈\sqrt{n}⌉

(g) f : n ↦ ⌈log_{2}(n)⌉ si f et g sont constructibles en espace :

(h) f − 1

(i) f + g

(j) fg

(k) 2^{f}

Les machines de Turing considérées ont un ruban d’entrée en lecture seule et des rubans de travail. 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 2,1 : compression d’espace

Soit L un langage accepté par une machine de Turing avec k rubans de travail en espace S(n). Soit c > 0. Montrer que L est accepté par une machine de Turing en espace cS(n).

Question 2,2 Montrer que si L est dans NESP ACE(S(n)) alors pour toute constante c strictement positive L est dans NESP ACE(cS(n)). Question 3 : réduction du nombre de rubans Montrer que si L est un langage accepté par une machine de Turing avec k rubans de travail en espace S(n), alors L est accepté par une machine de Turing avec un seul ruban de travail en espace S(n). Question 4,1 : accélération linéaire Soit L un langage accepté par une machine de Turing avec k rubans de travail en temps T (n) avec lim_{n→∞} T (n)/n = ∞ et soit c > 0. Alors L est accepté par une machine de Turing avec k rubans en temps cT (n). Question 4,2 Montrer que si lim_{n→∞} T (n)/n = ∞ et c > 0 alors DT IME(T (n)) = DT IME(cT (n)). Question 4,3 Appliquer le résultat au cas où T (n) = dn pour une constante d > 1. Montrer que pour tout ε > 0 on a DT IME(T (n)) = DT IME((1 + ε)T (n)). Question 5,1 : réduction du nombre de rubans pour la complexité en temps 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 5,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).