Maths et informatique theorique

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 :

la classe P des problèmes que l'on sait résoudre en un temps polynomial, c'est à dire que le temps de calcul est borné pat un polynôme de la taille des données, par exemple n¹⁵. Ces problèmes sont dit "faciles".
Inversement, la classe EXP des problèmes dont on peut prouver qu'il n'existe pas d'algorithme polynomial pour les résoudre : ces problèmes dits "difficiles" ont un temps de calcul au moins exponentiel, par exemple 3ⁿ.
Entre les deux, se trouve la classe des problèmes dont on ne sait pas si la résolution prendra un temps polynomial ou exponentiel, mais dont on peut vérifier une solution en un temps polynomial : si on dispose d'une solution possible, il existe un algorithme qui montre en un temps polynomial si c'est une vraie solution. Par exemple on ne connaït pas le temps de calcul minimal théorique pour factoriser un nombre N de n chiffres en produits de nombres premiers, mais il est très facile, lorsqu'on dispose de plusieurs nombres premiers, de montrer si leur produit vaut N ou pas. La plupart des problèmes pratiques intéressants appartiennent à cette classe, dite classe NP (pour non déterministe ET polynomial)

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.

Sciences

> La suite : la machine de Turing