COMPLEXITE ALEATOIRE (ou Complexité algorithmique, ou complexité de Solomonoff-Chaitin-Kolmogorov)

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.