Bases de la complexité !

[invite231234]

Bonsoir, il y a un sujet qui se voudrait similaire mais en fait j'aborde la complexité a minima :

http://fr.wikipedia.org/wiki/Complex..._de_Kolmogorov

http://en.wikipedia.org/wiki/NP-complete

http://fr.wikipedia.org/wiki/Machine_de_Turing

http://fr.wikipedia.org/wiki/Entropie_de_Shannon

http://fr.wikipedia.org/wiki/Entropie

http://fr.wikipedia.org/wiki/Th%C3%A9orie_du_chaos

http://fr.wikipedia.org/wiki/Syst%C3%A8me_dissipatif

Ces liens ont-ils en commun la complexité ?
Peut-on en tirer une définition opérationnelle a minima ?
Doit-on faire intervenir la notion temporelle dans la définition de la complexité ?
Comment ne pas penser que la complexité dépend de la notion d'observateur et de sa "finalité" ?
Est-ce une question d'échelle à laquelle on se place ?
Décrire la complexité est complexe !
-----

[invite73192618]

http://www.slideshare.net/seanmcarro...ng-time-aright
http://www.scottaaronson.com/blog/?p=762
http://www.scottaaronson.com/blog/?p=791
http://dabacon.org/pontiff/?p=5912

[invite231234]

Wow, merci Jiav. Il va falloir que j'essais de décrypter cet anglais dont je suis si mauvais mais les schémas me parlent. Alors d'après la logique de tes liens (des schémas ), je comprends que le temps est impliqué dans une formulation de la complexité. L'entropie n'est pas une mesure de la complexité mais intervient comme moteur de sa construction par la thermodynamique hors équilibre. En fait j'avais en tête de l'eau liquide froide, faible entropie, faible complexité, qui est chauffée et donc entre en ébullition, medium entropie, forte complexité puisque l'on peut arriver aux cellules de Benar (ou un truc du genre) mais instable puisque le liquide s'évapore et qu'il a consommation d'énergie en quantité fini. Enfin toute l'eau c'est évaporée, forte entropie, faible complexité.

Jiav, dis-moi si ce qu'ils disent a propos de la mort thermique de l'Univers est en fait une nécessité "en vue" d'accroître la complexité ? C'est ce que j'ai cru comprendre, une explication serait la bienvenue. J'ai vu aussi qu'il parlait de quantité d'information contenu dans un nombre restreint de bits. Il parle également de micro-états faut-il associer la notion d'observateur valorisée par la MQ en théorie de la complexité, n'y a-t-il pas une définition minimale en terme de bits à la notion de ce que l'on se représente d'un micro-état ?

[invite73192618]

C'est dur la science sans anglais... bon rapidement:

Le contexte et la question sont introduits magnifiquement par Sean Carroll à partir de sa slide 15 jusqu'à la slide 22. Le contexte est que l'univers est initialement homogène avec beaucoup d'énergie libre (fond diffus cosmologique oblige), à long terme subira probablement une "mort thermique" c'est-à-dire un état homogène avec un minimum d'énergie libre (loi d'augmentation de l'entropie oblige), mais entre les deux il semble se passer des choses intéressantes (genre nous) c'est-à-dire un état hétérogène et "complexe". La question est: comment quantifier cette complexité que l'on perçoit intuitivement?

Une première idée est la complexité de Kolmogorov, qui est mathématiquement la taille de la plus petite machine de Turing équivalente à un état quelconque. Le problème immédiat est que, si la mécanique quantique est correcte, alors les transformations de l'univers au cours du temps sont unitaires, c'est-à-dire que l'information est conservée, c'est-à-dire que la complexité de Kolmogorov est invariante au cours du temps. Pour reprendre l'exemple de la tasse de café diapo 16, cela veut dire que la tasse 2 ne serait malgré les apparences pas plus complexe que les tasses 1 et 3, sauf à violer la mécanique quantique. De plus, de très légères modifications de l'état de la tasse 2 lui ferait acquérir soudainement une complexité très grande, ce qui est esthétiquement gênant. La complexité telle que définit par Kolmogorov est donc peu satisfaisante pour ce problème et il faut alors trouver une autre mesure. Un autre problème est que c'est une mesure qui est mathématiquement prouvée comme incalculable

