Computabilidade da complexidade de Kolmogorov da linguagem incompleta de Turing

Question

Estou tentando determinar se a complexidade de Kolmogorov é computável para uma linguagem específica. Estou certo de que essa linguagem dada não é completa. A linguagem é definida da seguinte forma:

$ a; b \ text {- executa instruções A e B um após o outro.} $
$! X_I! \ Texto {- Sets Variável} x_i \ text {para o valor} 2. $
$ \ {x_i \} \ text {- dobra o valor da variável} x_i $
$ [x_i] \ text {- metade do valor da variável} x_i \ text {e arredeia.} $
$ "w" \ text {- imprime a string} w \ in {a, b, ..., z, a, b ..., z \} $
. $ \ lambda (x_i, a) \ text {- executa instrução} a \ text {exatamente} x_i \ text {vezes, independentemente de alterações posteriores em} x_i $ < / p >.

Especificamente, preciso saber se a complexidade de Kolmogorov em relação a esta linguagem é geralmente computável. O programa que calcula essa complexidade pode ser escrito em uma linguagem completa de Turing.

Eu entendo que, para qualquer linguagem completa de Turing, a complexidade de Kolmogorov não é computável. Esta linguagem aqui não tem a capacidade de criar um loop InfoTe, porém, e como tal é menor que a Turing - completa. Eu não estou sentindo nenhuma intuição decorrente dessa observação. Eu assumiria que, esta linguagem sendo mais fraca, a complexidade de Kolmogorov pode ser computável agora. No entanto, não consigo encontrar uma prova para isso. Dando um algoritmo que preenche esta tarefa aparece excessivamente complicado. O uso desta linguagem parece ser um caso especial da computabilidade mais geral da complexidade de Kolmogorov e como tal, não consigo derivar dos atributos do caso geral, se o caso geral não for computável. Isso ainda pode ser.

Eu não estou encontrando nenhum terreno para ficar com este problema e acolher qualquer dicas e ponteiros para uma solução. Podemos deduzir mais nada dessa linguagem do que o que mencionei até agora? É menor que a energia em relação aos idiomas completos de Turing nos ajude com esta situação?

Answer 1

O importante para notar é que seus programas sempre param. Isso torna a computação da complexidade Kolmogorov uma tarefa fácil, já que deu uma string $ W $ , você pode passar por todos os programas possíveis de comprimento $ \ le | w | +2 $ para encontrar o programa mais curto cuja saída é $ W $ . O limite superior $ | w | +2 $ segue do fato de que para qualquer string $ W $ , "W" é um programa cuja saída é $ W $ .

Na verdade, você provavelmente poderia calcular a complexidade de uma string no tempo polinomial, uma vez que a compactação só é possível no caso de repetições (você não pode aproveitar uma estrutura mais geral). Algo ao longo das seguintes linhas deve funcionar $ kc (w_1 ... w_n)=min \ limites_i \ big (kc \ left (w_ {i + 1} ... w_n | w_i \ Direita) + kc (w_1 ... w_i) \ big) $ , onde $ kc \ esquerda (w | w '\ direita) $ é apenas $ kc (w) $ se $ w '$ $ não é um prefixo de $ W $ , e $ kc (w '') + o (\ log j) $ caso contrário, onde $ w= w '^ jw' '$ e $ J $ é o número máximo que satisfaz isso. O ponto é que você só precisa calcular a complexidade de substrings de $ W $ , dos quais existem $ O (| w | ^ 2) $ .