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 n15. 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 3n.
- 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)
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
- Intro
- Astronomie
- Cosmologie
- Maths
- Intro
- Histoires de nombres
- Géométrie
- Fondements des mathématiques
- La création des formes
- Maths et informatique théorique
- Le théorème du Libre-Arbitre
- corruption et dillemme du prisonnier
- Cosmo maths !
- Physique
- Psychologie
- Biologie
- Pseudo Sciences
Jeu de briques
Snake
Pacman
Bubble