[PDF] [PDF] Calculabilité Les fonctions peuvent être simples :

View - Download [PDF] Calculabilité

Previous PDF

Next PDF

Calculabilite

IKevinPerrot{ Aix Marseille Universite { printemps 2016 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|Co njectured'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. Co njecturede 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. Co njecturede 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

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

References

[1] Jar kkoKari. Automata and formal languages. University of Turku, 2013. course notes available athttp://users.utu.fi/jkari/. [2] Mic haelSipser. Introduction to the theory of computation. Course Technology, 2006.

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 calculez 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. 2 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, 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, oueectifsignie 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 fonc- tions. 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 a 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 toutes1. 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 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 peur faire, mais pour realiser ce que ce dernier eectue en 1 seconde, il lui faut 3168 ans

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 realises 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 calculees 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'alphabet d'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;X) = (p;Y;L) signie que dans l'etatqet en lisant le symbole de rubanX, la machine passe dans l'etat p, remplaceXparYsur le ruban, et deplace la t^ete de lecture/ecriture d'une cellule sur la gauche (LpourleftetRpourright). Initialement, le mot d'entree est ecrit 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(et donc s'arr^ete), |rejetsi au cours des transitions la machine s'arr^ete dans un etat non nal (s'il n'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 desBa la n debv), si u=u0cavecc2alors=u0pcbv(potentiellement en supprimant desB a la n debv). 2.

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

5 |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 calculer

Denition 5.Le langagereconnu(ouaccepte) par la MTMest

L(M) =fwjw2etw`uqFvavecu;v2g

Denition 6.Un langage estrecursivement enumerable(r.e.) s'il est reconnu par une machine de Turing. Un langage estrecursif, oudecibable, s'il est reconnu par une machine de Turing qui s'arr^ete sur toute 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)indeniy "si l'execution ne termine pas: ypotentiellement en supprimant desBa la n deav. Denition 8.Une fonctionf: !estcalculableourecursivesi et seulement si 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:

(Calculer une fonctionfrevient a decider le langage f(x;y)jy=f(x)g

Remarque 10.

6 |Il existe une bije ctionentr eetN.

Il existe une bije ctionentr eetN.

Il existe une bijection entreNNetN,

et donc egalement entreNnetNpour toutn2N. Par consequent, lorsque nous parlons de fonctions calculables, nous pouvons restreindre nos considerations auxfonctions deNdansN. Nous n'etablirons pas de distinction tres nette entre calculer et decider. Dan sla vraie vi eon dira plut^ otcalculer (plus parlan t). Dan sle monde des math ematiqueson dira plut^ otd ecider(plus minimaliste, et s'applique aux proprietes). R ecursifest synon ymede calculable et d ecidable. Remarque 11.Le termerecursivement enumerablevient 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, possi- blement en repetant plusieurs fois certains mots). C'est-a-dire que nous aurons 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`tqew.

Exemple 12.Le langage suivant est recursif :

fw2 fa;bgjwest un palindromeg:

2.3 Proprietes de cl^oture

Theoreme 13.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 re- connaissentLet (mais ne s'arr^ete pas toujours). Puisque soit l'une soit l'autre acceptew, soit l'une soit l'autre entrera dans son etat nal, et nous pourrons alors : en trerdans notre etatnal si c'est la mac hinequi reconnait Lqui est entree dans son etat nal, en trerdans un nouv el etatnon nal apartir duquel aucune transition n'est possible si c'est la machine qui reconnait nLqui est entree dans son etat nal.2.4 Un peu d'histoire

Cantor (1845-1918)Hilbert (1862-1943)Godel (1906-1978)Church (1903-1995)Kleene (1909-1994)Turing (1912-1954)

A la toute n du XIXe siecle, Georg Cantor denit les fondements de la theorie des ensembles, dont l'usage systematique (c'est-a-dire qui est utilisee dans tous les do- maines) allait bouleverser les fondements de la logique mathematique. En 1900, pour f^eter le passage au XXe siecle, David Hilbert enonce 23 grands problemes ouverts, donc le suivant : les proprietes qui s'expriment en langage mathematique sont-elles toutes decidables? Si la reponse devait ^etre armatives, les proprietes mathematiques valides seraient des theoremes derivables mecaniquement de quelques axiomes dans un systeme formel. Autrement dit : on pourrait remplacer les mathematicienNEs par des machines surpuissantes! En 1931, Kurt Godel met un terme a cette interrogation : il existe des proprietes mathematiques indecidables (dans tous les systemes d'axiomes qui formalisent au moins l'arithmetique). Autrement dit : mathematicienNEs 1 - machines 0. Entre 1932 et 1936, Alsonso Church et Stephen Kleene proposent des modeles de calculs (le-calcul et les fonctions-recursives) qui semblent capturer la notion intuitive de fonctions cal- culables, mais il est un peu dicile de s'en convaincre... Notons tout de m^eme que le -calcul est extr^emement minimaliste, ce qui rend sa comprehension mathematique fort interessante : tout est capture en quelques lignes de denition! Independamment, en 1936, Alan Turing propose sa denition de machines. En 1937 il montre que la classe des fonc- tions-calculables est egale a la classe des fonctions programmables sur les machines de Turing. Les machines de Turing permettent de reformuler en termes intuitifs de calculs les resultats de Kurt Godel (qui etaient exprimes en termes de demonstration). Avec l'aide de Von Neumann (et d'autres), les premiers ordinateurs programmables verront le jour

quelques annees plus tard!La vie de Turing vaut le coup d'oeil (savez vous que le r^ole de Turing durant la seconde

guerre mondiale est reste secret d'Etat de nombreuses annees? e-penser(13') :https://www.youtube.com/watch?v=7dpFeXV_hqs8quotesdbs_dbs45.pdfusesText_45

[PDF] langage récursif

[PDF] épaisseur atmosphère saturne

[PDF] fonction primitive récursive exercice corrigé

[PDF] théorème de godel démonstration

[PDF] codage de godel

[PDF] théorème de gödel pdf

[PDF] arithmétique de robinson

[PDF] nombre de godel

[PDF] godel dieu

[PDF] théorème d'incomplétude pour les nuls

[PDF] incomplétude définition

[PDF] introduction ? la calculabilité pdf

[PDF] indemnité prof principal 2017

[PDF] isoe prof principal

[PDF] hsa prof