Computabilità della complessità di Kolmogorov del linguaggio di Turing-incompleto

Question

Sto cercando di determinare se la complessità di Kolmogorov è computabile per una lingua specifica. Sono certo che questa lingua data non è Turing-completa. La lingua è definita come segue:

$ a; b \ text {- esegue le istruzioni A e B uno dopo l'altro.} $
$! x_i! \ testo {- imposta la variabile} x_i \ testo {al valore} 2. $
$ {x_i \} \ testo {- raddoppia il valore della variabile} x_i $
$ [x_i] \ testo {- dimezza il valore della variabile} x_i \ testo {e gira su.} $
$ "w" \ testo {- Stampa la stringa} w \ in \ {a, b, ..., z, a, b ..., z \} $

. $ \ Lambda (x_i, a) \ text {- Executs istruzioni} A \ testo {esattamente} x_i \ testo {volte, indipendentemente dalle modifiche successive a} x_i $ < / P >.

In particolare, ho bisogno di sapere se la complessità di Kolmogorov relativa a questa lingua è generalmente computabile. Il programma che calcola questa complessità può essere scritto in una lingua completa di Turing.

Lo capisco per qualsiasi lingua di Turing-completa, la complessità di Kolmogorov non è calcolabile. Questa lingua qui manca la capacità di creare un loop infinto, però, e come tale è meno che turing-completo. Non sento alcuna intuizione derivante da questa osservazione però. Assumerei che questa lingua sia più debole, la complessità di Kolmogorov può essere calcolabile ora. Eppure non riesco a trovare una prova per questo. Dare un algoritmo che soddisfa questo compito appare troppo complicato. L'uso di questa lingua sembra un caso speciale del calcolo più generale della complessità Kolmogorov e in quanto tale, non posso derivare dagli attributi del caso generale se il caso generale non è calcolato. Questo potrebbe essere ancora.

Non sto trovando alcun motivo per stare in piedi con questo problema e accoglierebbe qualsiasi suggerimento e puntatori verso una soluzione. Possiamo dedurre qualsiasi altra cosa da questa lingua rispetto a quello che ho menzionato finora? È una potenza più bassa rispetto alle lingue complete-complete ci aiutano con questa situazione?

Answer 1

L'importante da notare è che i tuoi programmi si fermano sempre. Ciò rende il calcolo della complessità Kolmogorov un compito facile, dal momento che data una stringa $ W $ , puoi andare su tutti i possibili programmi di lunghezza $ \ le | w | +2 $ per trovare il programma più breve la cui uscita è $ W $ . Il limite superiore $ | w | +2 $ segue dal fatto che per qualsiasi stringa $ W $ , "W" è un programma la cui produzione è $ W $ .

In effetti, è probabilmente potuto calcolare la complessità di una stringa in tempo polinomiale, poiché la compressione è possibile solo in caso di ripetizioni (non è possibile sfruttare una struttura più generale). Qualcosa lungo le seguenti linee dovrebbe funzionare $ kc (w_1 ... w_n)=min \ limits_i \ big (kc \ sinistra (w_ {i + 1} ... w_n | w_i \ destra) + kc (w_1 ... w_i) \ big) $ , dove $ kc \ sinistra (w | w '\ destra) $ è Just $ kc (w) $ se $ w '$ non è un prefisso di $ W $ e $ kc (w '') + o (\ log j) $ altrimenti dove $ w= w '^ jw' '' $ e $ j $ è il numero massimo che lo soddisfa. Il punto è che devi solo calcolare la complessità delle sottostringhe di $ w $ , di cui ci sono $ o (| w | ^ 2) $ .