Calculabilité et complexité Cours no1
35
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
35
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Publié par
Langue
Français
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⊆ Σ´ ...
Voir
Publié par
Langue
Français
Calculabilit´eetcomplexite´ Cours no1
Nicolas (Miki) Hermann
´ LIX, Ecole Polytechnique
hermann@lix.polytechnique.fr
iMikHeramnnaCcllubaliti´eteocpmelixt´e(1)
Machine de Turingetsinitermd´eM= (Q,Σ,Γ, δ,
, , ,
)
e Q= ensemble fini d’ ´ tats Σla=bahpet(fini)d’entr´ee Γ = Σ∪ {.,t}= alphabet de travail .= limite gauche t= espace δ:Q×(Σ∪ {t})→(Q∪ {HALT,YES,NO})×Σ× {−1,0,1} = transition STARTd´=arep(tSTART∈Q) HALTa=rrˆet,YES= acceptation,NO= rejet (HALT,YES,NO∈Q)
MainchgnuTirseedSYETALHRTTASNOMiplextcomt´eebiliucalCnlamrnaikeH
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
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.
(1)it´elpxectmo´teeibildeTuringhcaMseni
MachinedeTuringd´eterministemulti-ruban(krubans,k∈N) M= (Q,Σ,Γ, δ,START,HALT,YES,NO) . . . δ:Q×(Σ∪ {t})k→(Q∪ {HALT,YES,NO})×(Σ× {−1,0,1})k Machine de Turing aveckrubans = notremod`eluudelclac
)1(
Resources : letempset l’espace
Si pour une machine de TuringM
´e(1exitompl
(START, .,x,(., )k−1)`tM(h,u1,w1, ,uk,wk)
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.
semeesr´suesRrcou
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
(START, .,x,(., )k−1)`∗M(HALT,u1,w1, ,uk,wk)
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
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.
ikMreHinnamclaCbaluuTirseedhcniaMng
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
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
(START, .,x,(., )k−1)`∗M(h,u1,w1, ,uk,wk)
MikiHermtceeplomitex(1´eCnnauclaibal´til
