Złożoność Kołmogorowa ze słabymi językami opisu

Możemy myśleć o złożoności łańcucha Kołmogorowa jako długości najkrótszego programu P i wprowadzić y tak, że x = P ( y ) . Zazwyczaj programy te są pobierane z jakiegoś kompletnego zestawu Turinga (np. P może być opisem maszyny Turinga lub może to być program w LISP lub C). Nawet gdy patrzymy na złożoność złożoności Kołmogorowa, wciąż patrzymy na maszyny Turinga, ale z pewnymi ograniczeniami dotyczącymi ich czasu wykonywania lub wykorzystania przestrzeni. Jedną z konsekwencji tego jest to, że złożoność łańcucha jest nierozstrzygalna. To wydaje się niezręczną funkcją.$x$$P$$y$$x = P(y)$$P$

Co się stanie, jeśli użyjemy niekompetentnych modeli obliczeniowych do zdefiniowania złożoności Kołmogorowa?

Jeśli wybierzemy wystarczająco restrykcyjny model (powiedzmy, że nasz model może tylko implementować tożsamość), wówczas złożoność łańcucha staje się rozstrzygalna, chociaż tracimy również twierdzenie o niezmienniczości. Czy możliwe jest posiadanie modelu wystarczająco silnego, aby złożoność była równa (aż do stałego przesunięcia, a nawet mnożnika) modelowi Turinga-kompletnemu, ale wystarczająco słaba, aby nadal decydować o złożoności łańcucha? Czy istnieje standardowa nazwa złożoności Kołmogorowa z niekompletnymi modelami obliczeniowymi Turinga? Gdzie mogę o tym przeczytać więcej?

$D(s)$$K(s)$$f(n)$$K(s) > f(D(s))$

$D(s)$$s_n$$f(D(s_n))> \mathrm{vff}(n)$$\mathrm{vff}$$\exp(\exp(\exp(n)))$

$K(s_n) > \mathrm{vff}(n)$$s(n)$$n$$n$$s(n)$$K(s_n)$$n$$\log(n)$$K(s_n)$

$f$$s$$K(s) \not> f(D(s))$

Brak możliwości obliczenia ogólnego KC jest konsekwencją nierozstrzygalności problemu zatrzymania w stosunku do klasy maszyn używanych do KC. Jeśli możemy zdecydować o problemie zatrzymania w stosunku do klasy maszyn, możemy obliczyć KC danego ciągu według nich. Po prostu uruchom wszystkie pary maszyn i danych wejściowych, które zatrzymują się do pierwszej, która wypisuje , a następnie wybierz najkrótszą.$x$