Calculabilité et complexité Cours no1

De
Publié par

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⊆ Σ´ ...
Publié le : samedi 24 septembre 2011
Lecture(s) : 44
Nombre de pages : 35
Voir plus Voir moins
Calculabilit´eetcomplexite´ Cours no1
Nicolas (Miki) Hermann
´ LIX, Ecole Polytechnique
hermann@lix.polytechnique.fr
iMikHeramnnaCcllubaliti´eteocpmelixt´e(1)
(1)it´e
Machine de Turingetsinitermd´eM= (Q,Σ,Γ, δ,
, , ,
)
e Q= ensemble fini d’ ´ tats Σla=bahpet(ni)dentr´ee Γ = Σ∪ {.,t}= alphabet de travail .= limite gauche t= espace δ:Q×∪ {t})(Q∪ {HALT,YES,NO})×Σ× {−1,0,1} = transition STARTd´=arep(tSTARTQ) HALTa=rrˆet,YES= acceptation,NO= rejet (HALT,YES,NOQ)
MainchgnuTirseedSYETALHRTTASNOMiplextcomt´eebiliucalCnlamrnaikeH
iMikeHmrnaCnlaculabilit´eetcomxelpe´ti)1(
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(xL(M)) M(x) =NOsiMrejettex(xL(M)) M(x) =%siM pasne s’arreˆ tesurx Si pour un langageLil existe une machine de TuringM, telle que sixLalorsM(x) =YES sixLalorsM(x) =NO nous disons queMde´ cidele langageLΣ. Un langageLΣde´cid´eparunemachinedeTuringMs’appelleisrufce´r.
(1)it´elpxectmo´teeibildeTuringhcaMseni
laculibianrmalnCiMeHikruTedsengnihiacMomtceet´´eitexpl
MachinedeTuringd´eterministemulti-ruban(krubans,kN) M= (Q,Σ,Γ, δ,START,HALT,YES,NO) . . . δ:Q×∪ {t})k(Q∪ {HALT,YES,NO})×× {−1,0,1})k Machine de Turing aveckrubans = notremod`eluudelclac
)1(
nCanrmHekiMictee´tilibalucla)
Resources : letempset l’espace
Si pour une machine de TuringM
´e(1exitompl
(START, .,x,(., )k1)`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
leelitexplomormpte´eCMikiHermannCalculbalitie´teocpmelxit´e(1)
Supposons que le langageLΣest de´ cide´ par une machine de TuringMaveckrubans travaillant en tempsf(n). Nous alons alors ´ i ecr re
LDTIME(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
elix´t(ee´teocpmulabilitmannCalckiMreHi
(START, .,x,(., )k1)`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
´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.
ikMreHinnamclaCbaluuTirseedhcniaMng
eontira´eirean´licA´clempcoxileitilet´eclaCbalureHinnam
Conclusion :Les constantes multiplicatives sont inutiles. LDTIME(f(n))etLDTIME(O(f(n)))signifient la meˆ chose. me
puis simuledeuxpas deMparunpas deM0.
eor Th´`eme SoitLDTIME(f(n)). AlorsLDTIME(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 motdentr´eedeM. La machineM0e´e´rrctixen x0=aa1∙ ∙ ∙anan12
Mik
se´rusemsecruoseR
pourh∈ {HALT,YES,NO}alors l’espacede travail deMsurxest
k1 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 TuringMaveckbunaesltetn´reerxnous avons
(START, .,x,(., )k1)`M(h,u1,w1,    ,uk,wk)
MikiHermtceeplomitex(1´eCnnauclaibal´til
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.