Carroll tend à penser (selon mon interprétation de ce qu'il a écrit en commentaire sur le blog d'Aaronson) que la solution est à chercher en séparant les échelles de taille, c'est-à-dire que la tasse 2 est plus complexe car chaque niveau de résolution apporte de l'information alors que pour les tasses 1 et 3 il n'y a pas ou pas beaucoup d'information nouvelle quand on change la résolution. Il ne propose toutefois pas de calcul opérationnel.

Aaronson propose d'utiliser une mesure qu'il appelle complextropy construite en modifiant la complexité de Kolmogorov grosso modo de la façon suivante: le plus petit programme qui génère, en temps polynomial, une distribution d'états difficile à différencier, en temps polynomial, de l'état mesuré.

Un avantage est que la contrainte de terminer en temps fini fait que cette mesure n'est plus du domaine de l'incalculable mais au pire dans la classe PSPACE... sauf que cette classe est en soit monstrueuse: calculable selon la définition de la calculabilité, mais en réalité incalculable en pratique.

Finalement le dernier lien est une proposition de Bennett, en réalité bien antérieure, toujours pour mesurer la complexité au sens où la tasse 2 est plus complexe que les tasses 1 et 3. Sa proposition est le logical depth, qui est aussi une variante de la complexité de kolmogorov: le plus petit temps mis par un des plus petit programmes générant l'état recherché. Je ne suis pas certain si c'est calculable ou non, par contre cette définition à l'avantage de lier temps et complexité: un état plus complexe nécessite nécessairement un temps plus long/plus une évolution est courte moins elle peut mener à un grand changement de complexité. Ce qui est une prédiction probablement testable.

Oups... mon "rapidement" a pris le bord

[A voir en vidéo sur Futura]

[pesdecoa]

Carroll tend à penser (selon mon interprétation de ce qu'il a écrit en commentaire sur le blog d'Aaronson) que la solution est à chercher en séparant les échelles de taille, c'est-à-dire que la tasse 2 est plus complexe car chaque niveau de résolution apporte de l'information alors que pour les tasses 1 et 3 il n'y a pas ou pas beaucoup d'information nouvelle quand on change la résolution. Il ne propose toutefois pas de calcul opérationnel.

Cette idée est vraiment interessante!
Prenons le cas du mouvement Brownien qui est le mouvement aléatoire d'une particule. Ce mouvement est invariant par changement d'échelle. Quelleque soit l'échelle d'observation, le mouvement reste inchangé. Dans ce cas, la complexité, suivant la définition de Carroll devient, infinie.
Ceci a du sens : Le hasard serait défini comme un système ayant une complexité infinie...

[Médiat]

Bonjour,

Une remarque : la complexité de Kolmogorov a été légèrement amendé sous le nom de complexité de Levin-Chaitin.

Un texte de Chaitin qui devrait intéresser les biologistes : http://www.cs.auckland.ac.nz/~chaitin/mit.pdf

[invite06b993d0]

très intéressant ce papier. Merci.

[shmikkki]

Oui, rien que l'abstract est très intéressant! Merci!
Même si je pense que je ne vais pas comprendre grand chose de la suite ... je ne comprend même pas certaines symboles mathématiques utilisés ...

[invite73192618]

Très intéressant ce lien

Jiav, dis-moi si ce qu'ils disent a propos de la mort thermique de l'Univers est en fait une nécessité "en vue" d'accroître la complexité ?

Non, la mort thermique amène à une diminution de complexité selon leurs définitions.

n'y a-t-il pas une définition minimale en terme de bits à la notion de ce que l'on se représente d'un micro-état ?

Pas compris.

Dans ce cas, la complexité, suivant la définition de Carroll devient, infinie.

Non, contresens. Le hasard comme complexité maximale est en prenant la définition de Kolmogorov. Les trois auteurs mentionnés cherchent au contraire à corriger cette caractéristique vue comme non désirable.

[noureddine2]

