Journal d'un terrien

Web log de Serge Boisse

On line depuis 1992 !

Recherche personnalisée

Maths et informatique théorique

L'ordinateur est un merveilleux outil pour explorer l'univers mathématique. Mais ce merveilleux outil pose également de redoutables problèmes théoriques.

Alan Turing a montré que tout calcul informatique pouvait être réalisé par un dispositif  très simple mais néanmoins universel : la machine de Turing. Sa thèse, la thèse de Church-Turing,  Consiste à dire que tout calcul envisageable par l'esprit humain peut être réalisé par ordinateur, ou, ce qui revient au même, par une machine de Turing. Je pense que cette affirmation mérite d'être discutée.

Les limites du calcul

Turing a montré que certaines fonctions numériques n'étaient pas calculables : Si l'on accepte sa thèse, cela pose une limite à ce que peut accomplir l'esprit humain : il ne pourra jamais calculer une fonction non calculable (au moins pour certains de ses arguments).

Historiquement, la première fonction non calculable envisagée par Turing est la fonction d'arrêt : Pour la définir, on imagine que l'on numérote en séquence (par exemple dans l'ordre lexicographique) tous les programmes qui peuvent s'écrire dans un langage informatique donnée (ou avec une machine de Turing). La fonction d'arrêt prend en argument le numéro d'un programme et vaut un si ce programme s'arrête au bout d'un temps fini (ou si le programme n'est pas interprétable par l'ordinateur parce qu'il est incorrect syntaxiquement par exemple),  et zéro sinon (un programme qui boucle indéfiniment).

S'il existait  un programme qui calcule la fonction d'arrêt, ce serait bien pratique, car on pourrait répondre mécaniquement à toutes les questions ouvertes des mathématiques : il suffirait d'écrire un programme qui s'arrête s'il a trouvé une solution à la question, puis de donner son numéro en pâture à notre programme qui calcule la fonction d'arrêt : On saurait alors, sans exécuter le programme qui répond à la question, s'il s'arrêtera ou non, c'est à dire s'il existe une solution !

Turing a prouvé que la fonction d'arrêt n'est pas calculable : il n'existe aucun programme qui puisse calculer cette fonction. Ceci mit un terme à ce que l'on a appelé le dixième problème de Hilbert : Savoir s'il existe un processus mécanique qui puisse démontrer ou infirmer toutes les affirmations d'un système formel donné. Et la réponse est : NON, hélas !

Temps de calcul

Cependant, il existe évidemment de nombreuses fonctions calculables, et ces fonctions peuvent se programmer avec une machine de Turing. La question se pose alors de savoir quel est le temps de calcul de ces fonctions. On démontre qu'il existe des programmes qui, bien que s'arrêtant au bout d'un temps fini, prendront en fait tellement longtemps pour répondre que; même avec le plus puissant ordinateur envisageable (par exemple un ordinateur qui comprendrait autant de processeurs qu'il y a de protons dans l'univers, avec un temps de cycle égal au temps que met la lumière pour traverser un proton), le calcul prendrait des milliards de milliards d'années !

Plus concrètement, lorsqu'on se trouve en face d'un problème pratique, comme l'optimisation d'un réseau électrique, ou la recherche du coût minimal pour la fabrication d'un produit industriel, la question de savoir combien de temps cette optimisation va prendre est extrêmement importante. C'est le but de la théorie de la complexité de répondre à de telles questions : lorsque on se trouve en face d'un algorithme donné, quel est le temps minimal de calcul, en comment varie-t-il en fonction des données ?

En général, on classe les problèmes en trois classes :

Il se trouve que l'on ne sait pas si P=NP ou P≠NP. Ceci constitue la conjecture P-NP , l'une des plus importantes conjectures des mathématiques contemporaines. Si vous parvenez à prouver l'égalité ou l'inégalité, vous gagnez un million de dollars, offerts par la fondation Clay.

Ma petite contribution à la solution de ce problème consiste à concevoir une machine de Turing à accélération, c'est à dire une machine qui apprend au cours de son propre fonctionnement à aller de plus en plus vite. Si cette machine existe, permet-elle de résoudre tous les problèmes NP en un temps polynomial ? Dans ce cas on aurait P=NP.

Le castor affairé

Enfin le concept de machine de Turing n'est pas sans lien avec la théorie des nombres . Je me suis intéressé à la fonction de Rado, qui est une fonction N->N notée sigma(n), et définie ainsi :

sigma(n) = le plus grand entier que peut produire une machine de Turing à n états avant de s'arrêter.

On appelle ces machines de turing les "castor affairés ", (busy beaver) car ce sont les machines qui calculent le plus de choses possibles avec un minimum de moyens.

Malheureusement, la fonction de Rado n'est pas calculable ; mais pour des petits arguments, on peut en trouver des bornes inférieures qui sont probablement les bonnes valeurs de la fonction. C'est une recherche très ludique et cela vaut le coup d'un jeter un oeil.

Le lien avec la théorie des nombres vient de ce que les nombres sigma(n) sont en quelque sorte les nombres "anti aléatoires" par excellence :  ces nombres sont formidablement grands, mais pourtant on peut les définir et les calculer avec de touts petits programmes.
 



> La suite : la machine de Turing

Journal d'un terrien

Commentaires (4) :

Page : [1] 

pol pot
Le 20/02/2013 à 11h23
ce n'est pas la these de turing mais celle de Church^^gps7
B.
Le 17/01/2010 à 19h13
Juste une petite remarque : il y a bien plus de 3 classes de complexité ! Les classes "plus petites" que P, NP et EXP sont légion (mais contenues dans EXP), mais surtout, il existe des fonctions calculables bien au delà de EXP ! Il y a par exemple des fonctions dans 2-EXP (doublement exponentielle), ou dans la classe ELEM (pour élémentaire, à savoir que la complexité est une tour d'exponentielle). L'existence de fonctions de telles complexités est assuré par le théorème de hiérarchie en temps, cf Wikipedia:Time_hierarchy_theorem.
Serge Boisse
Le 06/08/2008 à 15h01
Bonjour joel,

En effet ma classification porte sur les fonctions entières calculables uniquement.

La fonction sigma(n) est une fonction non calculable (car elle croît plus vite que toute fonction calculable) et donc elle ne rentre pas dans cette classification. Cependant bien que sigma(n) soit en théorie non calculable (c'est à dire qu'il existe des valeurs de n pour laquelle on ne sait pas la calculer), on peut en pratique la calculer pour de très petites valeurs de n (jusqu'à 6, semble-t-il), et il est clair que le temps de calcul croît plus vite que n'importe quelle polynôme. La fonction partielle sigma(n) réduite aux seules valeurs calculables serait donc dans la classe EXP, à ceci prêt que ce n'est plus une fonction entière (c'est à dire définie sur N)
joel
Le 06/08/2008 à 13h50
Vous dites que les problèmes peuvent être rangés dans 3 classes, P, NP et EXP. Mais est-ce que ces 3 classes couvrent tous les problèmes possibles ? A mon avis non, sinon ou rangeriez vous la fonction Sigma(n) du castor affairé ?


Ajouter un commentaire (pas besoin de s'enregistrer)

Pseudo :
Message :


image de protection
En cliquant sur le bouton "Envoyer" vous acceptez les conditions suivantes : Ne pas poster de message injurieux, obscène ou contraire à la loi, ni de liens vers de tels sites. Respecter la "netiquette", ne pas usurper le pseudo d'une autre personne, respecter les posts faits par les autres. L'auteur du site se réserve le droit de supprimer un ou plusieurs posts à tout moment. Merci !
Ah oui : le html genre <br>, <a href=...>, <b>b etc. ne fonctionne pas dans les commentaires. C'est voulu.
< Retour en haut de la page