COMPLEXITE ALEATOIRE (ou Complexité algorithmique, ou complexité de Solomonoff-Chaitin-Kolmogorov)
Publié le 22/02/2012
Extrait du document
Source: http://www.peiresc.org/DINER/Lexique.pdf
Taille du plus petit algorithme (programme) capable de décrire complètement l'objet. Si cette taille n'est pas inférieure à la taille de l'objet, cela signifie qu'il n'y a pas d'autre description de l'objet que la donnée de l'objet lui même. Cela correspond bien à l'intuition de ce qui est aléatoire. Malheureusement la complexité algorithmique est incalculable, car rien ne permet d'affirmer qu'il n'existe pas un algorithme plus court que celui éventuellement trouvé. La complexité de Kolmogorov d'un objet peut être considérée comme une mesure absolue et objective (intrinsèque) de la quantité d'information qu'il contient. Ce n'est pas une mesure de la quantité de complexité physique, qui est donnée par la profondeur logique de Bennett. Le lien entre complexité aléatoire et théorie de l'information est assuré par le fait que la longueur probable de la plus courte description binaire sur ordinateur d'une variable aléatoire est approximativement égale à son entropie de Shannon.
Liens utiles
- COMPLEXITE ORGANISEE (ou profondeur logique, ou complexité de Bennett)
- comment rené rend-il compte de la complexité de sa sensibilité ?
- Révisons sur la complexité climatique
- La pensée est-elle un processus algorithmique ? (Leibniz)
- Est-ce la complexité d'un propos qui rend l'interprétation nécessaire ?