Non, contresens. Le hasard comme complexité maximale est en prenant la définition de Kolmogorov. Les trois auteurs mentionnés cherchent au contraire à corriger cette caractéristique vue comme non désirable.

salut , le hasard c'est comme le chaos , c'est très complexe .
le déterminisme est moins complexe .

[invite73192618]

Le chaos est par définition déterministe et simple.

[pesdecoa]

Non, contresens. Le hasard comme complexité maximale est en prenant la définition de Kolmogorov. Les trois auteurs mentionnés cherchent au contraire à corriger cette caractéristique vue comme non désirable.

Perso, une complexité infinie ne me pose pas de problème. Si on fait le rapprochement avec la machine de turing . l' indécidabilité ou le hasard implique le non calculabilité car la complexité est infinie.
C'est une seconde façon de lier hasard et complexité

[Xoxopixo]

Bonjour,

Le chaos est par définition déterministe et simple.

Le chaos qui découle d'un processus déterministe, est simple.
Nuance.

[invite73192618]

http://fr.wikipedia.org/wiki/Th%C3%A9orie_du_chaos

[pesdecoa]

Pour mettre tout le monde d'accord, on pourrait dire que le chaos est cet ingrédient qui rend complexe le simple

[invite6754323456711]

Un texte de Chaitin qui devrait intéresser les biologistes : http://www.cs.auckland.ac.nz/~chaitin/mit.pdf

Dans ce cadre la définition de la complexité repose sur la théorie algorithmique de l’information. Des personnes comme Daniel tammet semble fonctionner à l'inverse de nous dans la représentation de l'information (symbole/codage) : http://data0.eklablog.com/nolaskey/p...ammet%20pi.jpg

Je suis moins convaincu de l'application de ce cadre pour les cas semblables à Daniel tammet.

Patrick

[pesdecoa]

Bonjour,

Une remarque : la complexité de Kolmogorov a été légèrement amendé sous le nom de complexité de Levin-Chaitin.

Un texte de Chaitin qui devrait intéresser les biologistes : http://www.cs.auckland.ac.nz/~chaitin/mit.pdf

Je n'ai pas compris comment Chaitin réussi à calculer la complexité d'une forme...
En tout cas sa méthode semble dire qu'il est possible de quantifier des formes géométriques par leur complexité.
Si quelqu'un pouvait donner l'explication, ce serait sympa...

[invite6754323456711]

Je n'ai pas compris comment Chaitin réussi à calculer la complexité d'une forme...

Est complexe ce qui ne peut se décrire brièvement. Ce qui semble donc être le cas pour le signifié "complexité".

Patrick

[Xoxopixo]

Un texte de Chaitin qui devrait intéresser les biologistes : http://www.cs.auckland.ac.nz/~chaitin/mit.pdf

Je n'ai pas compris comment Chaitin réussi à calculer la complexité d'une forme...
En tout cas sa méthode semble dire qu'il est possible de quantifier des formes géométriques par leur complexité.

D'après ce que j'ai pu en comprendre, le document présente une manière de définir la complexité d'une "forme" en la ségmentant en sous-parties de granularité "d".
Par exemple deux parties X et Y de la taille d.

Le principe en est le suivant :
Si les parties ne presentent aucun lien entre eux, c'est à dire que la connaissance de l'état de X ne peut permettre d'en déduire l'état de Y, elles sont indépendantes.
Si H est cette mesure de la complexité et que X et Y sont indépendants, on a H(X,Y)=H(X)+H(Y).
Mais si X et Y ne sont pas totalement indépendants on a H(X,Y)=H(X)+H(Y)-H(X:Y).
H(X:Y) étant la valeur qui défini le lien entre les sous-parties X et Y.
Plus ce lien a une valeur élevée et plus X et Y sont dépendants, donc moins (X,Y) est complexe.

Cette première approche défini un "état" instantanné de la complexité, qui doit être comparé aux etats successifs si on s'interresse à du "vivant".
Le "vivant", ce n'est pas une "image", mais un "film".
Est considéré "vivant" une structure dont la valeur de la complexité diminue avec le temps pour se stabiliser à une valeur "du vivant".

