La complexité de Kolmogorov est-elle une fonction surjective?

Fixons un encodage des machines de Turing et une machine de Turing universelle, U, qui en entrée (T, x) sort quelles que soient les sorties T en entrée x (éventuellement les deux fonctionnant pour toujours). Définissez la complexité de Kolmogorov de x, K (x), comme la longueur du programme le plus court, p, de telle sorte que U (p) = x.

Existe-t-il un N tel que pour tout n> N il y ait un x avec K (x) = n?

Remarque. Si nous définissons les machines de Turing universelles d'une manière différente, la réponse peut être négative. Par exemple, considérons un U qui en entrée (T, x) simule T sur x si la longueur de (T, x) est divisible par 100, et sinon ne fait rien. On peut modifier cet exemple de plusieurs manières pour obtenir des contre-exemples pour différentes définitions de machines de Turing universelles.

Juste un commentaire étendu sans approfondissement: vous pouvez peut-être tricher sur l'encodage d'une machine de Turing, et construire un encodage artificiel qui mène à une complexité de Kolmogorov surjective:

• représente la machine de Turing qui délivre 0 (1 état TM);$0$$0$
• représente la machine de Turing qui produit p + 1 (le nombre représenté par la chaîne binaire p plus un); c'est simplement une version "zippée" implicite d'une MT décidable qui produit p + 1 ;$0p$$p+1$$p$$p+1$
• représente la p + 1 -ème machine de Turing dans une énumération standard (l'énumération peut ignorer les MT déjà incluses avec 0 et 0 p ).$1p$$p+1$$0$$0p$

La TM universelle correspondante sur l'entrée vérifie quelle est la valeur de b , si elle est 0 alors elle sort simplement x + 1 , sinon elle simule TM M x + 1 ( M 0 lorsque x est la chaîne vide); notez que M x + 1 intègre les entrées.$bx$$b$$0$$x+1$$M_{x+1}$$M_0$$x$$M_{x+1}$

Pour toutes les chaînes , 1 ≤ K ( $x$ ; et pour tout n ≥ 1 il y a 2 n chaînes de longueur n mais il n'y a que 2 n - 1 - 1 programmes de longueur < n qui peuvent être représentés en utilisant lecodage 1 p ; et seulement 2 n - 1 programmes de longueur n qui peuvent être représentés en utilisant le 1 $1 \leq K(x) \leq |x|+1$$n \geq 1$$2^{n}$$n$$2^{n-1}-1$$< n$$1p$$2^{n}-1$$n$$1p$codage; ainsi au moins une chaîne de longueur n ne peut pas être représentée avec un programme 1 p de longueur ≤ n ; mais il peut sûrement être représenté avec le programme 0 x ′ de longueur n + 1 (on ne s'inquiète pas s'il existe aussi un programme 1 p de même longueur n + 1 qui le génère).$x'$$n$$1p$$\leq n$$0x'$$n+1$$1p$$n+1$

$n > 1$$x', |x'|=n$$K(x') = n+1$