Complexité de Kolmogorov - Kolmogorov complexity

Cette image illustre une partie de la fractale de l' ensemble de Mandelbrot . Le simple stockage de la couleur 24 bits de chaque pixel de cette image nécessiterait 23 millions d'octets, mais un petit programme informatique peut reproduire ces 23 Mo en utilisant la définition de l'ensemble de Mandelbrot et les coordonnées des coins de l'image. Ainsi, la complexité de Kolmogorov du fichier brut encodant ce bitmap est bien inférieure à 23 Mo dans tout modèle de calcul pragmatique . La compression d'image à usage général de PNG ne la réduit qu'à 1,6 Mo, plus petite que les données brutes mais beaucoup plus grande que la complexité de Kolmogorov.

Dans la théorie algorithmique de l'information (un sous-domaine de l' informatique et des mathématiques ), la complexité de Kolmogorov d'un objet, tel qu'un morceau de texte, est la longueur d'un programme informatique le plus court (dans un langage de programmation prédéterminé ) qui produit l'objet en sortie. Il est une mesure des calcul des ressources nécessaires pour préciser l'objet, et est également connu comme la complexité algorithmique , complexité Solomonoff-Kolmogorov-Chaitin , complexité taille du programme , la complexité descriptive , ou entropie algorithmique . Il porte le nom d' Andrey Kolmogorov , qui a publié pour la première fois sur le sujet en 1963.

La notion de complexité de Kolmogorov peut être utilisée pour énoncer et prouver des résultats d' impossibilité apparentés à l'argument diagonal de Cantor , au théorème d'incomplétude de Gödel et au problème d'arrêt de Turing . En particulier, aucun programme P calculant une borne inférieure pour la complexité de Kolmogorov de chaque texte ne peut renvoyer une valeur essentiellement plus grande que la propre longueur de P (voir la section § Théorème d'incomplétude de Chaitin ) ; par conséquent, aucun programme ne peut calculer la complexité exacte de Kolmogorov pour une infinité de textes.

Définition

Considérez les deux chaînes suivantes de 32 lettres minuscules et chiffres :

abababababababababababababababab , et
4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

La première chaîne a une courte description en anglais, à savoir " write ab 16 times", qui se compose de 17 caractères. Le second n'a pas de description simple évidente (utilisant le même jeu de caractères) autre que l'écriture de la chaîne elle-même, c'est-à-dire " write 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7" qui a 38 caractères. Par conséquent, l'opération d'écriture de la première chaîne peut être considérée comme "moins complexe" que l'écriture de la seconde.

Plus formellement, la complexité d'une chaîne est la longueur de la description la plus courte possible de la chaîne dans un langage de description universel fixe (la sensibilité de la complexité relative au choix du langage de description est discutée ci-dessous). On peut montrer que la complexité de Kolmogorov d'une chaîne ne peut pas dépasser de quelques octets la longueur de la chaîne elle-même. Les chaînes comme l' exemple abab ci-dessus, dont la complexité de Kolmogorov est faible par rapport à la taille de la chaîne, ne sont pas considérées comme complexes.

La complexité de Kolmogorov peut être définie pour n'importe quel objet mathématique, mais pour des raisons de simplicité, la portée de cet article est limitée aux chaînes. Nous devons d'abord spécifier un langage de description pour les chaînes. Un tel langage de description peut être basé sur n'importe quel langage de programmation informatique, tel que Lisp , Pascal ou Java . Si P est un programme qui génère une chaîne x , alors P est une description de x . La longueur de la description est juste la longueur de P en tant que chaîne de caractères, multipliée par le nombre de bits dans un caractère (par exemple, 7 pour ASCII ).

On pourrait, alternativement, choisir un encodage pour les machines de Turing , où un encodage est une fonction qui associe à chaque machine de Turing M une chaîne de bits < M >. Si M est une machine de Turing qui, à l'entrée w , sort la chaîne x , alors la chaîne concaténée < M > w est une description de x . Pour l'analyse théorique, cette approche est plus adaptée à la construction de preuves formelles détaillées et est généralement préférée dans la littérature de recherche. Dans cet article, une approche informelle est discutée.

Toute chaîne s a au moins une description. Par exemple, la deuxième chaîne ci-dessus est sortie par le programme :

function GenerateString2()
    return "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"

alors que la première chaîne est sortie par le pseudo-code (beaucoup plus court) :

function GenerateString1()
    return "ab" × 16

Si une description d ( s ) d'une chaîne s est de longueur minimale (c'est-à-dire utilisant le moins de bits), elle est appelée description minimale de s , et la longueur de d ( s ) (c'est-à-dire le nombre de bits description) est la complexité de Kolmogorov de s , notée K ( s ). Symboliquement,

K ( s ) = | d ( s )|.

La longueur de la description la plus courte dépendra du choix du langage de description ; mais l'effet du changement de langue est limité (un résultat appelé théorème d'invariance ).