On ne parle pas ici de géométrie, dans le sens par exemple de la droite abstraite (en 3D ici) qui on est d'accord semble ne nécessiter, "à priori", que peu d'informations.
On ségmente la droite en "pixels" de taille "d" ainsi que le volume qui l'entoure, et bien sûr on constate que les états 1 ou 0 des "pixels" sont liés par une loi. Cette loi permet de réduire le nombre de bits nécéssaires à la description de la "forme".
Ce qui fait de la "forme"; une droite en 3D; un objet moins complexe que le l'objet constitué du même nombre de "pixels" répartis au hasard.

On peut critiquer, comme le souligne le document lui-même, l'approche de la définition du vivant, qui est probablement incomplete, mais je pense que la proposition de la définition de la complexité instantanée de toute structure, vivante ou inerte, est ici tout à fait cohérente et opérationelle.

[invite6754323456711]

Le principe en est le suivant :

Cela ressemble à la mesure numérique du contenu commun en information qui est obtenue en utilisant des algorithmes de compression de données: http://homepages.cwi.nl/~paulv/papers/SimilarityV3.pdf

Patrick

[invite231234]

Hello Jiav !

Non, la mort thermique amène à une diminution de complexité selon leurs définitions.

Oui, je pense que nous sommes d'accord, ce que j'ai voulu dire maladroitement, c'est que la mort thermique de l'univers représente en quelque sorte un état final. Et que donc le moteur qui amène à cette situation est le temps et plus précisément l'augmentation de l'entropie. Evolution qui permet au passage d'augmenter la complexité temporairement. N'est-ce donc pas bêtement l'évolution de l'Univers dans le temps qui assure le passage à la complexité même si celle-ci ne sera pas l'aboutissement puisque comme tu le dis la mort thermique est un état de faible complexité.

Pas compris.

Oui là c'est pas clair !
Ce que j'ai voulu signifié c'est une définition opérationnelle qui pourrait alimenter un algorithme minimal afin de décrire le plus précisément possible (en terme d'accessibilité de l'information) un micro-état. Mais bon ... ?

