Cours sur les machines universelles

Informations

• Publié par: Ornui
• Nombre de lectures: 18
• Langue: Français

Extrait

6 6 ∗Machinesuniverselles †Résuméducoursd’AlainColmerauer mars2004 Tabledesmatières Isomorphie avec les entiers naturels Si l’alphabet Σ est un ensemblefinideβélémentsonpeutl’assimilerausous ensemble 1 Symboliqueversusnumérique 1 N ={0,1,...,β−1} (1)β 2 Machine 2 de l’ensembleN des entiers naturels, c’est à dire des entiers positifs ou nuls. Il existe alors des application bijective natu 3 Programmeuniversel 2 ?0 ?relles f : N → Σ et g : N → Σ . Pour β = 2 et la suite f(0),f(1),f(2),...est 4 MachinedeTuring 3 ε,1,01,11,001,101,011,111,0001,1001,1001,1101,0011,... 5 MachinedeTuringetchemindefer 3 1etlasuiteg(0),g(1),g(2),...est 6 Indécidabilitédel’arrêtd’unemachinedeTuring 4 ε,0,1,00,10,01,11,000,100,010,110,001,101,011,111,0000,... 7 CompositiondemachinesdeTuring 4 D’unefaçongénéraleonprend 8 MachinedeTuringarithmétisée 5 ( ε, sin = 0, sinon, f(n) = 9 Machineàinfinitéderégistres 5 (n modβ)·f(n÷β), (2)( 10 Machineàunrégistre 7 ε, sin = 0, sinon, g(n) = ((n−1) modβ)·g((n−1)÷β). 11 Machineàdeuxrégistres 7 avec n ≥ 0 et x÷y = bx/yc. On montre que f et g sont bien 12 Universalitédenosmachinesprogrammables 8 desbijectionsetque ( 13 Jeuxdelavie 8 0, six ...x =ε, sinon,0 k−1f (x ...x ) =0 k −1x +(β×f (x ...x )),0 1 k (3)( 0, six ...x =ε, sinon,0 k1 Symboliqueversusnumérique −1g (x ...x ) =0 k −1x +(β×g (x ...x ))+1.0 1 k Monoïde libre Soit Σ un ensemble appelé alphabet. Un mot Pouruneformulationplusexplicitedesvaleursdef etgonconstruit sur Σ, est une suite finie a = a a ...a d’éléments1 2 n trouvea deΣ.L’entiern,quipeutêtrenul,estla longueur|a|dumoti f(n) = x ...x , avec0 ka. L’unique mot de longueur nul est noté ε et l’ensemble des ? imotsconstruitssurΣestnotéΣ .Curieusementonauraaussi k = max{i∈N|n≥β }, ?αbesoindeconsidérerl’ensemble,notéΣ ,desmotsconstruits ix = (n÷β ) modβ,i sur Σquineseterminentpasparlesymboleα. (4) ? g(n) = x ...x , avec0 kSia =a ...a etb =b ...b sontdesélémentsdeΣ ,alors1 m 1 n i+1β −1aboua·bestlemota ...a b ...b .L’application(a,b)7→ab1 m 1 n k = max{i∈N|n≥ }, β−1? ? ? i+1deΣ ×Σ dansΣ estappeléeopérationdeconcaténation.C’est β −1 ix = ((n− )÷β ) modβ.i β−1une opération associative, c’est à dire que (xy)z = x(yz), et quiadmetεpourélémentneutre,c’est à direque xε =εx =x. 1.Pour justifier la suite il faudrait introduire l’ordre strict≺ suivant dans ? ?Si n est est entier positif ou nul et x un élément de Σ , on N :β n ? 0désigneparx l’élémentx···xde Σ .Enparticulierx =ε. | {z } m 0eta +1<β,1 2 n 1 2 n iSciences)etoption MASS (MathématiquesAppliquéesetSciencesSociales)   0·suc(a ...a ), sin> 0eta +1 =β.† Laboratoire d’Informatique Fondamentale de Marseille, CNRS et Uni n2 i versitésdeProvenceetdelaMéditerranée 1−1 −1Pouruneformulationplusexplicitedesvaleursdef etg En convenant que ω(%) = %, on prolonge naturellement ces ?ontrouve définitionsàtoutmotx∈ Σ par Pk−1 if (x ...x ) = β x , orbite(P,x) = orbite(P,α(x)).0 k ii=0 (5)Pk−1 ig (x ...x ) = β (x +1).0 k ii=0 trace(P,x) = trace(P,α(x)). Conclusion Labijectiong permetdetransposertoutemani resultat(P,x) = ω(resultat(P,α(x)) pulation d’entier naturels en une manipulation de mots sur Enfinonconvientqueun alphabet de β symboles et vice versa. Elle permet donc aussidetransposerunemanipulationdemotssurunalphabet resultat(P,%) = %.deβ symboles en une de mots sur un 0de β: il suffit de se servir de la bijection de type −1 −10 0 0 N →N :x7→g (g(x)),avecg définipar(2)etg définieβ β 3 Programmeuniversel0par(3)avecβ aulieudeβ. ?CodonstoutprogrammeP parunélémentdeΣ ,notécode(P). 2 Machine Définition UnprogrammeU estuniverselsi,pourtoutpro ?grammeP etpourtoutx∈ Σ ,onaDéfinition Une machineestuncouple (M,P), resultat(U,code(P)·x) = resultat(P,x) . (6) où M est une machine programmable et P un programme SidanslaformuleprécédenteonremplaceP parU,onobtient pourM.Une machine prMestunquintuplet une machine qui tourne une fois sur elle même pour ne rien faire: (Σ,C,α,ω,I), resultat(U,code(U)·x) = resultat(U,x). (7) n Sidanscettedernièreformuleonremplacexpar code(U) ·xoù onobtient Σ, l’alphabetdeM,estunensemblefininonvide; n+1 nC, est un ensemble, généralement infini, de configurations; resultat(U,code(U) ·x) = resultat(U,code(U) ·x) les couples (c ,c ) d’éléments de C sont appelés transi i j tions; etdonc : α, lafonctiond’entréeassocieuneconfigurationα(x)àchaque ?élémentxde Σ ; Propriété Si U est une machine universelle alors, quel que ? ?ω, lafonctiondesortieassocieunélémentω(c)deΣ àchaque soitn≥ 0etx∈ Σ , configurationc ;i n resultat(U,code(U) ·x) = resultat(U,x) .I, l’ensembledesinstructionsdeMestunensembledénom brable d’instructions; une intruction est un ensemble de transitions. Complexitésd’unprogrammeuniversel Complexitéquidé UnprogrammeP pourMestunsous ensemblede I,nefaisant pendde2paramètres, pas intervenir de transitions contradictoires, c’est à dire, ayant |trace(U,code(P)·x)|lamêmepremièrecomposante. λ(P,x) = |trace(P,x)| Fonctionnement Donnons nous une bonne fois pour toute Complexitéquidépendde1paramètre, unemachineprogrammableM.Enaccordavecleschéma |trace(U,code(U)·x)| λ(x) =x y |trace(U,x)| ↓ ↑ c −→ c −→ c ··· c −→ c0 1 2 n−1 n Coefficient d’introspection,unecomplexitéquin’existe pas tou jours mais qui est susceptible de ne dépendre d’aucun para pourtoutprogrammeP ettouteconfigurationc,ondéfinit mètre,  n+1 |trace(U,code(U) ·x)| lapluslonguesuitepossiblec ,c ,c ,...,0 1 2 λ = lim n n→∞ |trace(U,code(U) ·x)| orbite(P,c) = avecc =cetchaque0  (c ,c )élémentd’uneinstructiondeP.i i+1 ( (c ,c )(c ,c )(c ,c ) ...0 1 1 2 2 3 trace(P,c) = avec orbite(P,x) =c ,c ,c ,...,0 1 2 ( %, si orbite(P,c)estinfini, resultat(P,c)= c , si orbite(P,x)setermineparc .n n 26 6 locomotiveparcourantunréseaudechemindefer,faisantin 4 MachinedeTuring tervenirtroistypesd’aiguillages: Cette partie est fortement résumée. Pour plus de détails, consulter « Complexité d’un programme universel », exposé d’intérêtgénéraldonnéàLuminyle15mars2004,disponible à http://alain.colmerauer.free.fr Onsedonneunensembleinfinidénombrable{q ,q ,q ,...}0 1 2 ?d’états et un symbole spécialt, le blanc. Si x ∈ Σ , où Σ esttt un alphabet comprenant le blanc, on note·x le motx amputé desblancsdudébutetx·lemotxamputédesblancsdelafin. 1. l’aiguillage paresseux, qui mémorise la façon dont il a été prisdanslesensconfluentetrenvoiedanslamêmedirec tiondanslesensbifurquant,Définition Unemachineprogrammable(Σ,C,α,ω,I)estdite de Turingsi, 2. l’aiguillage à ressort, qui peut être pris dans le sens con fluent, mais qui envoie toujours dans la même direction– Σ = Σ ,avec Σ = Σ∪{t},t t danslesensbifurquant,– C estl’ensembledesquadrupletsdelaforme [q ,·x,a,y·],i ?avecq unétatquelconque,x,yprisdansΣ etaprisdansi t 3. l’aiguillage à bascule, qui dans le sens bifurquant envoie Σ ,t une fois dans une direction, une fois dans l’autre. Cet ai ?– α(x) = [q ,ε,t,x],pourtoutx∈ Σ ,0 guillagen’estpascenséêtreprisdanslesensconfluent. ?– ω([q ,·x,a,y·]) est l’élément de Σ le plus long qui com i Le ruban de la machine de Turing à n états q ,...q , estmencey·, 0 n−1 matérialiséparnvoiesparallèlesetchaquecaseestmatériali – I estl’ensemblesdesinstructionsnotéesetdéfinies,pour séeparunegareA.Pourn = 3onaladispositionsuivante:touslesétatsq ,q etélémentsa,bde Σ ,pari j t [q ,a,b,q ,G] :=i j A A A A{([q ,·xc,a,y·],[q ,·x,c,by·])|(x,c,y)∈E},i j [q ,a,b,q ,D] :=i j {([q ,·x,a,cy·],[q ,·xb,c,y·])|(x,c,y)∈E},i j – Le fait que la machine se trouve dans l’étatq ,...q se0 n−1 ? ?avecE = Σ ×Σ ×Σ . traduit par le fait que la locomotive se trouve sur la voiett t 0,...,n−1. – Le fait que la tête d’écriture lecture est positionnée surDéfinition Unemachineprogrammable(Σ,C,α,ω,I)estdite une certaine case se traduit par le fait que la locomotivede Turing avec polaritési, entredanslagareAcorrespondante. – Σ = Σ ,avec Σ = Σ∪{t},t t – Le fait que la machine s’arrête sur une certaine case se– C estl’ensembledesquintupletsdelaforme[s,q ,·x,a,y·],i ? traduitparlefaitquelalocomotiverentredanslehangaravec s ∈ {+,−}, q un état quelconque, x,y pris dans Σi t terminus,marqué FIN,delagareAcorrespondante.etaprisdans Σ ,t ?– α(x) = [+,q ,ε,t,x],pourtoutx∈ Σ ,0 – Lefaitqu’unecasdurubancontientlesymboletou1se ?– ω([s,q ,·x,a,y·])estl’élémentde Σ lepluslongquicom traduitparlefaitquelesnaigillagesàbasculeaucœurdei mencey·, la gare correspondante sont orientés dans un sens plutôt quedansunautre.– I estl’ensemblesdesinstructionsnotéesetdéfinies,pour touslesétatsq ,q etélémentsa,bde Σ ,pari j t Voicimaintenantl’architectured’unegareA, [q ,a,b,q ,−1] :=i j {([+,q ,·xc,a,y·],[−,q ,·x,c,by·])|(x,c,y)∈E}∪i j A{([−,q ,·x,a,cy·],[+,q ,·xb,c,y·])|(x,c,y)∈E},i j [q ,a,b,q ,+1] :=i j B 0 0{([−,q ,·xc,a,y·],[−,q ,·x,c,by·])|(x,c,y)∈E}∪i j 11{([+,q ,·x,a,cy·],[+,q ,·xb,c,y·])|(x,c,y)∈E},i j 2 2? ?avecE = Σ ×Σ ×Σ .t t t 2 1 0 0 1 2 5 MachinedeTuringetchemindefer NousallonssimulerfidèlementunemachinedeTuringd’al phabet Σ = {1}, et donc d’alphabet de ruban {t,1}, par une etsoncœurB, 36 6 6 6 – lefaitqu’ilestpossibledeconstruireunprogrammeDde B duplicationtelque,pourtoutedonnéex, u resultat(D,x) =x·x,C0 1 – le fait qu’il est possible de construire un programme M u de mise en boucletelque,pourtoutedonnéex,C1 1 ( %, six = 1, u resultat(M,x) = ε, six =ε.C2 1 Ladémonstrationproprementditesefaitparl’absurde.Sup F I N posons qu’il existe un programme A tel que (8) et montrons qu’on aboutit à une contradiction. A partir du programme A onpeutalorsconstruireleprogrammeB :=A◦Dquiestdonc telque,pourtoutprogrammeP,2 1 0 0 1 2 resultat(B, code(P)) = resultat(A, code(P)· code(P)), oùestprogramméelamachinedeTuring:   c’est à dire [q ,t,t,q ,D], 0 1 (   [q ,1,1,q ,D], 1, si resultat(P, code(P)) =%,1 1 . resulta