Théorème d'invariance

Traitement informel

Il existe des langages de description qui sont optimaux, dans le sens suivant : étant donné toute description d'un objet dans un langage de description, ladite description peut être utilisée dans le langage de description optimal avec un surcoût constant. La constante ne dépend que des langages impliqués, pas de la description de l'objet, ni de l'objet décrit.

Voici un exemple de langage de description optimal. Une description comportera deux parties :

  • La première partie décrit un autre langage de description.
  • La deuxième partie est une description de l'objet dans cette langue.

En termes plus techniques, la première partie d'une description est un programme informatique (en particulier : un compilateur pour le langage de l'objet, écrit dans le langage de description), la deuxième partie étant l'entrée de ce programme informatique qui produit l'objet en sortie.

Le théorème d'invariance est le suivant : Étant donné tout langage de description L , le langage de description optimal est au moins aussi efficace que L , avec un surcoût constant.

Preuve : Toute description D dans L peut être convertie en une description dans le langage optimal en décrivant d'abord L comme un programme informatique P (partie 1), puis en utilisant la description originale D comme entrée dans ce programme (partie 2). La longueur totale de cette nouvelle description D′ est (environ) :

| D′ | = | P | + | D |

La longueur de P est une constante qui ne dépend pas de D . Ainsi, il y a au plus un surcoût constant, quel que soit l'objet décrit. Par conséquent, le langage optimal est universel jusqu'à cette constante additive.

Un traitement plus formel

Théorème : Si K 1 et K 2 sont les fonctions de complexité relatives aux langages de description complète de Turing L 1 et L 2 , alors il existe une constante c  - qui ne dépend que des langages L 1 et L 2 choisis - telle que

s . - cK 1 ( s ) - K 2 ( s ) ≤ c .

Preuve : Par symétrie, il suffit de prouver qu'il existe une constante c telle que pour toute chaîne s

K 1 ( s ) ≤ K 2 ( s ) + c .

Maintenant, supposons qu'il existe un programme dans le langage L 1 qui agit comme un interprète pour L 2 :

function InterpretLanguage(string p)

p est un programme dans L 2 . L'interpréteur est caractérisé par la propriété suivante :

L'exécution InterpretLanguagesur l'entrée p renvoie le résultat de l'exécution de p .

Ainsi, si P est un programme dans L 2 qui est une description minimale de s , alors InterpretLanguage( P ) renvoie la chaîne s . La longueur de cette description de s est la somme de

  1. La longueur du programme InterpretLanguage, que nous pouvons considérer comme la constante c .
  2. La longueur de P qui par définition est K 2 ( s ).

Cela prouve la borne supérieure souhaitée.

Histoire et contexte

La théorie algorithmique de l'information est le domaine de l'informatique qui étudie la complexité de Kolmogorov et d'autres mesures de complexité sur des chaînes (ou d'autres structures de données ).

Le concept et la théorie de la complexité de Kolmogorov sont basés sur un théorème crucial découvert pour la première fois par Ray Solomonoff , qui l'a publié en 1960, le décrivant dans "A Preliminary Report on a General Theory of Inductive Inference" dans le cadre de son invention de la probabilité algorithmique . Il a donné une description plus complète dans ses publications de 1964, "A Formal Theory of Inductive Inference," Part 1 and Part 2 in Information and Control .

Andrey Kolmogorov a ensuite publié indépendamment ce théorème dans Problems Inform. Transmission en 1965. Gregory Chaitin présente également ce théorème dans J. ACM  – L'article de Chaitin a été soumis en octobre 1966 et révisé en décembre 1968, et cite à la fois les articles de Solomonoff et de Kolmogorov.

Le théorème dit que, parmi les algorithmes qui décodent les chaînes à partir de leurs descriptions (codes), il en existe un optimal. Cet algorithme, pour toutes les chaînes, permet des codes aussi courts que permis par tout autre algorithme jusqu'à une constante additive qui dépend des algorithmes, mais pas des chaînes elles-mêmes. Solomonoff a utilisé cet algorithme et les longueurs de code qu'il permet pour définir une "probabilité universelle" d'une chaîne sur laquelle l'inférence inductive des chiffres suivants de la chaîne peut être basée. Kolmogorov a utilisé ce théorème pour définir plusieurs fonctions des chaînes, notamment la complexité, le caractère aléatoire et l'information.

