Équivalence des définitions de Kolmogorov-Complexity

Il existe de nombreuses façons de définir la complexité de Kolmogorov et, généralement, toutes ces définitions sont équivalentes jusqu'à une constante additive. C'est-à-dire que si et sont des fonctions de complexité de kolmogorov (définies via différents langages ou modèles), alors il existe une constante telle que pour chaque chaîne , . Je crois que c'est parce que pour chaque fonction de complexité de Kolmogorov et pour chaque il tient que , pour une constante .K 2 c $K_1$$K_2$$c$$x$K x K ( x ) ≤ | x | + c $|K_1(x) - K_2(x)| < c$$K$$x$$K(x) \le |x| +c$$c$

Je suis intéressé par les définitions suivantes de , basées sur les machines de Turing$K$

1. nombre d'états : Définissez comme le nombre minimal tel qu'une MT avec états génère sur la chaîne vide.q q $K_1(x)$$q$$q$$x$
2. Durée du programme : Définissez comme le "programme" le plus court qui génère . À savoir, fixer un moyen de coder les MT en chaînes binaires; pour une machine désigne son encodage (binaire) comme . où le minimum est supérieur à tous les M qui produisent x sur une entrée vide.$K_2(x)$$x$$M$$\langle M \rangle$M $K_2(x) = \min |\langle M \rangle|$$M$$x$

Est-ce que $K_1$ et $K_2$ équivalents? Quelle est la relation entre eux, et laquelle saisit mieux le concept de complexité de Kolmogorov, s'ils ne sont pas équivalents.

Ce qui me dérange surtout, c'est l' augmentation du taux $K_2$ avec $x$ , qui ne semble pas être super-linéaire (ou au moins linéaire avec une constante $C>1$ telle que $K_2 < C|x|$ , plutôt que $|x|+c$ ). Considérez la MT la plus simple qui génère $x$ - celle qui code simplement $x$ dans le cadre de sa fonction d'états et de transitions. il est immédiat de voir que $K_1(x) \le |x|+1$ . Cependant l'encodage de la même machine est beaucoup plus grand, et la borne triviale que j'obtiens est $K_2(x) \le |x|\log |x|$.

Je m'excuse à l'avance d'avoir donné trop de détails, mais je suis sur le point de contredire les gens.

À propos de$K(x)≤K'(x)+c$

Le fait que provient généralement d'un interprète du langage de description # 2 dans le langage de description # 1 et non d'une traduction de programmes de # 2 en programmes de # 1.$K_1(x)≤K_2(x)+c$

Par exemple et vous obtenez cette inégalité aussi simplement que ceci:$K_\mathtt{C}(x)≤K_\mathtt{Python}(x)+c_\mathtt{py2c}$

void py_run(char * s) {
    // code of your Python interpreter
}

int main(void) {
    py_run("Put here your Python program of size Kpython(x)");
}

Ensuite, votre constante sera quelque chose comme 528 + 490240688 où 528 est le nombre de bits pour ce code et 490240688 bits est la taille de l'interpréteur Python officiel écrit en C.Bien sûr, vous n'avez besoin que d'interpréter ce qui est possible dans votre langage de description pour Python afin que vous puissiez faire mieux que 69 Mo :-)$c_\mathtt{py2c}$$528+490240688$$528$$490240688$

Ce qui est important, c'est que vous pouvez écrire votre programme Python de façon linéaire dans votre code C. Par exemple, une langue où vous devez mettre "BANANA" entre chaque caractère n'est pas un très bon programme de description et la propriété est alors fausse. (Mais si le langage de description vous autorise à écrire des données dans un fichier séparé ou dans un bloc, ce problème disparaît)

Pourquoi votre est défectueux$K_1(x)=q$

Le problème avec votre définition de est que vous pouvez avoir besoin de plus de bits pour décrire une machine de Turing avec états car vous devez coder des transitions.$K_1$$q$$q$

Donc aucun et K 2 ne sont probablement pas équivalents, mais c'est principalement la faute de K 1 . Je pense que nous pouvons prouver que pour tout un > 0 il y a une c une telle que K 1 ( x ) ≤ a | x | + c a . Bien sûr, tout a < 1 suffit pour réfuter le fait que K 1 n'est pas une fonction valide, car cela signifierait que nous pouvons coder plus toutes les 2 n chaînes de longueur possibles$K_1$$K_2$$K_1$$a>0$$c_a$$K_1(x)≤a|x|+c_a$$a<1$$K_1$$2^n$ dans un n + c a des bits.$n$$an+c_a$

Mais la taille est une limite incroyablement serrée lors de la construction de machines Turing. L'idée est que dans un bloc de états, il existe b 2 b façons de trouver des transitions pour chaque état et c'est mieux que les 2 b façons habituelles de remplir b bits. Ensuite, vous pouvez stocker dans chaque journal de bloc 2 b bits d'informations. (pas 2 log 2 b car vous devez entrer et sortir du bloc d'une manière ou d'une autre)$b$$b^{2b}$$2^b$$b$$\log_2 b$$2\log_2 b$

Alors oui ... Avec des blocs de taille vous pourriez probablement prouver K 1 ( x ) ≤ a | x | + c a . Mais j'ai déjà trop écrit sur les raisons pour lesquelles le nombre d'états n'est pas une fonction de complexité de Kolmogorov valide. Si vous voulez que j'élabore, je le ferai.$2^{1/a}$$K_1(x)≤a|x|+c_a$

Maintenant sur $K_2$

Le langage descriptif naïf correspond approximativement à (c'est-à-dire log 2 q pour chaque état suivant et détails sur l'écriture et la terminaison).$K_2(x)=q\cdot 2 \cdot (\log_2 q + 2)$$\log_2q$

Comme vous semblez l'être, je suis convaincu qu'une meilleure façon / tricherie serait d'autoriser à encoder des "données" dans la machine Turing, peut-être en ajoutant une balise binaire dans le langage de description qui indique si un état est un état de données ( qui écrit juste un peu et passe à l'état suivant) ou s'il fait autre chose. De cette façon, vous pouvez stocker un bit de votre dans un bit de votre langage descriptif.$x$

Cependant, si vous gardez le même vous pouvez utiliser la même technique que j'ai utilisée dans la partie précédente pour enregistrer quelques bits, mais il me semble que je suis bloqué à K 2 ( x ) ≤ a | x | journal | x | + c (pour tout a > 0 ) .. peut-être moins que log | x | , même, mais obtenir O ( | x | ) semble difficile. (Et je m'attends à ce que ce soit | x | , pas même O ( $K_2$$K_2(x)≤a|x|\log|x|+c$$a>0$$\log|x|$$O(|x|)$$|x|$ .)$O(|x|)$