[PDF] Calculabilité Cours 1 : machines de Turing

View - Download Calculabilité Cours 1 : machines de Turing

Previous PDF

Next PDF

Calculabilite

Cours 1 : machines de TuringKevinPerrot{ Aix Marseille Universite { printemps 2019

0 Divertissement

collatz(n:int) print n; si n == 1 alors stop, sinon si n%2 == 0 alors collatz(n/2), sinon collatz(3*n+1), finsi finsi Est-ce que le programmecollatztermine sur toute entreen? Comment le savoir?

T esterp ourtout n1020?

T estersi 9n,xtel quecollatz(n)=collatzx(n)?

V ousa vezun an a vec10 programmeurs surdou es.Commen tfaites-v ous?

Suite de Collatz (1937) :n7!n=2 sinmod 2 == 0

n3 + 1 sinon Conjectures refutees par de grands contre-exemples : C onjectured'Euler (1772). 8n >2 :8x1;:::;xk;z2N:Pk i=1xni6=zn. n= 5 (1966) : 275+ 845+ 1105+ 1335= 1445 n= 4 (1988) : 26824404+ 153656394+ 187967694= 206156734 n >5 : inconnu. C onjecturede P olya(1919). Plus de la moiti edes en tiersnaturels inf erieurs aun entier donne ont un nombre impair de facteurs premiers. (1980) : le plus petit contre exemple est 906150257. C onjecturede Mertens (1885) : prouv eefausse mais aucun con treexemple explicite connu.

2006 : plus petit contre exemple compris entre 10

14et 1:591040

Nom brede Sk ewes(1914).

1955 : il existe un tel nombre inferieur a 10

1010963.

1987 : il existe un tel nombre inferieur a 710370.

La morale de cet example est que les ordinateurs n'ont pas reponse a tout! 1

Table des matieres

0 Divertissement 1

1 Introduction 2

2 Machines de Turing 4

2.1 Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.2 Decider et calculer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.3 Proprietes de cl^oture . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.4 Un peu d'histoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 Ce cours est base sur le livre de Sipser [2] et le cours de Kari [1].

1 Introduction

Une machine de Turing est un objet mathematique, deni en 1936 parAlan Turing, qui a pour but de decrire ce qu'est uncalcul. Tout le monde sent ce qu'est un calcul : si vous avez deux nombre en base 10, disons123et456, et vous voulez calculer leur somme, vous le faites chire par chire de droite a gauche en propageant d'eventuelles retenues pour obtenir579. Si vous voulez calculer leur produit, vous le decomposez en multiplications plus simples pour lesquelles vous avez appris un nombre ni de tables, et vous sommez les resultats des sous-problemes :

123x456 =(1x100+2x10+3)x(4x100+5x10+6)

+(2x4)x(10x100)+(2x5)x(10x10)+(2x6)x(10) +(3x4)x(100)+(3x5)x(10)+(3x6) =56088. Lorsque vous apprenez a quelqu'un une methode pour eectuer une multiplication, vous decrivez unalgorithme: vous donnez une description nie (par exemple en 10 minutes de parole, ou en 2 pages) de la procedure a suivre pour obtenir le resultat.Les machines de Turing sont des objets mathematiques pour decrire les algorithmes. Une machine de Turing pour l'addition de nombres naturels en base 10 donne l'ensemble des instructions qu'il faut eectuer pour calculer la somme de deux nombres. Une remarque importante est que la description de la procedure est nie, mais elle permet de calculer la somme de n'importe quel couple de nombres :123+456ou1234567890+2345678901 ou des nombres plus grands! Bon, soyons serieux. Une machine de Turing decrit comment calculer quelque chose. Mais quel est cequelque chose? C'est unefonction. Par exemple, une fonction peut-^etre l'addition, ou la multiplication : etant donnee uneentreenie (dans notre exemple123 et456), une fonction associe une uniquesortie. L'entree et la sortie peuvent ^etre un ou plusieurs entiers naturels, des nombres negatifs, une phrase ecrite en alphabet Latin ou n'importe quel autre. Le point important est qu'elle soit de taillenie. Une fonction associe alors une unique sortie (le resultat) a chaque entree. Les fonctions peuvent ^etre simples : l'addition ou la multiplication de deux entiers naturels; ou plus compliquees : etant donne un entier naturel, quelle est sa decomposition en produit de facteurs premiers (entiers naturels plus grand que 1 qui n'ont pas de diviseur autre que 1 et lui-m^eme); ou m^emenon calculable: etant donne un enonce mathematique, 2 decider s'il est vrai ou faux. Oui, certaines fonctions ne sont pas calculables : il n'existe pas d'algorithme qui les calcul. De plus, il y a inniment plus de fonctions non calculables que de fonctions calculables! Il existe une innite de fonctions, et une innite de machines de Turing (d'algorithmes), mais le nombre de fonctions est inniment plus grand que le nombre de machines de Turing. Une question naturel est : si les machines de Turing peuvent calculer si peu de fonc- tions, pourquoi ne pas calculer avec un autre modele mathematique? En realite, les machines de Turing ne sont pas le seul objet mathematique permettant de decrire des algorithmes. De tels modeles sont appelesmodeles de calcul eectifs, oueectifsigni- e approximativement en accord avec le monde reel. Il est cependant magnique de constater que tous les modeles de calcul proposes jusqu'a present sont equivalents! Deux modeles sont equivalents s'ils peuvent calculer exactement le m^eme ensemble de fonctions. Rappelons nous bien : soitFl'ensemble de toutes les fonctions, les machines de Turing ne peuvent pas calculer toutes les fonctions de l'ensembleF, mais seulement un sous-ensembleC.La croyance (repandue) selon laquelle tout autre modele de calcul eectif que l'on pourrait imaginer sera egalement capable de calcu- ler toutes les fonctions de l'ensembleCet aucune autre est appeleethese de Church-Turing, etCest appele l'ensemble desfonctions calculables. L'une des questions les plus fondamentales de la science informatique est la suivante : pourquoi une fonction est-elle calculable ou non calculable? Un point interessant est l'existence de machines de Turinguniverselles. Une machine de Turing universelleUest une machine capable desimulertout autre machine de Turing. Qu'est-ce que cela signie? SoitMune machine de Turing quelconque etxune entree, la sortie deMsur l'entreexest noteeM(x). Une machineUest universelle si l'on peut ecrire une entreeysur le ruban telle que le calcul deUsurydonneM(x)en sortie. Uetyne sont pas tres compliques a construire :Ma une description nie (principale- ment sa table d'actions), donc cette description peut ^etre ecrite sur le ruban, elle utilisera ncellules; et sur d'autres cellules vides, on peut ecrirex. Maintenant,Ua toute l'infor- mation qui denitM(x)sur le ruban, et il est possible1de construire une telle machineU quilitl'entreexsur le ruban, ensuitelitla table d'action deMsur lesncellules dediees du ruban, et ensuite realise surxce que la machineMaurait realise si elle avait ete executee sur un ruban contenantx. Une telle machineUest un peu delicate a construire, mais pas excessivement. De nos jours, un ruban est appeledisque dur, la table d'action deMecrite sur le ruban est unprogramme, etUest unordinateur! Une machine de Turing universelle entierement mecanique a ete realisee en Lego. http://www.dailymotion.com/video/xrmfie/ http://rubens.ens-lyon.fr/ Par consequent, ce tas de Lego est capable de calculer l'ensemble des fonctions calculables C: il a exactement la m^emepuissance de calculque votre ordinateur ou votre telephone portable! En comparaison avec un ordinateur moderne qui realise une instruction toutes les nano-secondes (0.000000001 secondes), cette machine en Lego realise une instruction toutes les 100 secondes.Elle peut faire ce qu'un ordinateur moderne peut faire,

mais pour realiser ce que ce dernier eectue en 1 seconde, il lui faut 3168 ans1. Remarquons que l'existence de fonctions non calculables implique que pour d'autres problemes

(encore une fois il y en a enormement, inniement plus que des calculales), m^eme avec toute l'information

qui denit la question, il n'existe pas de machine de Turing qui calcule le resultat. 3

295 jours 9 heures 46 minutes et 40 secondes

2. Quoi qu'il en soit, l'important est

qu'elle en soit capable, n'est-ce pas? C'est le coeur de lacalculabilite. Les ordinateurs sont chaque annee plus rapides, et leur vitesse continue d'augmenter. Cependant, ils restent restreints a l'ensemble des fonctions calculables,C. Ils peuvent calculer les fonctions de l'ensembleCtoujours plus vite, mais ne peuvent pas s'echapper deC: leurexpressivitereste la m^eme. L'etude de cette expressivite, du sens de cette puissance de calcul, s'appelle latheorie de la calculabilite. Vous pouvez parfois entendre que nous sommes aujourd'hui capables de calculer des choses qui etaient impossible a calculer les annees passees, que les ordinateurs sont plus puissants aujourd'hui qu'hier. Ces phrases doivent ^etre precisees. En realite, ces calculs etaient simplement trop longs a realiser les annees passees (par exemple, il aurait fallut

100 ans si vous les aviez executes sur un ordinateur en l'an 2000), mais aujourd'hui vous

pouvez les calculer en un temps raisonnable (par exemple 100 secondes) ce qui permet d'obtenir eectivement le resultat. Un exemple interessant est le jeu des echecs : il est possible aujourd'hui, et il a toujours ete possible, d'ecrire un algorithme qui vous indique coup apres coup la meilleure action possible, mais les ordinateurs actuels sont bien trop lents pour executer un tel algorithme jusqu'au bout... Neanmoins, un jour nous serons capables de realiser ce calcul en un temps raisonnable, et ensuite jouer aux echecs avec un ordinateur deviendra denitivement ennuyant car nous serons s^urs et certains de perdre chaque partie

3. Laissez moi repeter qu'un tel algorithme existe deja et est facile a

implementer sur un ordinateur, les ordinateurs sont simplement trop lents pour realiser les calculs en un temps raisonnable. Latheorie de la calculabilites'interesse a des verites mathematiques qui sont independantes du temps de calcul : la question n'est pas de savoir si quelque chose sera faisable dans 10 ou 20 ans, mais plut^ot si quelque chose est fondamentalement faisable ou non, fondamentalement vrai ou faux.

2 Machines de Turing

Pour montrer qu'une fonction est calculable ou qu'un langage est decidable (distinc- tion discutee en 2.2) il faut donner un algorithme. Pour montrer qu'une fonction n'est pas calculable ou qu'un langage est indecibable, il faut d'abord denir l'ensemble des algorithmes (car cela denit l'ensemble de ce qui est calculable/decibable). L'inter^et des machines de Turing est qu'elles denissent les algorithmes de facon intuitive et simple! Imaginez devoir denir mathematiquement votre langage de programmation prefere dans ses moindres details...

Idee du calculateur humain devant sa feuille :

fe uillesd ecoupeesen cases : ruban ; cr ayonp osesur une case : t ^etede lecture/ ecriture,d eplacement;

l'o perateurdisp osed'une m emoire nie(son cerv eau): etats.2. Ce nombre est en realite completement faux, parce qu'une instruction de machine de Turing est

dierente d'une instruction d'un ordinateur moderne. Neanmoins, il est la pour souligner le fait que cette

machine de Turing en Lego est tres precisement equivalente a un ordinateur moderne

3. Je mens un peu. En realite, puisque nous n'avons encore jamais calcule toutes les actions possibles

aux echecs, nous ne savons pas si ce sont les blancs ou les noirs qui ont une strategie gagnante, ou si

nous arriverions a un match nul avec deux joueurs parfaits... 4

2.1 Denitions

Denition 1.Unemachine de Turing(MT) deterministe est un 7-uplet

M= (Q;;;;q0;B;qF)ou

|Qest unensemble d'etatsni;|est l'alphabet d'entree;|est l'alphabet de ruban(il contient tous les symboles qui peuvent appara^tre sur le ruban. En particulier

car l'entree est initialement ecrite sur le ruban. On supposera queQ\ =;pour qu'il n'y ait pas de confusion entre etats et symboles du ruban);

|est unefonction de transitiondecrite ci-apres;|q02Qest l'etat initial;|B2nest unsymbole blancspecial (ne fait pas partie de l'alphabetd'entree);

|qF2Qest l'etat nal.La fonction de transitionest une application (partielle) de l'ensemble (Qn fqFg) dans l'ensembleQ fL;Rg. L'application est partielle : elle peut ^etre indenie pour certains arguments, auquel cas la machine n'a pas de mouvement suivant et s'arr^ete. En particulier, il n'y a pas de transition depuis l'etat nalqF. Une transition (q;a) = (p;b;L) signie que dans l'etatqet en lisant le symbole de rubana, la machine passe dans l'etat p, remplaceaparbsur le ruban, et deplace la t^ete de lecture/ecriture d'une cellule sur la gauche (LpourleftetRpourright). Initialement, le mot d'entree estecrit sur le ruban et toutes les autres cellules contiennent le symbole blancB. La machine est dans l'etatq0, et la t^ete de lecture/ecriture est posi-

tionnee sur la lettre la plus a gauche de l'entree. Il y a trois possibilites :|acceptationsi au cours des transitions la machine entre dans l'etat nalqF(etdonc s'arr^ete),

|rejetsi au cours des transitions la machine s'arr^ete dans un etat non nal (s'iln'y a pas de mouvement suivant a realiser),

|rejetsi la machine ne s'arr^ete jamais.Denition 2.Unedescription instantanee(DI) d'une MT decrit sa conguration

courante. C'est un mot uqav2(fg [(n fBg))Q(fg [(n fBg) avecq2Ql'etat courant,u;v2le contenu du ruban a gauche et a droite de la t^ete, respectivement, jusqu'au dernier symbole non blanc, eta2le symbole de ruban actuellement sous la t^ete. Denition 3.Unmouvement, unetransition, undeplacementde la MT a partir de la DI=uqavvers la DI suivantesera note`. Plus precisement : 1.

Si (q;a) = (p;b;L),

si u=alors=pBbv(potentiellement en supprimant lesBa la n debv), 5 |si u=u0cavecc2alors=u0pcbv(potentiellement en supprimant lesBa la n debv). 2.

Si (q;a) = (p;b;R),

si v=alors=ubpB(potentiellement en supprimant lesBau debut deub), si v6=alors=ubpv(potentiellement en supprimant lesBau debut deub). 3. Si (q;a)est indeni alors aucun mouvement n'est possible depuis, etest une

DI d'arr^et. Siq=qFalorsest uneDI acceptante.

Notation 4.Notre modele de MT estdeterministe, ce qui signie que pour toutil y a au plus untel que`. Nous noterons si la MT changeenen n'importe quel nombre d'etapes (0 inclus, auquel cas=), `+si la MT changeenen au moins une etape, et `isi la MT changeenen exactementietapes. Pour toutw2nous pouvons denir la DI correspondante w=q0w;siw6= q

0Bsiw=:

2.2 Decider et calculerDenition 5.Le langagereconnu(ouaccepte) par la MTMest

L(M) =fwjw2etw`uqFvavecu;v2gDenition 6.Un langage estrecursivement enumerable(r.e.) s'il est reconnu parune machine de Turing. Un langage estrecursif, oudecibable, s'il est reconnu parune machine de Turing qui s'arr^ete sur toutes les entrees.

Attention a la dierence! Bien entendu, tout langage recursif est egalement r.e. Notation 7.Leresultatdu calcul de la MTMsur l'entreewsera note

M(w) =8

:uvsiw`uqFvavecu;v2 uavsiw`uqavavecu;v2et(q;a)non deniy

"si l'execution ne termine pas:ypotentiellement en supprimant lesBa la n deav.Denition 8.Une fonctionf: !estcalculableourecursivesi et seulementsi il existe une MTMtelle que pour toutw2:f(w) =M(w).Remarque 9.D ecider(un langage) est equivalent acalculer (une f onction).

(Decider un langageLrevient a calculer safonction caracteristique f

L: ! f0;1g

w7!1siw2L

0sinon:

6 )Calculer une fonctionfrevient a decider le langage f(x;y)jy=f(x)g: Nous n'etablirons pas de distinction tres nette entre calculer et decider. Da nsla vraie v ieon dira plut^ otcalculer (plus parlan t). Da nsle monde des math ematiqueson dira plut^ otd ecider(plus minimaliste, et s'applique aux proprietes). R ecursifest synon ymede calculable et d ecidable. Remarque 10.Le termerecursivement enumerable(denition 6) vient du fait qu'il est possible d'ecrire (pour ces langages) une MT qui va, a partir d'une entree vide, enumerer tous les mots du langage, un a un et sans en oublier aucun (dans n'importe quel ordre, possiblement en repetant plusieurs fois certains mots). C'est-a-dire que nous au- rons unetat special d'enumerationqe(quand on entre dans cet etat c'est qu'on enumere le mot present sur le ruban, par convention a la droite de la t^ete de lecture/ecriture) tel que : pour tout motw2L, il existe une etapettelle que`tw0qew.

Exemple 11.Le langage suivant est recursif :

fw2 fa;bgjwest un palindromeg donc il existe une machineMpalindromequi le decide (repond oui/non sur toute entree).

2.3 Proprietes de cl^oture

Theoreme 12.Les proprietes suivantes sont vraies : 1. la famil ledes langages r ecursifsest close p arc omplementation; 2. les famil lesdes langages r ecursifset r ecursivement enumerablessont closes p ar union et intersection; 3. Un langage Lest recursif si et seulement siLetnLsont recursivement enumerables.

Idees de demonstration.

1. On v eutprouv erLrecursif implique nLrecursif. SoitMla machine dont le langage estL(M) =Let qui s'arr^ete toujours, nous allons construire une nouvelle machineM0dont le langage estL(M0) = nLet qui s'arr^ete toujours. Pour cela, on ajoute un puits global qui sera notre nouvel etat nal. Ainsi, la nouvelle machine s'arr^ete dans cet etat nal a chaque fois queMs'arr^etait sur un etat non nal (w =2L(M))w2L(M0)). De plus, chaque fois queMs'arr^etait dans l'etat nal,M0va dans un nouvel etat non nal a partir duquel aucune transition n'est possible (w2L(M))w =2L(M0)). 2. In tersection.Soien tL1=L(M1) etL2=L(M2). On veut construire une machine M

0dont le langage estL(M0) =L1\L2. Pour cela, sur une entreewla machine

M

0simulera (pour cela il sut de modier l'etat nal des machines simulees) :

|M1sur l'entreew(on sait que le calcul termine), pu isM2sur l'entreew(on sait que le calcul termine), 7 se souviendra du resultat de chaque simulation (arr^et dans l'etat nal ou non), et va dans l'etat nal si et seulement siM1etM2acceptentw(sinonM0va dans un nouvel etat non nal a partir duquel aucune transition n'est possible). Pour les langages r.e. on etudie en plus les cas ou les machinesM1etM2ne s'arr^ete pas. 3. Le sens )est direct. Pour(, on simule en parallele les deux machines qui recon- naissentLetLn(mais ne s'arr^ete pas toujours). Puisque soit l'une soit l'autrequotesdbs_dbs45.pdfusesText_45

[PDF] indemnité prof principal 2017

[PDF] isoe prof principal

[PDF] hsa prof

[PDF] indemnite tuteur stagiaire education nationale

[PDF] prime prof principal contractuel

[PDF] evaluation anglais 6ème description physique

[PDF] indemnité prof principal agrégé terminale

[PDF] indemnités vacances éducation nationale

[PDF] enseignant contractuel vacances d'été

[PDF] entretien d'embauche la meilleure défense c'est d'être préparé

[PDF] cdi prof contractuel

[PDF] planification annuelle français secondaire 1

[PDF] planification annuelle français secondaire 3

[PDF] planification français secondaire 4

[PDF] dernier pays indépendant dans le monde