Lorsque Kolmogorov a pris connaissance du travail de Solomonoff, il a reconnu la priorité de Solomonoff. Pendant plusieurs années, l'œuvre de Solomonoff était plus connue en Union soviétique qu'en Occident. Le consensus général dans la communauté scientifique, cependant, était d'associer ce type de complexité à Kolmogorov, qui était préoccupé par le caractère aléatoire d'une séquence, tandis que la probabilité algorithmique est devenue associée à Solomonoff, qui s'est concentré sur la prédiction en utilisant son invention de la distribution de probabilité a priori universelle. . Le domaine plus large englobant la complexité descriptive et la probabilité est souvent appelé complexité de Kolmogorov. L'informaticien Ming Li considère qu'il s'agit d'un exemple de l' effet Matthew : "…à tous ceux qui ont, plus sera donné…"

Il existe plusieurs autres variantes de la complexité de Kolmogorov ou de l'information algorithmique. Le plus largement utilisé est basé sur des programmes auto-délimitants , et est principalement dû à Leonid Levin (1974).

Une approche axiomatique de la complexité de Kolmogorov basée sur les axiomes de Blum (Blum 1967) a été introduite par Mark Burgin dans l'article présenté pour publication par Andrey Kolmogorov.

Résultats de base

Dans la discussion suivante, soit K ( s ) la complexité de la chaîne s .

Il n'est pas difficile de voir que la description minimale d'une chaîne ne peut pas être beaucoup plus grande que la chaîne elle-même - le programme GenerateString2ci-dessus qui génère s est une quantité fixe supérieure à s .

Théorème : Il existe une constante c telle que

s . K ( s ) | s | + c .

Incalculabilité de la complexité de Kolmogorov

Une tentative naïve d'un programme pour calculer K

À première vue, il peut sembler trivial d'écrire un programme qui peut calculer K ( s ) pour n'importe quel s , tel que le suivant :

function KolmogorovComplexity(string s)
    for i = 1 to infinity:
        for each string p of length exactly i
            if isValidProgram(p) and evaluate(p) == s
                return i

Ce programme parcourt tous les programmes possibles (en parcourant toutes les chaînes possibles et en ne considérant que celles qui sont des programmes valides), en commençant par le plus court. Chaque programme est exécuté pour trouver le résultat produit par ce programme, en le comparant à l'entrée s . Si le résultat correspond à la longueur du programme est retourné.

Cependant cela ne fonctionnera pas car certains des programmes p testés ne se termineront pas, par exemple s'ils contiennent des boucles infinies. Il n'y a aucun moyen d'éviter tous ces programmes en les testant d'une manière ou d'une autre avant de les exécuter en raison de la non-calculabilité du problème d'arrêt .

Qui plus est, aucun programme ne peut calculer la fonction K , fût-ce si sophistiqué soit-il. Ceci est prouvé dans ce qui suit.

Preuve formelle d'incalculabilité de K

Théorème : Il existe des chaînes de complexité de Kolmogorov arbitrairement grande. Formellement : pour chaque n ∈ ℕ, il existe une chaîne s avec K ( s ) ≥ n .

Preuve : Sinon, toutes les chaînes finies infiniment nombreuses pourraient être générées par les programmes en nombre fini avec une complexité inférieure à n bits.

Théorème : K n'est pas une fonction calculable . En d'autres termes, il n'y a pas de programme qui prend une chaîne s en entrée et produit l'entier K ( s ) en sortie.

