Web log de Serge Boisse
On line depuis 1992 !
Si cette page vous a plu, Copiez son adresse et partagez-la !
http://sboisse.free.fr/science/maths/info.php
Auteur: Serge Boisse
Date: Le 26/03/2023 à 17:03
Type: web/MOC
Tags: maths,informatique,théorie
pub: oui
commentaires: ouiL'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.
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 !
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.
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.
Commentaires (4) :
Page : [1]Le 20/02/2013 à 11h23
Le 17/01/2010 à 19h13
Le 06/08/2008 à 15h01
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)
Le 06/08/2008 à 13h50
Ajouter un commentaire (pas besoin de s'enregistrer)
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 bbcode et le html genre <br>, <a href=...>, <b>b etc. ne fonctionnent pas dans les commentaires. C'est voulu.