L'algorithme ultime

[invite6f044255]

il ya aussi un petit truc rigolo qui dit que l'histoire de l'univers est déjà écrite, mais on sait pas trop où. En fait il existe des nombres-univers, qui sont des réels transcendants (dont la partie décimale n'a pas de fin et n'est pas périodique). Pi en est un par exemple. Donc, si tu prends les Misérables de Victor Hugo, et qu'à chaque lettre tu fais correspondre un nombre (a=1,b=2,...,z=26), tu obtiendras une séquence de nombre gigantesque, séquence qui existe qqpart dans tout nombre univers à condition d'aller chercher loin, très loin, très très loin.... Ainsi de la même façon, l'histoire de l'univers est écrite dans Pi.
Qu'est-ce que vous dites de ça?
-----

[yat]

il ya aussi un petit truc rigolo qui dit que l'histoire de l'univers est déjà écrite, mais on sait pas trop où. En fait il existe des nombres-univers, qui sont des réels transcendants (dont la partie décimale n'a pas de fin et n'est pas périodique). Pi en est un par exemple. Donc, si tu prends les Misérables de Victor Hugo, et qu'à chaque lettre tu fais correspondre un nombre (a=1,b=2,...,z=26), tu obtiendras une séquence de nombre gigantesque, séquence qui existe qqpart dans tout nombre univers à condition d'aller chercher loin, très loin, très très loin.... Ainsi de la même façon, l'histoire de l'univers est écrite dans Pi.
Qu'est-ce que vous dites de ça?

C'est tout à fait vrai, mais c'est surtout un jeu de l'esprit... en effet il faudra autant d'informations pour trouver la séquence que les informations qu'elle contient... donc ça ne nous avance à rien, c'est simplement une manière de mélanger toutes les séquences de l'univers... Ce qu'il faut savoir, c'est qu'en plus de l'oeuvre de Hugo, il existera également dans tout nombre univers toutes les versions qu'on peut imaginer avec des fautes d'orthographe... et celui avec la fin alternative dans laquelle Valjean fait péter Paris avec une bombe atomique... et puis toute l'histoire de l'univers, mais dans laquelle Nicolas Sarkozy a des oreilles de lapin.
Et puis il y en a un autre nombre univers qui fait bien comprendre que c'est purement pour rigoler : il suffit d'écrire les entiers successifs à la suite : ça commence par 012345678910111213141516...
De la même manière que pi et les autres, ce nombre contient de par sa définition toutes les séquences possibles...

[invite3c88c1db]

Kurt Gödel a démontré en 1931 que quel que soit le système d'axiomes utilisé pour fonder une théorie, il existe des propositions que l'on sait vraies mais dont la vérité ne peut pas être démontrée dans le cadre du système. Donc quelle que soit la richesse d'un système d'axiomes elle ne peut égaler la complexité du contenu potentiel de la pensée.
Cette démonstration a jeté un froid chez les mathématiciens, si cela te permet de dormir tranquille.

[invite6c250b59]

Bonjour,

il suffit d'écrire les entiers successifs à la suite : ça commence par 012345678910111213141516...
De la même manière que pi et les autres, ce nombre contient de par sa définition toutes les séquences possibles...

Il me semble que ce chiffre contient en fait toutes les séquences de longueur fini (et donc aucun chiffre irrationnel). D'ailleurs, ça me semble un point clef de la question initiale: si un algorithme peut décrire l'univers, alors l'univers contient une somme finie d'information, et effectivement ton chiffre contient la "réponse". maintenant, si l'univers contient une infinité d'information alors 1- il n'y a pas d'algorithme pour le décrire, 2- il n'y a pas de déterminisme absolu (l'autre question qui anime ce fil).

G

[inviteeab9c5e9]

pourtant il existe des algos -finis- pour calculer Pi ... leur temps d'execution est infini, mais bon, on peut quand meme representer la valeur "exacte" de Pi par ces algos...

Et autre chose:
Chaque algo que l'on ecrit est une partie de cet utopique algo ultime
Comme deja ecrit + haut, on decrit tres bien certains phenomenes (comme le mouvement des astres, la balistique, etc...) et on obtient de vraies predictions du futur, et donc -j'insiste- on connait le resultat avant qu'il se produise dans la vraie vie... ceci pour dire que je ne pense pas que si L'Algo existait, il donnerait ces resultats en temps réel... (ce serait un vrai predicteur)

