Comments on Que ferait-on d'un ordinateur infiniment rapide ?

Je ne sais pas si tu as déjà entendu parler de ça…
<URL:http://arxiv.org/abs/gr-qc/0104023v2/ >

Sans doute que oui, mais bon, c'est à la base de The Planck Dive de Greg Egan
<URL: http://gregegan.customer.netspace.net.au/PLANCK/Complete/Planck.html/ >

Il y a cela qui est aussi rigolo
<URL:http://arxiv.org/abs/quant-ph/0401062/ >

Et n'oublions pas celui là aussi:

<URL: http://arxiv.org/abs/quant-ph/0502072/ >

@f3t: Coquille repérée, "Quand à ma phrase" -> "Quant à ma phrase"

Bonjour, professeur !
Fonctions lisses, vouliez-vous dire C\infty… difféomorphismes ?
Ce dernier mot devrait d'ailleurs être au bestiaire, avec "modulo", "trivial", "à isomorphisme près", et "epsilonesque" (entre autres).
Enfin, la "Fin du Monde"(tm) n'ayant pas eu lieu fin 2012, vous gagnez tous : chanceux !

@frankie : cette question d'échelle est probablement une fausse question, parce que les équations de Navier-Stokes supposent des fonctions lisses (Cinfinies). Quand à ma phrase sur les supercalculateurs, vous avez sûrement mal lu, vu que c'est une question, et que la remplacer par sa négation revient juste à échanger les réponses oui et non…

@f3et qui écrit entre autres :
"Déjà,l'histoire du sens physique pour Navier-Stokes est rendu peu pertinent par le fait que ces équations décrivent le comportement de fluides continus, alors que les vrais sont formés de molécules… Et du coup, on peut résoudre réellement les deux questions à 1 million de dollars : 1) la solution est elle stable ? 2) Correspond-elle au comportement des fluides réels? Mais cela dit, je suis surpris que la discussion ne démarre pas sur l'application réelle (je veux dire ici et maintenant) des supercalculateurs fort chers qu'on a aujourd'hui : vous croyez vraiment que s'ils devenaient de puissance infinie, ça ne changerait rien en pratique d'un point de vue social ? "

Un modèle physique est pertinent s'il représente une réalité mesurable avec une précision suffisante. Il possède un domaine de validité. A ce jour, aucun ne possède de domaine de validité illimité. NS pas plus que les autres. Encore faut-il que l'on sache le définir…
Ce que j'évoquais, c'est la possibilité qu'à des échelles suffisamment petites dans la solution mathématique, ou numérique si vous préférez, et donc physiquement non pertinentes pour la raison que vous indiquez, ou d'autres , mais ce n'est pas essentiel d'entrer dans les détails, interviennent des phénomènes qui aient des répercussions à des échelles macroscopiques. Lisez U. Frisch, par exemple, mais je n'ai pas envie de donner des détails pour une multitude de raisons que vous comprendrez aisément.
je serais en accord avec votre phrase sur les supercalculateurs à condition que vous remplaciez "ça ne changerait rien" par "ça changerait quelque chose", ce qui modifie le sens de cette première du tout au tout. Ou ai-je mal lu ?

@ Antoine Levitt :

J'aimerais savoir ce que vous appelez un vrai physicien*…

Sur la suite de vos propos, elle sonne bien. Elle mériterait une large continuation.
Sauf que je ne saisis pas très bien la logique de votre "échelle" qui mélange allègrement EDP (pas de théorie unifiée) et EDO (no comment), théories classiques et quantiques -alors que les théories semi-classiques sont d'une grande utilité-, et qui semblent laisser de côté des équations très pratiquées (celles de MHD, ou de Hartree-Fock, citées là uniquement pour débuter une liste assez interminable). Mais cette échelle n'est pas indispensable, je suppose, pour comprendre la teneur de votre interrogation.
Pour ma part, j'aurais plutôt été emballé du côté de la QCD, par exemple, la QED étant le modèle fétiche des physiciens car ayant donné lieu à la mesure la plus précise jamais effectuée…

