La Complexité de Kolmogorov (1)

En général, la description d'une chaine est un programme dont la sortie est la chaine en question.

La longueur de cette description est celle du programme comprenant la fonction principale ainsi que toutes les sous fonctions appellées.

La longueur de chaque variable est celle du nombre de bits qui sont necessaires à la représentation de cette variable.

Donc la complexité de Kolmogorov n'est pas calculable par ordinateur, étant donné que le programme permettant de la calculer rentre dans le calcul de la complexité.

• La complexité K d'une chaine s dépend du langage de description L choisi.

• Pour un langage L donné, il peut y avoir plusieurs descriptions de s, notées di(s)

• La meilleure description de s, notée d(s), est celle dont la longueur est la plus courte.

• La taille de cette description est la valeur de complexisté de Kolmogorov de s : K(s) = |d(s)|.

• Si K1 et K2 sont les valeurs de complexité de la chaine s suivant les langages L1 et L2, alors, pour tout s, | K1(s) - K2(s) | <= cste.

• La complexité d'une chaine ne dépasse pas ou peu la longueur de la chaine : Pour tout s, K(s) <= | s | + cste.

(suite ...)