cependant j'admet tout a fait que cet algo ne puisse pas exister, a mon avis l'univers (ses habitant y compris) n'est pas deterministe... mais bon la science a encore de beaux jours devant elle n'est ce pas

[yat]

Il me semble que ce chiffre contient en fait toutes les séquences de longueur fini (et donc aucun chiffre irrationnel).

Tout à fait. Comme dans pi et tous les nombres univers de par leur définition. C'est simplement une séquence infinie dans laquelle on peut trouver toutes les séquences finies concevables. Pour l'irrationnalité, je vois pas trop ce que tu veux dire, il n'est question ici que de séquences de chiffres.

D'ailleurs, ça me semble un point clef de la question initiale: si un algorithme peut décrire l'univers, alors l'univers contient une somme finie d'information, et effectivement ton chiffre contient la "réponse". maintenant, si l'univers contient une infinité d'information alors 1- il n'y a pas d'algorithme pour le décrire, 2- il n'y a pas de déterminisme absolu (l'autre question qui anime ce fil).

En effet, tu soulèves là une question clé. Pourtant, il ne me semble pas qu'il y ait de réelle contradiction entre un nombre infini d'informations et la description par un algorithme, ou le déterminisme absolu (c'est un peu lié, non ?).
Le gros problème pour moi, c'est plutôt l'existence d'une durée minimale. Temps de Planck ou que sais-je, mais en tout cas un intervalle de temps qui correspondra à la durée d'une boucle dans notre algorithme magique.
Pour prendre un exemple, j'imagine un univers constitué d'une suite infinie de chiffres. A chaque "instant", chaque chiffre est modifié en fonction de ses deux chiffres voisins. Même si cet univers en lui-même est infini et contient un nombre infini d'informations, pour tout intervalle donné, et en conaissant l'état d'un intervalle (plus large) à l'instant t, on peut déterminer l'état de cet intervalle à l'instant t+1. Evidemment (et c'est peut-être ce que tu voulais dire), je ne vois pas comment on pourrait décrire l'ensemble de cet univers puisque ce n'est pas une séquence finie, mais le fait d'avoir une vitesse de propagation maximale de l'information nous permet de concevoir un algorithme qui prédit l'état d'une séquence. Dans notre univers à nous, cette vitesse de propagation maximale existe bien.

[JPL]

En effet, tu soulèves là une question clé. Pourtant, il ne me semble pas qu'il y ait de réelle contradiction entre un nombre infini d'informations et la description par un algorithme, ou le déterminisme absolu (c'est un peu lié, non ?).

Il y a une méthode dérivée de l'informatique sur laquelle les mathématiciens semblent s'accorder pour mesurer la quantité d'information contenue dans un ensemble de données : s'il y a des données redondantes (donc si la quantité d'information est inférieure au nombre de bits de l'ensemble de données), ces données peuvent être comprimées sans perte par un programme de compression classique. Donc plus un ensemble de données est compressible, moins il contient d'information. Inversement une suite de nombre réellement aléatoire n'est pas compressible parce que rien n'est prévisible ou calculable : tout bit est une information irremplaçable.
Le problème de Pi, par exemple, c'est que la suite des décimales est bien répartie de manière parfaitement aléatoire en apparence, mais qu'on connaît un algorithme assez court permettant de générer cette suite. Et l'existence de cet algorithme prouve bien que cette suite est compressible, sinon l'algorithme devrait être aussi long (longueur infinie) que le nombre lui-même.
Donc si l'univers contient une infinité d'informations il est impossible de le modéliser par un algorithme plus petit que l'univers lui-même.
Le paradoxe apparent provient du fait que dans notre esprit une information est, d'une certaine manière, un ensemble structuré. On a donc du mal à concevoir qu'il y a d'autant plus d'information qu'il y a plus d'aléatoire ; et que paradoxalement ce qui contient le plus d'information, c'est une suite de données dans un désordre parfait.

[yat]

Je ne vois pas le rapport. Il n'est de toutes façons pas question, dans le cadre d'un nombre infini de données, de toutes les calculer. Ca me semble évident.
Le sens de l'interrogation est donc plutôt de prévoir le comportement d'un sous-ensemble (un intervalle dans le cadre d'une suite infinie d'entiers).

[invite6f044255]

Il y a quelque chose qu je ne comprends pas: par exemple la fonction exp(x) (ou toute autre fonction) contient une infinité d'information dans le sens où elle est valable sur ]-oo,+oo[. pourtant avec notre langage mathematique, on arrive à réduire toutes ces infos en une petite expression.
On pourra objecter que le langage mathématique sur lequel on se base contient de l'information, mais il n'en contient pas une infinité...
Donc même si l'univers contient une infinité d'information (ce dont je doute...mais là n'est pas la question ), il me semble possible de décrire même une infinité d'info avec une expression réduite...

Il me veint un exemple:
Si je décris la trajectoire de la Terre, c'est valable a priori éternellement. Il se trouve que le système solaire a une fin, mais ça, je peux le prévoir et incorporer cette donnée (et les équations qui la décrivent) à ma description de la trajectoire de la Terre, non?

[yat]

Il y a quelque chose qu je ne comprends pas: par exemple la fonction exp(x) (ou toute autre fonction) contient une infinité d'information dans le sens où elle est valable sur ]-oo,+oo[. pourtant avec notre langage mathematique, on arrive à réduire toutes ces infos en une petite expression.

Pas du tout. C'est exactement ce que soulignait JPL. la fonction exp(x) ne contient pas une infinité d'informations, justement parce que n'importe quel élément peut être retrouvé selon un algorithme fini (pour résumer). C'est exactement la même chose que pour les décimales de pi, ou pour aller plus loin, un truc aussi simple que f(x)=2x. Mais JPL l'expliquait mieux que moi je pense.

Pour l'exemple de la trajectoire de la Terre, je suis d'accord avec toi sur le fond, mais il ne faut pas oublier que pour aller suffisamment loin dans le temps il faudra prendre en compte une sphère d'interaction suffisamment grande. Et donc pour prévoir ça éternellement il faudrait connaitre la l'état de l'intégralité de l'univers.

[invite6c250b59]

Bonjour et bon appétit à tous,

si l'univers contient une infinité d'information alors 1- il n'y a pas d'algorithme pour le décrire, 2- il n'y a pas de déterminisme absolu (l'autre question qui anime ce fil).

pourtant il existe des algos -finis- pour calculer Pi ... leur temps d'execution est infini, mais bon, on peut quand meme representer la valeur "exacte" de Pi par ces algos...

Absoluement, mais est-ce qu'on peut dire que Pi contient un nombre infini d'information? Comme le note JPL, l'opinion des matheux semble être que la quantité d'information d'une séquence dépend non pas du nombre de bits utilisés mais du nombre de bits après compression.

Ixi, ça répond aussi à ta question non? ha oui yat l'explique aussi.

Gamma

[invite6c250b59]

Il me semble que ce chiffre contient en fait toutes les séquences de longueur fini (et donc aucun chiffre irrationnel).

Tout à fait. Comme dans pi et tous les nombres univers de par leur définition. C'est simplement une séquence infinie dans laquelle on peut trouver toutes les séquences finies concevables. Pour l'irrationnalité, je vois pas trop ce que tu veux dire, il n'est question ici que de séquences de chiffres.

L'intérêt du chiffre que tu cites (012345678910111213141516...) c'est qu'il contient effectivement toutes les séquences de longueur finie possibles... à ma connaissance ça n'est pas démontré pour Pi par exemple (même si c'est la croyance générale).

Pour les chiffres irrationnels, ils sont de longueur infini sans répétition interne: donc tu ne peux trouver aucun chiffre irrationnel dans la séquence 012345678910111213141516... (on ne se lasse pas de l'écrire!)

G.

[invite6c250b59]

je ne pense pas que si L'Algo existait, il donnerait ces resultats en temps réel... (ce serait un vrai predicteur)

A voir... il existe maintenant des algorithmes qui donnent le nième chiffre de la séquence de Pi sans calculer les chiffres intermédiaires... on peut donc imaginer avec un algorithme ultime (si il existe) obtenir une réponse à une question partielle sans recalculer toutes les informations de l'univers à chaque fois.

G.

le fait d'avoir une vitesse de propagation maximale de l'information nous permet de concevoir un algorithme qui prédit l'état d'une séquence.

en réalité, il me semble qu'une vitesse finie pour le transfert de l'information est ce qui permet la causalité... qui est un des points nécessaire pour l'existence d'un algorithme tu as raison. C'est marrant que cela ai échappé aux philosophes, ils aurait peut-être pu prévoir la relativité avec ça!

G.

[invite6c250b59]

Donc plus un ensemble de données est compressible, moins il contient d'information. Inversement une suite de nombre réellement aléatoire n'est pas compressible parce que rien n'est prévisible ou calculable : tout bit est une information irremplaçable.

Tu as surement noté que le résultat de la compression dépend largement du programme utilisé, et que d'autre part il n'existe pas de programme universel marchant à tout coup pour la compression. pi est un bon exemple: un algorithme simple (plusieurs en fait) peut donner la séquence correcte, mais est-ce qu'on aurrait pu déduire ces algorithmes à partir de la séquence elle-même?

Du coup, on peut imaginer que les séquences apparement aléatoires qu'on peut trouver ne sont en fait pas aléatoire du tout mais produit par des algorithmes simples dont on a pas encore découvert l'existence. Bref l'univers pourrait être calculable et fini en terme de contenu d'information.

D'un autre coté, il me semble avoir entendu parler d'algorithme non calculables, dans le prolongement des travaux de Gödel (iriiax: es-tu au courant?). Si ils ont une signification physique (pas sur) alors ça invalide l'idée d'un univers calculable sans qu'on ai besoin de répondre à la question d'un contenu d'information fini/infini de l'univers

G.

PS: comme un vrai chercheur: une idée=un papier
PS II: Désolé j'ai l'impression de mettre planté avec les balises

[yat]

L'intérêt du chiffre que tu cites (012345678910111213141516...) c'est qu'il contient effectivement toutes les séquences de longueur finie possibles... à ma connaissance ça n'est pas démontré pour Pi par exemple (même si c'est la croyance générale).

Tiens, tu fais bien de le préciser, j'étais effectivement persuadé qu'il était démontré que pi était un nombre univers...

pi est un bon exemple: un algorithme simple (plusieurs en fait) peut donner la séquence correcte, mais est-ce qu'on aurrait pu déduire ces algorithmes à partir de la séquence elle-même?

Voilà encore une question clé, à mon avis. Le fait est que pour tenter de déterminer le "fonctionnement" de l'univers, on ne dispose que de l'observation de ses états successifs... et il semble qu'il y a des phénomènes dont on n'a pour l'instant d'autre moyens de les décrire que des stats.

[invitedb5bdc8a]

Bien que la réponse à la question initiale soit connue, la question reste intéressante. On voit que les notions de calculabilité, de quantité d'information, de compression d'information, de hasard (voir le débat sur le hasard, très riche), de déterminisme, de libre arbitre, de prévisibilité, d'ordre et de désordre, de loi et de chaos, d'épistémologie des sciences (et en particulier des mathématiques), d'intelligence ... sont très intimement liées. Ce qui conduit certains à faire ce que d'autres voient comme du hors sujet.
La réponse a la question posée a été donnée dans le fil de la discussion. Le théorème de gödel, appliqué à la question (Turing ?) du développement d'un algorithme permettant de détermnier en un temps fini si n'importe quel algorithme converge en un temps fini permet de répondre: non. Donc l'algorithme ultime mentionné ci dessus ne pourrait pas prévoir ce que donne un algorithme que je programmerais sur ma petite machine dans mon ptiti coin d'univers. A fortiori il ne pourrait donc calculer le reste de l'univers. Par contre on peut toujours faire des calculs approchés qui permettent de calculer certains phénomènes plus vite qu'ils ne se produisent, donc de les prévoir. Ce qui autorise la psycho histoire de fondation (ouf) qui comme c'est bien stipulé dans le livre ne prévoit que le mouvement global, pas les détails.

[invite6c250b59]

Bien que la réponse à la question initiale soit connue, la question reste intéressante.

D'accord sur l'intérêt de la question , pas sur la réponse que tu lui donne.

========= mise au point sur Gödel/Turing ===============

Si je comprend bien, Gödel a montré que les "univers" définis par un ensemble de rêgles axiomatiques contenaient au moins une proposition indécidable à l'intérieur de cet univers.

Comme ça s'applique à tous système logique, on peut en donner une illustration toute bête: "Tout ce que j'écris est faux"
Si cette phrase est vrai, elle est fausse, si elle est fausse, alors elle est vrai... donc elle est indécidable dans notre logique courante où une proposition ne peut être en même temps vrai et fausse.

Turing a étendu cette découverte pour sa machine dite "de Turing" (qui est un calculateur universel): dans ce cas le théorème d'indécidabilité fait qu'il n'y a pas de méthode marchant à tous les coups pour décider si cette machine universelle va ou non s'arréter (et donc c'est vrai pour n'importe quel algorithme).

==== et vous me dites si j'ai les pieds dans le tapis la dessus =====

Comme un algorithme ne peut prévoir à tous coup si un autre algorithme se termine, alors pi-r2 proclame que l'univers ne peut être un algorithme. Sauf que...

1- le critère de non prédictibilité n'est valide qu'à l'intérieur d'un système d'axiome donné: rien n'empêche d'inventer un système d'axiome plus riche pour contrer le problème. Ce que l'on programme dans son coin et que l'on constate indécidable est possiblement décidable dans un système plus large.

2- la portée de cette reflexion est limitée à la décidabilité, pas à l'existence: on peut bien imaginer un univers algorithmique dans lequel des propositions indécidables existent. En fait Gödel nous dit même qu'on a pas le choix à ce niveau: si c'est algorithmique, il y a un truc indécidable quelque part.

3- tu peux imaginer que l'univers est un algorithme (ou un système d'algorithme, ça ne fait pas de différence) en cours de calcul, c'est à dire que le décours du temps est lié à l'application d'un calcul sur cet algorithme. Dans ce cas, le théorème de Gödel nous dit simplement qu'il n'y a pas de moyen de savoir si cet algorithme fini un jour ou non.

Gamma

[invitea4b4a777]

L'une des question est de savoir si a partir d'un etat initial on arriverais a tout prévoir. La question est de savoir si on est capable de tout prevoir pour NOTRE univers (si on suppose l'existence d'univers parallele), ou tout prevoir pour un univers basé sur tel ou tel element. Je m'explique.

Imaginé un instant qu'on crée un algo qui ne contienne que 4 fonction (formule) avec 6 variable (element). Les fonctions sont les equations quantique pour les forces (il en manque 1, la gravité, mais imaginé qu'on ai la formule, ou alors prenez celle qui fonctionne au niveau macroscopique) et les variables sont les quarks. Fait une photo du rayonnement fossile ou de tout etat de l'univers avant et fait PLAY. Votre algo, en se basant sur les données du rayonnement fossile et sur les formules quantiques, vous calculera non pas tout les possibilité, mais toute les interaction entre les variables et donc sortira que les possibilité existantes. Commencer a T = 0, fait tourner l'equivalent en instruction du nombre d'interaction en 15 milliard d'années (et ca prend pas 15 milliard d'années, puisque certaine interaction reel sont plus longue que l'execution du code correspondant) et vous aurez le plus formidable telescope-microscope du monde. Continué en le laissant depacé la date du jour et vous aurez le devin le plus omniscient de l'univers. C'est plus ou moins ce qu'on fais avec les algo de vie artificielle dans lesquel on met des formules (contrainte) et des variable (organisme) et ou on regarde se que le chaos est capable de crée. Combiné 3 quark en 1 proton et 3 autre en 1 electron (aucun problème pour n'importe quel PC vu qu'on as les equations) puis combiné ses proton et electron et vous obtener un atome d'hydrogene. Continué les interactions en vous basant sur les formules quantiques et vous pourrez verifié si physique quantique et physique classique sont compatible puisqu'on devrait arrivé au meme univers quelques soit la methode (quantique ou classique). Et en se qui concerne les principes genre le principe d'incertitude, ben si c'est un principe connu de votre algo (donc forcement de nous, et c'est le cas pour ce principe) et votre algo n'est plus incertain puisqu'on decrit ce qu'est l'incertitude. La seul chose que notre algo a besoin, c'est les fomules de base, les variables de base et un etat de base. Le reste, il le determine par l'execution meme.

Effectivement, notre algo vit dans notre univers, mais l'univers de l'algo lui il vit dans la machine executant l'algo et pas dans notre univers. La machine fait office de barriere universelle, comme pour nous ou on est incapable de dire ce qu'il y a après la frontiere de l'univers, pt etre une machine de turing ou rien, mais personne ne peut le dire. Et un etre vivant de cet univers virtuel aura le meme problème que nous pour les limites de notre univers. Mais la, on en revient au problème soulevez par Matrix : vivons nous dans un vrai univers ou dans une representation virtuel de qqch qui nous echappe (puisque la representation est virtuel).

[invitedb5bdc8a]

Ouh là ! tout doux gamma. On ne s'est pas compris. J'essaie de ne rien "proclamer" et si c'est l'impression que j'ai donnée, je m'en excuse bien platement.
Pour l'interprétation du théorème de Gödel / revu par Turing, je suis d'accord avec toi, c'est comme ça que je le vois (avec le même risque de me manger le tapis).
Je n'ai pas dit (je crois...) que l'univers n'était pas un algorithme. J'ai dit qu'on ne pouvait pas concevoir un algorithme au sein de notre univers qui puisse permettre d'émuler cet univers et de prévoir son déroulement futur dans tous ses détails plus vite que l'univers ne se "calcule" lui même.
Je pense qu'en fait là dessus on a la même interprétation même si on ne l'écrit pas pareil. Pour moi, l'univers est cohérent et non contradictoire. Donc selon le théorème de Gödel, il contient effectivement des "indécidables". ce sont ces indécidables qui constituent le hasard, moteur des modifications.
En logique par exemple, les paradoxes sont "créateurs". Pour sortir de certains paradoxes (l'ensemble de tous les ensembles qui se contiennent, les adjectifs qui représentent ce qu'il veulent dire et ceux qui ne le font pas...) on doit "créer" des catégories "supérieures".

[invite6c250b59]

Maudit réseau de m.... si on peut même plus regarder les forums futura depuis le bureau, où va-t-on? hein? ou va-t-on??

J'essaie de ne rien "proclamer" et si c'est l'impression que j'ai donnée, je m'en excuse bien platement.

Non c'est moi "proclamer" a une connotation de revendication, et c'était pas mon intention, j'aurais du utiliser "dire/affirmer".

Je n'ai pas dit (je crois...) que l'univers n'était pas un algorithme. J'ai dit qu'on ne pouvait pas concevoir un algorithme au sein de notre univers qui puisse permettre d'émuler cet univers et de prévoir sont déroulement futur dans tous ses détails plus vite que l'univers ne se "calcule" lui même

.

ok je ne t'avais pas compris.

Je pense qu'en fait là dessus on a la même interprétation même si on ne l'écrit pas pareil.

En fait j'ai un (petit) doute. Si on considère que chacune des informations de l'univers est importante, alors ok. Mais qu'est-ce qui se passe si les informations sont redondantes (ou plutôt compressible)?

Je dis petit doute parcequ'avec les indécidables dont tu parles aussi, notre univers est probablement une réalisation particulière parmi un ensemble possible d'univers avec les mêmes lois... calculable aux hasards près donc.

Pour moi, l'univers est cohérent et non contradictoire. Donc selon le théorème de Gödel, il contient effectivement des "indécidables". ce sont ces indécidables qui constituent le hasard

Est-ce que tu imagines par exemple que les incertitudes quantiques sur la position/vitesse proviennent d'un indécidable? J'aime bien l'idée!

G.

[invitef3935d39]

Mais si l'on imagine le temps non plus comme une ligne mais comme un cercle ou une spirale?

Après tout, la Nature ne fonctionne-t'elle pas en cycles (cycles de la reproduction, cycles biologiques, cycles des climats...)? L'univers ne pourrait-il pas en faire de même?

Dans ce cas là, si tout n'était qu'un perpétuel recommencement, cet "algorithme ultime" ne pourrait-il pas alors réellement exister?

[invite6687cb56]

A lire vos post Jedeki et Boardingman on peut se dire que cet algorythme ne peut être connu s'il peut être changé , et n'est connu que s'il ne peut pas être changé (si une des propriétés de cet algorythme est de rester le même ).
Quelle seraient les autres propriétés de cet algorythme ?

[spi100]

par pitié, algorithme et pas algorythme.