Calculabilite´ et complexite´oCours n 1Nicolas (Miki) Hermann´LIX, Ecole Polytechniquehermann@lix.polytechnique.fr´ ´Miki Hermann Calculabilite et complexite (1)Machines de TuringMachine de Turing deter´ ministe M = (Q,Σ,Γ,δ,START,HALT,YES,NO)´Q = ensemble fini d’etats´Σ = alphabet (fini) d’entreeΓ = Σ∪{ , t} = alphabet de travail. = limite gauchet = espaceδ: Q×(Σ∪{t})→ (Q∪{HALT,YES,NO})×Σ×{−1,0,1}= transitionSTART = depar´ t (START∈ Q)HALT = arret,ˆ YES = acceptation, NO = rejet(HALT,YES,NO∈/ Q)´ ´Miki Hermann Calculabilite et complexite (1)Machines de TuringM = (Q,Σ,Γ,δ,START,HALT,YES,NO)∗ ∗Configuration : (q,u,w)∈ (Q∪{HALT,YES,NO})×Γ ×Γ∗Config. acceptante : (YES,u,w) pour des mots u,w∈ Γ0 0 0Pas de M : (q,u,v)‘ (q ,u ,v ) pour les configs (q,u,v) etM0 0 0 0(q ,u ,v ) si δ(q,a) = (q ,b,D) ou` a = fst(v) tel que0 0 0 0u = ub et v = av si D =1, u = u et fst(v ) = b si D =0,0 0u = u lst(u) et v = lst(u)bfollow(v) si D =−1∗ 0 0 0Calcul de M : (q,u,v)‘ (q ,u ,v )M∗ ∗Langage accepte´ : L(M) ={x∈ Σ | (START, , x)‘ (YES,u,v)}M´ ´Miki Hermann Calculabilite et complexite (1)Machines de Turing∗Pour une machine M et un mot x∈ Σ , M(x) est le resultat´ du calculde M sur xM(x) = YES si M accepte x (x∈ L(M))M(x) = NO si M rejette x (x∈/ L(M))M(x) =% si M ne s’arreteˆ pas sur xSi pour un langage L il existe une machine de Turing M, telle quesi x∈ L alors M(x) = YESsi x∈/ L alors M(x) = NO∗ ∗´nous disons que M decide le langage L⊆ Σ . Un langage L⊆ Σ´ ...
M= (Q,Σ,Γ, δ,START,HALT,YES,NO) Configuration :(q,u,w)∈(Q∪ {HALT,YES,NO})×Γ∗×Γ∗ Config. acceptante :(YES,u,w)pour des motsu,w∈Γ∗ Pas deM:(q,u,v)`M(q0,u0,v0)pour les configs(q,u,v)et (q0,u0,v0)siδ(q,a) = (q0,b,D)ou`a=fst(v)tel que u0=ubetv=av0siD=1,u0=uetfst(v0) =bsiD=0, u=u0lst(u)etv0=lst(u)bfollow(v)siD=−1 Calcul deM:(q,u,v)`∗M(q0,u0,v0) Langage accepte´ :L(M) ={x∈Σ∗|(START, .,x)`∗M(YES,u,v)}
gniruacMeTsdnehi
alnClacuHekianrmiM
Pour une machineMet un motx∈Σ∗,M(x)est lettaulse´rdu calcul deMsurx M(x) =YESsiMacceptex(x∈L(M)) M(x) =NOsiMrejettex(x∈L(M)) M(x) =%siM pasne s’arreˆ tesurx Si pour un langageLil existe une machine de TuringM, telle que six∈LalorsM(x) =YES six∈LalorsM(x) =NO nous disons queMde´ cidele langageL⊆Σ∗. Un langageL⊆Σ∗ de´cid´eparunemachinedeTuringMs’appelleisrufce´r.
Si pour une machine de TuringMaveckrubans et l’entre´ exnous avons
Nous disons que la machineMtravaille en tempsf(n)si pour chaque motxle temps de travail deMsurxest au plusf(|x|). La fonctionf(n) est laborne temporelledeM.
pourh∈ {YES,NO}alors letempsde travail deMsurxestt. Si M(x) =%alors le temps de travail deMsurxest infini.
Supposons que le langageL⊆Σ∗est de´ cide´ par une machine de TuringMaveckrubans travaillant en tempsf(n). Nous alons alors ´ i ecr re
L∈DTIME(f(n))
AlorsDTIME(f(x))est un ensemble de langages. Il contient exactement les langages de´ cidables par une machine de Turing multi-ruban travaillant en tempsf(x). DTIME(f(n))est uneesedocpmelix´teascl
alorsM(x) =ukwkest ler´esultatdu travail deMsurx Ruban no1 = ban d’ent ´ ruree Ruban nok = ruban desortie Rubans 2, . . . , k-1 = rubans detravail
Pour une machineMaveckrubans et un motx, si
1)MingeTurnesdachi
´eetilitlexicomp)1
Comparaison de puissance des machines de Turing multi-ruban
´t(e
Id´eedelapreuve Leskrubans de la machineMleeltebaemnucsmoer´esid´tconsonT. Chaque colonne de la tabelleTest un symbole de la machineM0. La tabelleTest le seul ruban de la machineM0 tes. Il faut ajouter les teˆ deMdans les colonnes deM0en tant que nouveaux symboles.
Theoreme ´ ` Pour chaque machine de TuringMaveckrubans travaillant en temps f(n)il existe une machine de TuringM0travaillant en tempsO(f(n)2), telle que pour chaque motxnous avonsM(x) =M0(x).
Conclusion :de distinguer les machines de TuringIl est inutile un `a ou plusieurs rubans.
Conclusion :Les constantes multiplicatives sont inutiles. L∈DTIME(f(n))etL∈DTIME(O(f(n)))signifient la meˆ chose. me
puis simuledeuxpas deMparunpas deM0.
eor Th´`eme SoitL∈DTIME(f(n)). AlorsL∈DTIME(f0(n))`ouf0(n) =cf(n) +n+2, pour chaquec>0.
´t(e)1
Ide´ e de la preuve Preuve pourc=12. La machineMacceptantLtravaille en tempsf(n). Soitx=a1∙ ∙ ∙anle motd’entr´eedeM. La machineM0e´e´rrctixen x0=aa1∙ ∙ ∙ana−n1 2
Mik
se´rusemsecruoseR
pourh∈ {HALT,YES,NO}alors l’espacede travail deMsurxest
k−1 Xuiwi
i=2
(car le ruban est l’entre´ e et le rubankest la sortie). Nous disons que la machineMtravaille en espacef(n)si pour chaque motxl’espace de travail deMsurxest au plusf(|x|). La fonctionf(n)est laborne spatialedeM.
)
Si pour une machine de TuringMaveckbunaeslte’tn´reerxnous avons