Calculabilité et complexité Cours no1

Nicolas (Miki) Hermann

Description

Calculabilite´ et complexite´oCours n 1Nicolas (Miki) Hermann´LIX, Ecole [e-mail]´ ´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⊆ Σ´ ...

Informations

• Publié par: Islue
• Nombre de lectures: 45
• Langue: Français

Extrait

Calculabilit ´ eetcomplexite ´ Cours n o 1

Nicolas (Miki) Hermann

´ LIX, Ecole Polytechnique

[e-mail]

iMikHeramnnaCcllubaliti´eteocpmelixt´e(1)

(1)it´e

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 START d ´ =arep(t START ∈Q) HALT a=rr ˆ et, YES = acceptation, NO = rejet ( HALT , YES , NO ∈Q)

MainchgnuTirseed SYETALHRTTASNO Miplextcomt´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 (q 0 ,u 0 ,v 0 )pour les configs(q,u,v)et (q 0 ,u 0 ,v 0 )siδ(q,a) = (q 0 ,b,D)ou`a=fst(v)tel que u 0 =ubetv=av 0 siD=1,u 0 =uetfst(v 0 ) =bsiD=0, u=u 0 lst(u)etv 0 =lst(u)bfollow(v)siD=−1 Calcul deM:(q,u,v)` ∗ M (q 0 ,u 0 ,v 0 ) 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) = YES siMacceptex(x∈L(M)) M(x) = NO siMrejettex(x∈L(M)) M(x) =%siM pas ne s’arreˆ  tesurx Si pour un langageLil existe une machine de TuringM, telle que six∈LalorsM(x) = YES six∈LalorsM(x) = NO nous disons queM de´ cide le langageL⊆Σ ∗ . Un langageL⊆Σ ∗ de ´ cid ´ eparunemachinedeTuringMs’appelleisrufce ´ r.

(1)it´elpxectmo´teeibil deTuringhcaMseni

laculibianrmalnCiMeHik ruTedsengnihiacM omtceet´´eitexpl

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(

nCanrmHekiMictee´tilibalucla)

Resources : letempset l’espace

Si pour une machine de TuringM

´e(1exitompl

( START , .,x,(., ) k−1 )` t M (h,u 1 ,w 1 ,    ,u k ,w k )

Si pour une machine de TuringMaveck rubans 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´eC MikiHermannCalculbalitie´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

L∈ DTIME (f(n))

Alors DTIME (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,(., ) k−1 )` ∗ M ( HALT ,u 1 ,w 1 ,    ,u k ,w k )

alorsM(x) =u k w k est ler ´ esultatdu travail deMsurx Ruban n o 1 = ban d’ ent ´ ruree Ruban n o k = 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 machineM 0 . La tabelleTest le seul ruban de la machineM 0  tes . Il faut ajouter les teˆ deMdans les colonnes deM 0 en tant que nouveaux symboles.

Theoreme ´ ` Pour chaque machine de TuringMaveckrubans travaillant en temps f(n)il existe une machine de TuringM 0 travaillant en tempsO(f(n) 2 ), telle que pour chaque motxnous avonsM(x) =M 0 (x).

Conclusion :de distinguer les machines de TuringIl est inutile  un  `a ou plusieurs rubans.

ikMreHinnamclaCbalu uTirseedhcniaMng

eontira´eirean´licA´cle mpcoxileitilet´eclaCbalureHinnam

Conclusion :Les constantes multiplicatives sont inutiles. L∈ DTIME (f(n))etL∈ DTIME (O(f(n))) signifient la meˆ  chose. me

puis simuledeuxpas deMparunpas deM 0 .

eor Th ´` eme SoitL∈ DTIME (f(n)). AlorsL∈ DTIME (f 0 (n)) ` ouf 0 (n) =cf(n) +n+2, pour chaquec>0.

´t(e)1

Ide´ e  de la preuve Preuve pourc=12. La machineMacceptantLtravaille en tempsf(n). Soitx=a 1 ∙ ∙ ∙a n le motd’entr ´ eedeM. La machineM 0 e ´ e ´ rrctixen x 0 =  a a 1  ∙ ∙ ∙  a n a − n 1  2

Mik

se´rusemsecruoseR

pourh∈ { HALT , YES , NO }alors l’espacede travail deMsurxest

k−1 X u i w i

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,u 1 ,w 1 ,    ,u k ,w k )

MikiHermtceeplomitex(1´eCnnauclaibal´til