Compubilité de la complexité de Kolmogorov de la langue de Turing-incomplète

Question

J'essaie de déterminer si la complexité de Kolmogorov est calculable pour une langue spécifique. Je suis certain que cette langue donnée n'est pas complète. La langue est définie comme suit:

$ a; b \ texte {- exécute les instructions A et B une après l'autre.} $
$! X_I! \ Text {- Définit la variable} x_i \ Text {à la valeur} 2. $
$ \ {x_i \ \ \ texte {- double la valeur de la variable} x_i $
$ [x_i] \ texte {- moitiés la valeur de la variable} x_i \ text {et l'arrondit.} $
$ "w" \ texte {- imprime la chaîne} w \ in \ {a, b, ..., z, a, b ..., z \} $
$ \ lambda (x_i, a) \ texte {- exécute l'instruction} a \ texte {exactement} x_i \ texte {fois, quelles que soient les modifications ultérieures de} x_i $ < / p>

Spécifiquement, j'ai besoin de savoir si la complexité Kolmogorov par rapport à cette langue est généralement calculable. Le programme qui calcule cette complexité peut être écrit dans une langue Turing-Complete.

Je comprends que pour toute langue Turing-Complete, la complexité de Kolmogorov n'est pas calculable. Ce langage ici manque de la capacité de créer une boucle infinte, cependant, et comme tel est inférieur à Turing-complet. Je ne ressens aucune intuition découlant de cette observation cependant. Je suppose que cette langue est plus faible, la complexité de Kolmogorov peut être calculée maintenant. Pourtant, je ne peux pas trouver une preuve pour cela. Donner un algorithme qui remplit cette tâche apparaît trop compliqué. L'utilisation de ce langage semble être une case particulière de la calculation plus générale de la complexité Kolmogorov et, en tant que telles, je ne peux pas tirer des attributs du cas général si le cas général n'est pas calculable. Cela peut encore être.

Je ne trouve aucun motif à faire face à ce problème et à accueillir des conseils et des pointeurs vers une solution. Pouvons-nous déduire autre chose de ce langage que ce que j'ai mentionné jusqu'à présent? Est-ce que c'est une puissance inférieure par rapport à Turing-Terminal Langues Aidez-nous avec cette situation?

Answer 1

La chose importante à noter est que vos programmes s'arrêtent toujours. Cela permet de calculer la complexité de Kolmogorov une tâche facile, car donné une chaîne $ w $ , vous pouvez consulter tous les programmes de longueur possibles $ \ le | w | +2 $ Pour trouver le programme le plus court dont la sortie est $ w $ . La limite supérieure $ | w | +2 $ découle du fait que pour n'importe quelle chaîne $ w $ , "W" est un programme dont la sortie est $ w $ .

En fait, vous pouvez probablement calculer la complexité d'une chaîne en temps polynomial, car la compression n'est possible que dans le cas de répétitions (vous ne pouvez pas tirer parti d'une structure plus générale). Quelque chose le long des lignes suivantes devrait fonctionner $ kc (w_n ... w_n)=min \ limites_i \ gros (kc \ gauche (w_ {i + 1} ... w_n | w_n | w_n | w_n | w_n | w_n | \ droite) + kc (w_1 ... w_i) \ gros) $ , où $ kc \ gauche (w | w '\ span> est Juste $ kc (w) $ si $ w '$ n'est pas un préfixe de $ w $ et $ kc (w '') + o (\ log j) $ sinon où $ w= w '^ jw' '' $ et $ j $ est le nombre maximal satisfaisant. Le point est que vous n'avez besoin que de calculer la complexité des sous-chaînes de $ w $ , dont il y a $ o (| w | ^ 2) $ .