*Là comme ailleurs, beaucoup postulent et peu sont agréés…

Les simulations au niveau arôme avec un pas de temps arbitrairement fin, ça va bien aider en physique.

Et tout ce qui est apprentissage à base de "génère moi la plus petite machine de turing travaillant en temps raisonnable et résolvant mon problème" ça doit dépoter.

A mon avis, dans les 3 mois qui suivront la sortie de la machine, la science aura fait un bond absolument incalculable.

Déjà,l'histoire du sens physique pour Navier-Stokes est rendu peu pertinent par le fait que ces équations décrivent le comportement de fluides continus, alors que les vrais sont formés de molécules… Et du coup, on peut résoudre réellement les deux questions à 1 million de dollars : 1) la solution est elle stable ? 2) Correspond-elle au comportement des fluides réels? Mais cela dit, je suis surpris que la discussion ne démarre pas sur l'application réelle (je veux dire ici et maintenant) des supercalculateurs fort chers qu'on a aujourd'hui : vous croyez vraiment que s'ils devenaient de puissance infinie, ça ne changerait rien en pratique d'un point de vue social ? Alors, pourquoi dépenser tous ces sous ? Variante : la plupart des problèmes en intelligence artificielle sont modélisés par des parcours dans des graphes ou des arbres ; il parait peu probable qu'avec une puissance informatique infinie (et pas juste 10^20 fois plus grande que la puissance actuelle), une fois qu'ils sont tous résolus, on ne puisse néanmoins pas construire une machine véritablement "intelligente", et alors, à nous la Singularité… Dernier exemple : on en sait probablement assez en génétique et en chimie pour pouvoir (en théorie, muni d'un ordinateur assez rapide) simuler le comportement d'une séquence d'ADN quelconque ; là encore, c'est facile d'imaginer les applications…

Ca serait intéressant de demander ça à un vrai physicien, ce qu'on fait si on a puissance de calcul illimitée. A quel étage de l'échelle (navier-stokes -> boltzman -> newton -> schrödinger -> QED -> ?) on se place pour avoir un truc qui soit précis et qu'on ait en même temps un modèle qui a du sens ? (par exemple, je ne sais pas si on peut avoir une vraie formulation bien propre de la QED)

La dérivation physique des équations de NV (et de bien d'autres) s'appuie sur des hypothèses thermodynamiques qui font que si l'on connaissait exactement une solution, on ne saurait décider à des échelles suffisamment petites si elle correspond à quelque chose*.
Si la solution est assez lisse, on fait comme si cela n'avait pas d'importance. Mais si la solution est trop singulière dans un sens que je ne précise pas, sa signification physique a toutes les chances de disparaître.

D'un point de vue mathématique, se posent, j'imagine, le problème de convergence de la solution numérique, de la validité des équations de NV, en particulier du cadre d'analyse fonctionnelle le plus adéquat pour traiter un (tous les ?) problème(s) donné(s)… Un ordinateur hyperarithmétique pourrait-t-il répondre à toutes ces interrogations, ou parties ?

*En laissant de côté le modèle physique impliqué à la base, qui fait intervenir un certain nombre de quantités invariantes, liées à des symétries, et de degrés de liberté…

@ Ruxor (2013-01-24T15:09:00+0100)
qui répondait à M :
@M: Numériquement, oui, bien sûr, avec une précision aussi grande qu'on veut (et même, dans un certain sens, avec une précision infinie). Mais comme je le souligne, le problème pratique avec ce genre d'équation n'est pas juste de les résoudre numériquement, mais aussi d'avoir une mesure expérimentale des conditions initiales.

Et de savoir dans quel régime l'on se trouve (turbulent, laminaire, etc), de façon à pouvoir faire émerger un paramètre de temps de fiabilité de la solution en fonction de la précision des CI.
Dans la cas de NS, on a le nombre de Reynolds.

NB : le problème de la validité des équations de NS n'est pas encore résolu.

Et donc, pour revenir sur ta dernière phrase, qu'est-ce que ça implique d'être un automate fini (infiniment rapide) ?

En écrivant la question, je crois apercevoir la réponse : si la mémoire est finie, la taille des données du problème est finie et toutes les questions de limites quand cette taille tend vers l'infini (et donc les classes de complexité) sont évacuées… Est-ce correct ?

* Infiniment rapide *et* avec mémoire infinie, non ?
* Effectivement, peut-être bien que le facteur le plus limitant n'est pas du tout la rapidité de calcul ou la quantité de mémoire pour l'essentiel des utilisations pratiques. Question intéressante en tout cas.

Il me vient une question : la taille de la mémoire n'intervient-elle pas de façon déterminante pour une telle machine ? Par exemple, pour reprendre la question de M, je suppose qu'il est possible de résoudre toutes les équations non linéaires avec une précision arbitraire en utilisant les algorithmes qui existent déjà, et en discrétisant de manière arbitrairement fine. Mais cela suppose une mémoire également infinie.

D'où ma question : quelle est l'influence de la taille de la mémoire sur une machine infiniment rapide ?

Mes réflexions naïves me soufflent que cette influence est réelle (en considérant les cas extrêmes). La question est donc plutôt de savoir quelle serait l'influence d'une limitation de l'ordre de quelques téraoctets, par rapport à une taille infinie.

> Les conséquences d'une telle découverte, à savoir qu'on pourrait résoudre
> efficacement toute une classe de problèmes (PH) qui semblent a priori
> impossibles à mener « en pratique » (c'est-à-dire, en un temps raisonnable)

En fait on sait resoudre en pratique tout un tas de problemes NP-difficiles. Par exemple il n'y a plus de TSP (pur) a l'echelle humaine qui resiste aux methodes de resolution actuelles ; qui a vraiment besoin d'un TSP de plus de 30 000 villes ?

Aussi nous sommes aussi progressivement passes de methodes ad-hoc et probleme specifiques a des methodes generales comme le MILP et le SMT dans lesquelles tu decris ton probleme sous forme d'equations et le moteur le resout.

Et puis il y a le miracle divin : les moteurs MILP et SMT doublent de performance tous les ans (a machine fixe). Donc notre capacite a resoudre ces problemes croit de facon exponentielle avec le temps. En fait c'est vrai pour toute l'informatique au cause des machines mais avec les problemes NP c'est vraiment vrai : tous les ans on te demande de "complexifier" le probleme NP pour faire remonter le temps de calcul vers les 10 minutes. Si bien que dans la pratique la resolution de problemes NP se heurte a des difficultes "techniques" comme l'expressivite des langages, la certification, ou encore les bases de donnees, les interfaces graphiques et le web.

Et aussi des difficultes de formation ! Plus le temps passe, plus la resolution pratique de problemes NP s'apparente a un travail de physicien : il faut connaitre la realite du terrain (p. ex. le transport routier), negliger tout un tas de facteurs dont on sait qu'ils affectent le probleme seulement au second ordre, transformer en equations qui ont une forme sympathique pour le moteur d'optimisation, resoudre, valider sur le terrain que l'approximation est suffisamment precise, mettre en place le resultat dans un systeme reel complexe et recommencer tous les ans.

Je ne dis pas que tous les problemes NP sont resolus, loin de la, et un ordinateur infiniment rapide serait indubitablement apprecie. Mais cela ne reglerait certainement pas tous nos soucis.

C'est une perspective effrayante car si le chiffrement devient inutile pour dissimuler des informations il faudra recourir à des méthodes psychologiques -et là, on basculerait vraiment du droit dans le tordu…

Pour parler de physique, est-ce que tu penses que ce genre de machine aiderait a resoudre des equations non-lineaires (tel que Navier Stokes)? Dans ce cas ca aiderait grandement, vue que tout ce qui est vraiment interessant dans la nature est non-lineaire…