13.3 Machines de Turing et fonctions r´ ecursives
425
machines particuli` eres peuvent se ramener ` a des machines de Turing standard [8] ; c’est
pourquoi nous consacrerons notre ´ etude ` a celles-ci. Notons qu’` a tout moment, mˆ eme si le
ruban est non born´ e, seul un nombre fini de cases du ruban contiennent un caract` ere de
l’alphabet de ruban autre que le symbole blanc puisque la chaˆ ıne enregistr´ ee au d´ epart
est finie et qu’` a chaque ´ etape, on change au plus un symbole blanc en un caract` ere de
l’alphabet.
Avant d’aller plus loin, il est primordial de d´ efinir rigoureusement ce qu’est une
fonction calculable par une machine de Turing, fonction que nous appellerons MTcalculable. Cependant, nous devons tout d’abord prendre le temps de d´ efinir l’ensemble
des mots bˆ atis avec un alphabet X, ensemble que nous utiliserons `
a quelques reprises.
D´ efinition 13.3 Soient X un alphabet et λ le mot ne comportant aucun caract` ere.
L’ensemble X
∗ des mots construits avec l’alphabet X est d´ efini comme suit :
(i) λ ∈ X
∗ ;
(ii) si a ∈ X et c ∈ X
∗ , alors ca ∈ X
∗ , o` u ca repr´ esente le mot construit ` a partir du
mot c par addition du symbole a ` a droite ;
(iii) ω ∈ X
∗ seulement s’il peut ˆ etre obtenu de λ par application de l’´ etape (ii) un
nombre fini de fois.
Nous utiliserons aussi `
a quelques reprises une op´ eration sur deux mots qu’on nomme
la concat´ enation. Nous allons d´ efinir cette derni` ere op´ eration.
D´ efinition 13.4 Soient b et c deux mots de X
∗ . La concat´ enation de b et de c est le
mot bc ∈ X
∗ qu’on obtient en ´ ecrivant c ` a la suite de b.
D´ efinition 13.5 Une machine de Turing M = (Q, X, ϕ) calcule la fonction f : U ⊂
X
∗
→ X
∗ si
1. il existe une unique transition de q 0 et que sa forme est ϕ(q 0 , B) = (q i , B, 1), q i = q 0 ;
2. il n’existe pas de transition de la forme ϕ(q i , x) = (q 0 , y, c), o` u i = 0, x, y ∈ X et
c ∈ {−1, 0, 1} ;
3. il n’existe pas de transition de la forme ϕ(q f , B), o` u q f ∈ Q f ;
4. pour tout μ ∈ U , le calcul effectu´ e par M sur μ pour q 0 BμB comme configuration
initiale s’arrˆ ete dans la configuration finale q f BνB, ν ∈ X
∗ , apr` es un nombre fini
d’´ etapes si f (μ) = ν. (Nous dirons qu’une machine de Turing s’arrˆ ete dans la
configuration q i x 1 ...x n si la valeur ϕ(q i , x 1 ) n’est pas d´ efinie) ;
5. le calcul effectu´ e par M continue ind´ efiniment si l’entr´ ee est μ ∈ X
∗ et que f (μ)
n’est pas d´ efinie, c’est-` a-dire si μ ∈ X
∗
\ U .
On dit alors que la fonction f est MT-calculable.
425
machines particuli` eres peuvent se ramener ` a des machines de Turing standard [8] ; c’est
pourquoi nous consacrerons notre ´ etude ` a celles-ci. Notons qu’` a tout moment, mˆ eme si le
ruban est non born´ e, seul un nombre fini de cases du ruban contiennent un caract` ere de
l’alphabet de ruban autre que le symbole blanc puisque la chaˆ ıne enregistr´ ee au d´ epart
est finie et qu’` a chaque ´ etape, on change au plus un symbole blanc en un caract` ere de
l’alphabet.
Avant d’aller plus loin, il est primordial de d´ efinir rigoureusement ce qu’est une
fonction calculable par une machine de Turing, fonction que nous appellerons MTcalculable. Cependant, nous devons tout d’abord prendre le temps de d´ efinir l’ensemble
des mots bˆ atis avec un alphabet X, ensemble que nous utiliserons `
a quelques reprises.
D´ efinition 13.3 Soient X un alphabet et λ le mot ne comportant aucun caract` ere.
L’ensemble X
∗ des mots construits avec l’alphabet X est d´ efini comme suit :
(i) λ ∈ X
∗ ;
(ii) si a ∈ X et c ∈ X
∗ , alors ca ∈ X
∗ , o` u ca repr´ esente le mot construit ` a partir du
mot c par addition du symbole a ` a droite ;
(iii) ω ∈ X
∗ seulement s’il peut ˆ etre obtenu de λ par application de l’´ etape (ii) un
nombre fini de fois.
Nous utiliserons aussi `
a quelques reprises une op´ eration sur deux mots qu’on nomme
la concat´ enation. Nous allons d´ efinir cette derni` ere op´ eration.
D´ efinition 13.4 Soient b et c deux mots de X
∗ . La concat´ enation de b et de c est le
mot bc ∈ X
∗ qu’on obtient en ´ ecrivant c ` a la suite de b.
D´ efinition 13.5 Une machine de Turing M = (Q, X, ϕ) calcule la fonction f : U ⊂
X
∗
→ X
∗ si
1. il existe une unique transition de q 0 et que sa forme est ϕ(q 0 , B) = (q i , B, 1), q i = q 0 ;
2. il n’existe pas de transition de la forme ϕ(q i , x) = (q 0 , y, c), o` u i = 0, x, y ∈ X et
c ∈ {−1, 0, 1} ;
3. il n’existe pas de transition de la forme ϕ(q f , B), o` u q f ∈ Q f ;
4. pour tout μ ∈ U , le calcul effectu´ e par M sur μ pour q 0 BμB comme configuration
initiale s’arrˆ ete dans la configuration finale q f BνB, ν ∈ X
∗ , apr` es un nombre fini
d’´ etapes si f (μ) = ν. (Nous dirons qu’une machine de Turing s’arrˆ ete dans la
configuration q i x 1 ...x n si la valeur ϕ(q i , x 1 ) n’est pas d´ efinie) ;
5. le calcul effectu´ e par M continue ind´ efiniment si l’entr´ ee est μ ∈ X
∗ et que f (μ)
n’est pas d´ efinie, c’est-` a-dire si μ ∈ X
∗
\ U .
On dit alors que la fonction f est MT-calculable.