Alors sinon mon objectif concernant ce topic est de vous amenez à réfléchir à ça : Comment parler de "l'intelligence" sans parler de "complexité" ? Il me semble que "nous" n'échappons pas à l'évolution qui nous à amené à être intelligent, du moins ça c'est la manière anthropocentrique de se décrire. Ne peut-on pas s'expliquer par une procédure, qui même en restant incalculable, nous permettrait de savoir quels éléments sont nécessaire à une complexification.
Ce que j'ai compris est qu'on pourrait faire un modèle de notre "fonctionnement" (ou du moins quelque-chose qui s'en rapproche) en implémentant sur la plus petite machine de Turing un algorithme minimal capable de sortir une série de bits en un temps polynomial sans oublier et ce me semble important une capacité de stockage pour passer à l'étape suivante. ça serait comme une avancé dans la compréhension de la complexité. Mais en parlant de compréhension dites moi si j'ai mal raisonné, ou bien, utilisé des définitions qui ne collent pas tout à fait avec le cadre ...

Bon, je vais aller complexifier mon cerveau !

[invite6754323456711]

la complexité d'une forme...

En fait si tu codes/numérises un tableau pour obtenir des pixels, la manière à laquelle tu les organise dans l'espace va faire varier sa complexité définit dans ce cadre. Le nombre de permutation de pixel semblable (même codification) laissant le tableau inchangé, reste quand à lui invariant.

Patrick

[pesdecoa]

D'après ce que j'ai pu en comprendre, le document présente une manière de définir la complexité d'une "forme" en la ségmentant en sous-parties de granularité "d"...

Un super grand merci Xoxopixo!
Je suis impressionné par ton travail de vulgarisation du document!

Donc il y a l'aspect spatial et l'aspect temporel.
La spatialisation est prise en compte à travers un terme de dépendance entre les différentes parties. Effectivement si il y a une parfaite indépendance entres les différentes parties, alors on a une complexité maximale.

Il y a aussi l'aspect temporel. La complexité varie au cours du temps. Pour certaines valeurs particulières de la complexité, alors l'apparition du vivant est propice.

[invite6754323456711]

La complexité varie au cours du temps.

Ce qui n'apparaît pas être la même chose que de dire la complexité est corrélé/dépend du temps. Dans un espace donné je peux changer dans le temps l'organisation des objets qui le remplissent, ce qui conduit à faire varier sa complexité. La complexité, dans ce cas, reste lié à l'organisation dans l'espace.

Le nombre de permutation des pixels qui transforme la scène semble être une mesure de ses degrés de liberté. Dans ce cas ils ne peuvent s'exprimer que si on rajoute une dimension temps (changement) en plus de l'espace à la scène.

Patrick

[pesdecoa]

Le nombre de permutation de pixel semblable (même codification) laissant le tableau inchangé, reste quand à lui invariant.

Très bien vu!
L'intérêt de rechercher des invariants, -ce qui n'est jamais une chose facile à voir!-, est qu'on peut envisager de faire par la suite des calculs!

[invite231234]

Excusez mon impertinence ou mon absence totale de compréhension du dit document mais je me risque à fournir une image au risque (bon vous m'aurez reconnu) de paraître ridiculus.
Ne peut-on faire un analogue de réflexion entre la MQ et ce document, comme le dit Xoxo, si les partie sont de granularité d et quelles sont indépendantes H(X,Y) = H(X) + H(Y) comme le ferait des particules, (au sens classique), du numérique en somme, par contre si elles sont dépendantes on a H(X,Y) = H(X) + H(Y) - H(X:Y) comme si l'on pouvait retirer les interférences de cette onde qui interfèrent, (au sens de la mécanique ondulatoire) de l'analogique en somme.
Ne peut-on afficher une probabilité d'état de forme à partir du moment où le temps s'en mêle ?
Onde(s)/Particule(s) ... Analogique/Numérique ... Représentation(s) <-- objet(s)/invariant(s) !

[invite6754323456711]

Ne peut-on afficher une probabilité d'état de forme à partir du moment où le temps s'en mêle ?

Dans le cadre de la MQ on ne connait pas le devenir observable (avant de l'avoir observé). Au mieux dans une représentation donné on peut donner une mesure des possibles. L'exemple donné par Delayale "Le Soleil se lèvera demain" prend en compte la structure que forme les évènements passés. Tout nouveaux évènements venant se rajouter, les plus probables d'après la mesure de Levin seraient ceux qui maintiendrait une structure. Est-ce vraiment ce qui est constaté en MQ ?

Patrick

[invite231234]

Salut Patrick !

Dans le cadre de la MQ on ne connait pas le devenir observable (avant de l'avoir observé).

Oui mais que ne nous faisons-nous pas comme a priori par le calcul ...

Au mieux dans une représentation donné on peut donner une mesure des possibles.

Oui c'est ce que je voulais dire par probabilité c'est toujours a priori !

'exemple donné par Delayale "Le Soleil se lèvera demain" prend en compte la structure que forme les évènements passés. Tout nouveaux évènements venant se rajouter, les plus probables d'après la mesure de Levin seraient ceux qui maintiendrait une structure. Est-ce vraiment ce qui est constaté en MQ ?

C'est plutôt ce qui est constaté dans l'ensemble ... non !

[invite6754323456711]

C'est plutôt ce qui est constaté dans l'ensemble ... non !

Les structures ne sont-elles pas la conséquence de nos représentations ?

Une autre façon d'intégrer le temps dans la mesure de la notion de complexité dans le cadre des représentations que l'on se fait. Dans l'exemple du tri-rapide deux représentations/descriptions sont faite. Une graphique, l'autre textuelle. La représentation graphique permet (sans l'aide du texte) me semble t-il d'avoir une description dés la lecture des premières images, ce qui ne semble pas le cas de la description textuelle (sans l'aide des schémas). Une description semble plus concise que l'autre dans le sens ou on acquière une description complète dans un temps plus court.

Patrick

[pesdecoa]

Dans le vivant, la complexité se stabilise sur certains niveaux... Et c'est là que j'ajoute une hypothèse un peu osée...
Ces niveaux de complexité sont tels que le beau est maximisé!
Tel la roue du paon...