Une machine de Turing M est dite linéairement bornée si elle n'écrit pas en dehors de l'espace utilisé par la donnée.
Comme on peut toujours supposer qu'une machine de Turing n'écrit pas le symbole blanc # (en le dupliquant éventuellement en un autre symbole #'), on peut aussi dire qu'une machine linéairement bornée est une machine telle que si p, # → q, b, x est une transition alors, b = # et x = L. Ceci impose à la machine qu'elle ne peut pas modifier les symboles blancs présents sur la bande.
L'espace utilisé par une machine linéairement bornée peut être augmenté en ajoutant de nouveaux symboles à l'alphabet de bande mais l'espace ainsi disponible reste proportionnel à la taille de l'entrée. Ceci justifie la terminologie.
L'objectif de cette partie est de définir les grammaires contextuelles et de montrer qu'elles ont même pouvoir d'expression que les machines linéairement bornées. Ceci signifie qu'un langage est accepté par une machine linéairement bornée si et seulement si il est engendré par une grammaire contextuelle.
Une grammaire contextuelle est un quadruplet (A, V, P, S) où A est un alphabet fini, V un ensemble fini de variables, S ∈ V est l'axiome et P est un ensemble de règles de la forme suivante.
L'élément important de cette définition est que seul l'axiome peut engendrer le mot vide. Hormis la règle S → 1, le membre droit d'une règle est toujours de longueur supérieure ou égale au membre gauche.
Une grammaire croissante est un triplet (A, V, P) où A est un alphabet fini, V un ensemble fini de variables et P est un ensemble de règles de la forme u → v avec u, v ∈ (A+V)* et |v| ≥ |u|.
La proposition suivante montre que grammaires contextuelles et grammaires croissantes sont équivalentes pour les langages ne contenant pas le mot vide.
Proposition. Un langage L ⊆ A+ est engendré par une grammaire contextuelle si et seulement si il est engendré par une grammaire croissante.
Une grammaire contextuelle qui ne contient pas la règle S → 1 est une grammaire croissante. Si L est engendré par une grammaire contextuelle, celle-ci ne contient pas la règle S → 1.
La réciproque est un peu plus délicate. Elle consiste à transformer une grammaire croissante en une grammaire contextuelle équivalente. Chaque règle de la grammaire croissante est remplacée par plusieurs règles dans la grammaire croissante construite. Quitte à introduire une nouvelle variable pour chaque lettre de A, on peut supposer que les règles de la grammaire croissante sont des deux formes suivantes.
Les règles de la forme S → a sont laissées telles quelles. Chaque règle Si1…Sik → Sj1…Sjm est remplacée par les règles suivantes.
où Z1, Z2, …, Zk-1 sont k-1 nouvelles variables propres à la règle transformée. Il facile de vérifier que les nouvelles règles simulent l'ancienne règle.
Les grammaires croissantes permettent de démontrer le résultat suivant.
Théorème. Un langage est engendré par une grammaire contextuelle si et seulement s'il est accepté par une machine linéairement borné.
Étant donné une grammaire quelconque, on peut toujours faire une machine de Turing non déterministe qui devine la dérivation à l'envers. La machine accepte lorsqu'elle trouve l'axiome. Si la grammaire est contextuelle, l'espace mémoire utilisé diminue au cours du calcul. On obtient donc une machine linéairement bornée.
Réciproquemnt soit une machine linéairement bornée M = (Q, Σ, Γ, E, q0, F, #). Sans perte de généralité, on peut supposer que la machine M a un seul état final qf, c'est-à-dire que F = { qf }. On construit alors la grammaire contextuelle (A, V, P, S) suivante. L'alphabet A est l'alphabet d'entrée Σ de M. L'ensemble V de variables est { S } ∪ Γ×Σ ∪ Q×Γ×Σ qui contient l'axiome S, les paires (a, b) formées d'une lettre a ∈ Γ; de l'alphabet de bande et d'une lettre b ∈ Σ de l'alphabet d'entrée ainsi que les triplets (q, a, b) formés d'un état q ∈ Q, d'une lettre a ∈ Γ de l'alphabet de bande et d'une lettre b ∈ Σ de l'alphabet d'entrée. L'ensemble P contient les règles des trois types suivants.
Certains problèmes comme celui de l'acceptation deviennent décidables pour les machines linéairement bornées alors que d'autres comme celui du vide restent indécidables.
Théorème. Il peut être décidé si une machine linéairement bornée accepte un mot w.
Pour une entrée de longueur n, le nombre de configurations possibles de la machine n|Q||Γ|n où |Q| est le nombre d'états et |Γ| le nombre de symboles de bande. On peut construire effectivement le graphe de calcul de la machine sur l'entrée w et décider s'il y a, dans ce graphe, un chemin de la configuration initiale q0w à une configuration acceptante.
Théorème. Il est indécidable de savoir si une machine M linéairement bornée n'accepte aucun mot, c'est-à-dire L(M) = ∅.
Soit M une machine de Turing quelconque et soit w un mot d'entrée de M. Soit $ un nouveau symbole qui n'appartient pas à Q ∪ Γ. On définit le langage Xw de la manière suivante.
Xw = { C0$C1$…$Ck | q0w = C0 ⇒ C1 ⇒ … ⇒ Ck est un calcul acceptant w }
Le langage Xw est accepté par une machine linéairement bornée M' qui peut être effectivement construite à partir de la machine M et de w. La machine M' doit vérifier que C0 = q0w, que Ci ⇒ Ci+1 pour 0 ≤ i < k et que Ck est acceptante. On a alors les équivalences
w ∈ L(M) ⇔ Xw ≠ ∅ ⇔ L(M') ≠ ∅
qui montre que le problème de l'acceptation pour les machines de Turing se réduit au problème du vide pour les machines linéairement bornées. Le problème du vide pour les machines linéairement bornées est donc indécidable.
Nous montrons dans cette partie que la famille des langages acceptés par des machines linéairement bornées est fermée par complémentation.
Théorème (Immerman). Pour toute machine M linéairement bornée et non-déterministe, il existe une machine M' linéairement bornée et non déterministe qui accepte le complémentaire du langage accepté par M.
Soit L un langage accepté par une machine linéairement bornée M. Pour une entrée w ∈ Σ* de M, on note N(w) le nombre de configurations de M qui peuvent être atteintes par M à partir de l'entrée w (c'est-à-dire de la configuration initiale q0w). On a l'inégalité N(w) ≤ K|w| pour une constante K bien choisie. Le nombre N(w) peut donc être stocké sur une bande de longueur |w|.
On construit une machine M' linéairement bornée et non déterministe qui accepte le complémentaire Σ* \ L du langage L. Pour une entrée w, le calcul de M' comprend les deux étapes principales suivantes.
On commence par décrire l'étape 2 puis on décrit l'étape 1.
Pour l'entrée w, on note C(w), l'ensemble des configurations contenues dans l'espace |w|.
Étape 2
i = 0
foreach c ∈ C(w)
choisir de façon non déterministe si q0w ⇒* c
if (q0w ⇒* c)
vérifier que q0w ⇒* c
if (la vérification réussit) i = i + 1
if (la vérification échoue) ÉCHEC
if (c est acceptante) ÉCHEC
if (i < N(w)) ÉCHEC
else ACCEPTER
On note Ni(w) le nombre de configurations qui peuvent être atteinte en au plus i étapes de calcul de M. On a N0(w) = 1 et N(w) = Ni(w) où i est le plus petit entier tel que Ni(w) = Ni+1(w). Pour calculer N(w), il suffit donc de savoir calculer Ni+1(w) à partir de Ni(w). La procédure suivante calcule Ni+1(w) à partir de Ni(w).
i = 0
foreach c ∈ C(w)
j = 0
foreach c' ∈ C(w)
choisir de façon non déterministe si q0w ⇒≤i c
if (q0w ⇒≤i c)
vérifier que q0w ⇒≤i c
if (la vérification réussit) j = j + 1
if (la vérification échoue) ÉCHEC
if ((c' == c) || (c' ⇒ c))
i = i + 1
break
if (j < Ni(w)) ÉCHEC
return i