Tu vas pas y arriver pour toutes les suites, parce qu'il existe des suites de bits aléatoires au sens de Levin-Chaitin pour lesquelles la complexité de Kolmogorov des n premiers termes de la suite moins n tend vers l'infini. La complexité de Kolmogorov d'une chaine c'est la taille de la plus petite description algorithmique de la chaine. Je pense qu'en fixant à un algo particulier on arrive à trouver une séquence qui n'est pas compressée strictement.
[^] # Re: «Une fois, j'en ai même attrapé un gros comme ça !»
Posté par Shuba . En réponse au journal Comment les gens perçoivent la gratuité dans l'informatique ?. Évalué à 4.
Tu vas pas y arriver pour toutes les suites, parce qu'il existe des suites de bits aléatoires au sens de Levin-Chaitin pour lesquelles la complexité de Kolmogorov des n premiers termes de la suite moins n tend vers l'infini. La complexité de Kolmogorov d'une chaine c'est la taille de la plus petite description algorithmique de la chaine. Je pense qu'en fixant à un algo particulier on arrive à trouver une séquence qui n'est pas compressée strictement.