ce que nous nommerons simple
On peut en effet toujours donner à un ordinateur une construction telle qu’une opération très particulière (par exemple le calcul de pi ou l’impression de l’intégrale des œuvres de Victor Hugo) y sera codée par un bit. On retrouve ici la notion connue qu’une information n’est jamais contenue dans un message seul, mais toujours dans le couple message + décodeur pris de façon indissociable. Aussi la notion de « plus petit programme théorique » ne peut-elle être définie opérationnellement de façon rigoureuse et univoque qu’avec la référence à une machine. On pourrait objecter qu’il suffit de prendre comme référence la machine la plus simple. C’est oublier que ce que nous nommerons simple dépend justement de notre vécu et de notre langage, tous deux arbitraires.
Une difficulté supplémentaire réside dans le fait que la complexité de Kolmogorov n’est pas décidable : on peut donner un algorithme produisant l’objet voulu, ce qui prouve que la complexité de cet objet est au plus la taille de cet algorithme. Mais on ne peut pas écrire de programme qui donne la complexité de Kolmogorov de tout objet que l’on voudrait lui donner en entrée.
La notion, manipulée avec précaution, se révèle néanmoins à l’origine de nombreux résultats théoriques.
