CALCULABILITE 2ème Partie Machine de Turing.pdf


Preview of PDF document calculabilite-2eme-partie-machine-de-turing.pdf

Page 1 2 3 4 5 6

Text preview


Cours de LOGIQUE

*  (n , m )  IN2

q0n*m

F2 de IN2

telle que F2(n,m) = (n+1 ,m)

IN2

I de MT

q1 n+1 * m

* ….
*  (n1 , n2 , … , np)  INp q0 n1* n2 * … * np
Fp de INp

INp

I de MT

qf n1+1 * n2 * … * np

telle que Fp (n1 , n2 , … , np) = (n1 +1 , n2 , … , np)

6 ) COMPOSITION DE MACHINES DE TURING :
Théorème :
Soient deux machine de Turing :
- MT1 (S1 , E1 , I1) qui calcule la fonction F1 de INp

INq

- MT2 (S2 , E2 , I2) qui calcule la fonction F1 de INq

INr

telle que S1 = S2 .
Alors la machine de Turing MT ( S , E , I ) définie par :
S = S1 = S2
E = E1  E’2
I = I1  I’2  { qf1 1 1 q’i2 } où
E’2 et I’2 sont obtenus à partir de E2 et I2 en remplaçant chaque qi par q’i (renomage des
noms des états dans E2 et I2) de manière à ce que E1  E2 =  et I1  I2 =  ,
Permet de calculer la fonction composée (F2  F1).
La machine MT est considérée comme étant la composition des machines MT1 et MT2
notée : (MT2  MT1).

Lemme :
Les fonctions de Base : Z , S et Pin sont des fonctions calculables par des machine de Turing.

6