La preuve indirecte suivante utilise un langage simple de type Pascal pour désigner les programmes ; pour des raisons de simplicité de preuve, supposons que sa description (c'est-à-dire un interpréteur ) a une longueur de1 400 000 bits. Supposons pour contradiction qu'il existe un programme

function KolmogorovComplexity(string s)

qui prend en entrée une chaîne s et renvoie K ( s ). Tous les programmes sont de longueur finie donc, par souci de simplicité de preuve, supposons qu'il soit7 000 000 000 bits. Considérons maintenant le programme de longueur suivant1288 bits :

function GenerateComplexString()
    for i = 1 to infinity:
        for each string s of length exactly i
            if KolmogorovComplexity(s) ≥ 8000000000
                return s

En utilisant KolmogorovComplexitycomme sous-programme, le programme essaie chaque chaîne, en commençant par la plus courte, jusqu'à ce qu'il renvoie une chaîne avec une complexité de Kolmogorov au moins8 000 000 000 bits, c'est-à-dire une chaîne qui ne peut être produite par aucun programme plus court que8 000 000 000 bits. Cependant, la durée totale du programme ci-dessus qui a produit s n'est que7 001 401 288 bits, ce qui est une contradiction. (Si le code de KolmogorovComplexityest plus court, la contradiction demeure. S'il est plus long, la constante utilisée dans GenerateComplexStringpeut toujours être modifiée de manière appropriée.)

La preuve ci-dessus utilise une contradiction similaire à celle du paradoxe de Berry : " 1 Le 2 plus petit 3 positif 4 entier 5 que 6 ne peut pas 7 être 8 défini 9 en 10 moins 11 que 12 vingt 13 anglais 14 mots". Il est également possible de montrer la non-calculabilité de K par réduction de la non-calculabilité du problème d'arrêt H , puisque K et H sont équivalents de Turing .

Il existe un corollaire, appelé avec humour le « théorème du plein emploi » dans la communauté des langages de programmation, affirmant qu'il n'existe pas de compilateur parfait pour optimiser la taille.

Règle de chaîne pour la complexité de Kolmogorov

La règle de la chaîne pour la complexité de Kolmogorov stipule que

K ( X , Y ) K ( X ) + K ( Y | X ) + O (log( K ( X , Y ))).

Il précise que le plus court programme qui reproduit X et Y est pas plus qu'un terme logarithmique plus grand qu'un programme de reproduction X et un programme de reproduction Y donné X . En utilisant cette déclaration, on peut définir un analogue d'information mutuelle pour la complexité de Kolmogorov .

Compression

Il est simple de calculer les limites supérieures pour K ( s ) - compressez simplement la chaîne s avec une méthode, implémentez le décompresseur correspondant dans la langue choisie, concaténez le décompresseur à la chaîne compressée et mesurez la longueur de la chaîne résultante - concrètement, la taille d'une archive auto-extractible dans la langue donnée.

Une chaîne s est compressible d'un nombre c si elle a une description dont la longueur n'excède pas | s | − c bits. Cela revient à dire que K ( s ) | s | − c . Sinon, s est incompressible par c . Une chaîne incompressible par 1 est dite simplement incompressible  - selon le principe du pigeonhole , qui s'applique car chaque chaîne compressée correspond à une seule chaîne non compressée, des chaînes incompressibles doivent exister, car il y a 2 n chaînes de bits de longueur n , mais seulement 2 n − 1 chaînes plus courtes, c'est-à-dire des chaînes de longueur inférieure à n , (c'est-à-dire de longueur 0, 1, ..., n − 1).

Pour la même raison, la plupart des chaînes sont complexes dans le sens où elles ne peuvent pas être compressées de manière significative – leur K ( s ) n'est pas beaucoup plus petit que | s |, la longueur de s en bits. Pour rendre cela précis, fixez une valeur de n . Il y a 2 n chaînes de bits de longueur n . La distribution de probabilité uniforme sur l'espace de ces chaînes de bits attribue un poids exactement égal 2 n à chaque chaîne de longueur n .

Théorème : Avec la distribution de probabilité uniforme sur l'espace des chaînes de bits de longueur n , la probabilité qu'une chaîne soit incompressible par c est d'au moins 1 − 2 c +1 + 2 n .

Pour prouver le théorème, notons que le nombre de descriptions de longueur n'excédant pas nc est donné par la série géométrique :

1 + 2 + 2 2 + … + 2 nc = 2 nc +1 − 1.

Il reste au moins

2 n − 2 nc +1 + 1

des chaînes de bits de longueur n qui sont incompressibles par c . Pour déterminer la probabilité, divisez par 2 n .

Théorème d'incomplétude de Chaitin

Complexité de Kolmogorov K ( s ) , et deux fonctions de borne inférieure calculables prog1(s), prog2(s). L'axe horizontal ( échelle logarithmique ) énumère toutes les chaînes s , classées par longueur ; l'axe vertical ( échelle linéaire ) mesure la complexité de Kolmogorov en bits . La plupart des chaînes sont incompressibles, c'est-à-dire que leur complexité de Kolmogorov dépasse leur longueur d'une quantité constante. 9 cordes compressibles sont montrées dans l'image, apparaissant comme des pentes presque verticales. En raison du théorème d'incomplétude de Chaitin (1974), la sortie de tout programme calculant une limite inférieure de la complexité de Kolmogorov ne peut pas dépasser une limite fixe, qui est indépendante de la chaîne d'entrée s .

D'après le théorème ci-dessus ( § Compression ), la plupart des chaînes sont complexes dans le sens où elles ne peuvent pas être décrites de manière significativement "compressée". Cependant, il s'avère que le fait qu'une chaîne spécifique soit complexe ne peut pas être formellement prouvé, si la complexité de la chaîne est supérieure à un certain seuil. La formalisation précise est la suivante. Tout d'abord, fixez un système axiomatique particulier S pour les nombres naturels . Le système axiomatique doit être suffisamment puissant pour qu'à certaines assertions A sur la complexité des chaînes, on puisse associer une formule F A dans S . Cette association doit avoir la propriété suivante :

Si F A est prouvable à partir des axiomes de S , alors l'assertion correspondante A doit être vraie. Cette « formalisation » peut être réalisée sur la base d'une numérotation Gödel .

Théorème : Il existe une constante L (qui ne dépend que de S et du choix du langage de description) telle qu'il n'existe pas de chaîne s pour laquelle l'énoncé

K ( s ) ≥ L       (comme formalisé dans S )

peut être prouvé dans S .


Idée de preuve : La preuve de ce résultat est calquée sur une construction autoréférentielle utilisée dans le paradoxe de Berry . Nous obtenons d'abord un programme qui énumère les preuves dans S et nous spécifions une procédure P qui prend en entrée un entier L et imprime les chaînes x qui sont dans les preuves dans S de l'énoncé K ( x ) ≥ L . En fixant ensuite L à une valeur supérieure à la longueur de cette procédure P , nous avons que la longueur requise d'un programme pour imprimer x comme indiqué dans K ( x ) ≥ L comme étant au moins L est alors inférieure à la quantité L puisque la chaîne x a été imprimé par la procédure P . C'est une contradiction. Il n'est donc pas possible pour le système de preuve S de prouver K ( x ) ≥ L pour L arbitrairement grand, en particulier, pour L plus grand que la longueur de la procédure P , (qui est finie).

Preuve :

Nous pouvons trouver une énumération efficace de toutes les preuves formelles dans S par une procédure

function NthProof(int n)

qui prend en entrée n et produit une preuve. Cette fonction énumère toutes les preuves. Certaines d'entre elles sont des preuves de formules qui ne nous intéressent pas ici, puisque toutes les preuves possibles dans le langage de S sont produites pour certains n . Certaines d'entre elles sont des formules de complexité de la forme K ( s ) ≥  ns et n sont des constantes dans le langage de S . il y a une procédure

function NthProofProvesComplexityFormula(int n)

qui détermine si la n ième preuve prouve réellement une formule de complexité K ( sL . Les chaînes s , et l'entier L à leur tour, sont calculables par procédure :

function StringNthProof(int n)
function ComplexityLowerBoundNthProof(int n)

Considérez la procédure suivante :

function GenerateProvablyComplexString(int n)
    for i = 1 to infinity:
        if NthProofProvesComplexityFormula(i) and ComplexityLowerBoundNthProof(i) ≥ n
            return StringNthProof(i)

Étant donné un n , cette procédure essaie chaque preuve jusqu'à ce qu'elle trouve une chaîne et une preuve dans le système formel S de la formule K ( s ) ≥  L pour un certain L  ≥  n ; si une telle preuve n'existe pas, elle boucle indéfiniment.

Enfin, considérons le programme composé de toutes ces définitions de procédure et d'un appel principal :

GenerateProvablyComplexString(n0)

où la constante n 0 sera déterminée ultérieurement. La longueur totale du programme peut être exprimée sous la forme U + log 2 ( n 0 ), où U est une constante et log 2 ( n 0 ) représente la longueur de la valeur entière n 0 , en supposant raisonnable qu'elle soit codée en chiffres binaires . Nous choisirons n 0 supérieur à la longueur du programme, c'est-à-dire tel que n 0 > U +log 2 ( n 0 ). Ceci est clairement vrai pour n 0 suffisamment grand, car le membre de gauche croît linéairement en n 0 tandis que le membre de droite croît logarithmiquement en n 0 jusqu'à la constante fixe U .

Alors aucune preuve de la forme " K ( s )≥ L " avec Ln 0 ne peut être obtenue dans S , comme on peut le voir par un argument indirect : Si ComplexityLowerBoundNthProof(i)pouvait retourner une valeur ≥ n 0 , alors la boucle à l' intérieur GenerateProvablyComplexStringfinirait par se terminer , et cette procédure renverrait une chaîne s telle que

K ( s )
?? n 0           par construction de GenerateProvablyComplexString
> U + log 2 ( n 0 ) par le choix de n 0
?? K ( s ) puisque s a été décrit par le programme avec cette longueur

C'est une contradiction, CQFD

En conséquence, le programme ci-dessus, avec la valeur choisie de n 0 , doit boucler indéfiniment.

Des idées similaires sont utilisées pour prouver les propriétés de la constante de Chaitin .

Longueur minimale des messages

Le principe de longueur de message minimum de l'inférence statistique et inductive et de l'apprentissage automatique a été développé par CS Wallace et DM Boulton en 1968. MML est bayésien (c'est-à-dire qu'il incorpore des croyances antérieures) et théorique de l'information. Il a les propriétés souhaitables d'invariance statistique (c'est-à-dire les transformations d'inférence avec une re-paramétrisation, comme des coordonnées polaires aux coordonnées cartésiennes), de cohérence statistique (c'est-à-dire même pour des problèmes très difficiles, MML convergera vers n'importe quel modèle sous-jacent) et d'efficacité ( c'est-à-dire que le modèle MML convergera vers n'importe quel véritable modèle sous-jacent aussi rapidement que possible). CS Wallace et DL Dowe (1999) ont montré un lien formel entre le MML et la théorie algorithmique de l'information (ou complexité de Kolmogorov).

Aléatoire de Kolmogorov

Le caractère aléatoire de Kolmogorov définit une chaîne (généralement de bits ) comme étant aléatoire si et seulement si chaque programme informatique pouvant produire cette chaîne est au moins aussi long que la chaîne elle-même. Pour rendre cela précis, un ordinateur universel (ou machine de Turing universelle ) doit être spécifié, de sorte que "programme" signifie un programme pour cette machine universelle. Une chaîne aléatoire dans ce sens est « incompressible » en ce sens qu'il est impossible de « compresser » la chaîne dans un programme plus court que la chaîne elle-même. Pour chaque ordinateur universel, il existe au moins une chaîne algorithmiquement aléatoire de chaque longueur. Cependant, le fait qu'une chaîne particulière soit aléatoire dépend de l'ordinateur universel spécifique choisi. En effet, un ordinateur universel peut avoir une chaîne particulière codée en dur en lui-même, et un programme exécuté sur cet ordinateur universel peut alors simplement se référer à cette chaîne codée en dur en utilisant une courte séquence de bits (c'est-à-dire beaucoup plus courte que la chaîne elle-même) .

Cette définition peut être étendue pour définir une notion d'aléatoire pour des séquences infinies à partir d'un alphabet fini. Ces séquences algorithmiquement aléatoires peuvent être définies de trois manières équivalentes. L'une utilise un analogue efficace de la théorie de la mesure ; un autre utilise des martingales efficaces . La troisième voie définit une séquence infinie comme étant aléatoire si la complexité de Kolmogorov sans préfixe de ses segments initiaux croît assez rapidement — il doit y avoir une constante c telle que la complexité d'un segment initial de longueur n soit toujours d'au moins nc . Cette définition, contrairement à la définition du caractère aléatoire pour une chaîne finie, n'est pas affectée par la machine universelle utilisée pour définir la complexité de Kolmogorov sans préfixe.

Relation avec l'entropie

Pour les systèmes dynamiques, le taux d'entropie et la complexité algorithmique des trajectoires sont liés par un théorème de Brudno, que l'égalité tient pour presque tous .

On peut montrer que pour la sortie des sources d'information de Markov , la complexité de Kolmogorov est liée à l' entropie de la source d'information. Plus précisément, la complexité de Kolmogorov de la sortie d'une source d'information de Markov, normalisée par la longueur de la sortie, converge presque sûrement (comme la longueur de la sortie tend vers l'infini) vers l' entropie de la source.

Versions conditionnelles

La complexité de Kolmogorov conditionnelle de deux chaînes est, grosso modo, définie comme la complexité de Kolmogorov de x étant donné y comme entrée auxiliaire de la procédure.

Il existe également une complexité conditionnelle à la longueur , qui est la complexité de x étant donné la longueur de x connue/entrée.

Voir également

Remarques

Les références

Lectures complémentaires

Liens externes