13.4 Les machines de Turing et les syst` emes d’insertion–d´ el´ etion
441
correspondant `
a l’ancien ´ etat et la remplacer par une portion de chaˆ ıne correspondant
au nouvel ´ etat. Finalement, il doit couper la portion de chaˆ ıne correspondant ` a l’ancienne position du pointeur et la remplacer par une portion de chaˆ ıne correspondant ` a
la nouvelle position du pointeur.
Id´ ee de la preuve du th´ eor` eme 13.43 Nous voulons montrer que toutes les actions
sur le ruban que peut faire une machine de Turing peuvent aussi ˆ etre faites sur des mots
par un syst` eme d’insertion–d´ el´ etion. Pour chaque transition sur le ruban d’une machine
de Turing, nous allons donc construire le syst` eme d’insertion–d´ el´ etion qui effectue la
mˆ eme action sur une chaˆ ıne de caract` eres repr´ esentant l’entr´ ee du ruban.
Soit M = (Q, X, ϕ) une machine de Turing. Si ϕ(q i , x i ) = (q j , x j , c), nous noterons
(q i , x i ) → (q j , x j , c), o` u c ∈ (−1, 0, 1). S´ eparons cette r` egle selon que c = 0, c = 1
ou c = −1. Il faut v´ erifier que chacune de ces trois r` egles de transition poss` ede un
´ equivalent dans un syst` eme d’insertion–d´ el´ etion ID = (N, I, D) pour lequel N sera de
la forme N = X ∪ Q ∪ {L, R, O} ∪ {q
i : q i ∈ Q}. Les ensembles {q
i : q i ∈ Q} et
{L, R, O} et leur rˆ ole seront explicit´ es dans la preuve. Le but est de construire, pour
chacune des r` egles de transition de la machine de Turing, un ensemble d’insertions et
de d´ el´ etions qui, effectu´ ees dans un ordre prescrit, ont le mˆ eme effet que la r` egle de
transition. Une mise en garde : nous devons empˆ echer que ces insertions et d´ el´ etions
puissent ˆ etre ex´ ecut´ ees dans un autre ordre avec pour effet de produire des r´ esultats
non conformes aux instructions de la machine de Turing.
Nous utiliserons diverses chaˆ ınes de caract` eres dans cette preuve. Notons que μ, μ 1 , ν,
x i , x j , μ 2 , ρ, σ, τ ∈ X et q i , q j ∈ Q.
1. Pour toutes les r` egles de la forme (q i , x i ) → (q j , x j , 0), nous devons ajouter ` a ID les
trois r` egles suivantes : (q i x i , q j Ox j , ν) I , (μ, q i x i , q j Ox j ) D , (ρσq j , O, x j ) D pour tous
les μ, ν, ρ, σ ∈ X. En fait, pour chaque caract` ere ν de X, il faut ajouter `
a ID une
r` egle de la forme (q i x i , q j Ox j , ν) I , et de mˆ eme pour les deux autres r` egles. Puisque
la cardinalit´ e de X est finie, nous avons un nombre fini de r` egles ` a ajouter ` a ID, et
cela ne pose donc aucun probl` eme.
Nous pouvons alors effectuer les op´ erations suivantes sur une chaˆ ıne de la forme
μq i x i ν :
μq i x i ν =⇒ I μq i x i q j Ox j ν =⇒ D μq j Ox j ν =⇒ D μq j x j ν.
D´ ecrivons-les. Partant de la chaˆ ıne μq i x i ν, nous ins´ erons la chaˆ ıne q j Ox j entre q i x i
et ν. Suivent deux d´ el´ etions : la premi` ere permet d’enlever q i x i , la seconde spprime
le O restant entre q j et x j . Le r´ esultat final, μq j x j ν, est la chaˆ ıne que nous voulions
obtenir. Rappelons que le caract` ere repr´ esentant l’´ etat du pointeur, c’est-` a-dire q j ,
pr´ ec` ede le caract` ere sur lequel le pointeur se trouve. Nous voyons alors que les
op´ erations pr´ ec´ edentes nous ont permis de passer de la configuration μx i ν dans
l’´ etat q i ` a la configuration μx j ν dans l’´ etat q j .
Pourquoi avons-nous utilis´ e ce O ? Pourquoi n’avons-nous pas simplement effectu´ e
μq i x i ν =⇒ I μq i x i q j x j ν =⇒ D μq j x j ν?
441
correspondant `
a l’ancien ´ etat et la remplacer par une portion de chaˆ ıne correspondant
au nouvel ´ etat. Finalement, il doit couper la portion de chaˆ ıne correspondant ` a l’ancienne position du pointeur et la remplacer par une portion de chaˆ ıne correspondant ` a
la nouvelle position du pointeur.
Id´ ee de la preuve du th´ eor` eme 13.43 Nous voulons montrer que toutes les actions
sur le ruban que peut faire une machine de Turing peuvent aussi ˆ etre faites sur des mots
par un syst` eme d’insertion–d´ el´ etion. Pour chaque transition sur le ruban d’une machine
de Turing, nous allons donc construire le syst` eme d’insertion–d´ el´ etion qui effectue la
mˆ eme action sur une chaˆ ıne de caract` eres repr´ esentant l’entr´ ee du ruban.
Soit M = (Q, X, ϕ) une machine de Turing. Si ϕ(q i , x i ) = (q j , x j , c), nous noterons
(q i , x i ) → (q j , x j , c), o` u c ∈ (−1, 0, 1). S´ eparons cette r` egle selon que c = 0, c = 1
ou c = −1. Il faut v´ erifier que chacune de ces trois r` egles de transition poss` ede un
´ equivalent dans un syst` eme d’insertion–d´ el´ etion ID = (N, I, D) pour lequel N sera de
la forme N = X ∪ Q ∪ {L, R, O} ∪ {q
i : q i ∈ Q}. Les ensembles {q
i : q i ∈ Q} et
{L, R, O} et leur rˆ ole seront explicit´ es dans la preuve. Le but est de construire, pour
chacune des r` egles de transition de la machine de Turing, un ensemble d’insertions et
de d´ el´ etions qui, effectu´ ees dans un ordre prescrit, ont le mˆ eme effet que la r` egle de
transition. Une mise en garde : nous devons empˆ echer que ces insertions et d´ el´ etions
puissent ˆ etre ex´ ecut´ ees dans un autre ordre avec pour effet de produire des r´ esultats
non conformes aux instructions de la machine de Turing.
Nous utiliserons diverses chaˆ ınes de caract` eres dans cette preuve. Notons que μ, μ 1 , ν,
x i , x j , μ 2 , ρ, σ, τ ∈ X et q i , q j ∈ Q.
1. Pour toutes les r` egles de la forme (q i , x i ) → (q j , x j , 0), nous devons ajouter ` a ID les
trois r` egles suivantes : (q i x i , q j Ox j , ν) I , (μ, q i x i , q j Ox j ) D , (ρσq j , O, x j ) D pour tous
les μ, ν, ρ, σ ∈ X. En fait, pour chaque caract` ere ν de X, il faut ajouter `
a ID une
r` egle de la forme (q i x i , q j Ox j , ν) I , et de mˆ eme pour les deux autres r` egles. Puisque
la cardinalit´ e de X est finie, nous avons un nombre fini de r` egles ` a ajouter ` a ID, et
cela ne pose donc aucun probl` eme.
Nous pouvons alors effectuer les op´ erations suivantes sur une chaˆ ıne de la forme
μq i x i ν :
μq i x i ν =⇒ I μq i x i q j Ox j ν =⇒ D μq j Ox j ν =⇒ D μq j x j ν.
D´ ecrivons-les. Partant de la chaˆ ıne μq i x i ν, nous ins´ erons la chaˆ ıne q j Ox j entre q i x i
et ν. Suivent deux d´ el´ etions : la premi` ere permet d’enlever q i x i , la seconde spprime
le O restant entre q j et x j . Le r´ esultat final, μq j x j ν, est la chaˆ ıne que nous voulions
obtenir. Rappelons que le caract` ere repr´ esentant l’´ etat du pointeur, c’est-` a-dire q j ,
pr´ ec` ede le caract` ere sur lequel le pointeur se trouve. Nous voyons alors que les
op´ erations pr´ ec´ edentes nous ont permis de passer de la configuration μx i ν dans
l’´ etat q i ` a la configuration μx j ν dans l’´ etat q j .
Pourquoi avons-nous utilis´ e ce O ? Pourquoi n’avons-nous pas simplement effectu´ e
μq i x i ν =⇒ I μq i x i q j x j ν =⇒ D μq j x j ν?