Колмогоровская сложность со слабыми языками описания

Мы можем думать о колмогоровской сложности строки $x$ как о длине самой короткой программы $P$ и вводим , что . Обычно эти программы взяты из некоторого полного набора Тьюринга (например, может быть описанием машины Тьюринга, или это может быть программа на LISP или C). Даже когда мы смотрим на ограниченную в ресурсах сложность Колмогорова, мы все равно смотрим на машины Тьюринга, но с некоторыми ограничениями на их время выполнения или использование пространства. Одним из последствий этого является то, что сложность строки неразрешима. Это кажется неловкой особенностью.x = P ( y ) $y$$x = P(y)$$P$

Что произойдет, если мы будем использовать полные модели Тьюринга для вычисления сложности Колмогорова?

Если мы выберем достаточно ограничительную модель (скажем, наша модель может реализовать только тождество), то сложность строки становится разрешимой, хотя мы также теряем теорему об инвариантности. Возможно ли иметь модель, достаточно сильную, чтобы иметь сложность, равную (вплоть до постоянного смещения или даже мультипликативного коэффициента) модели, полной по Тьюрингу, но достаточно слабую, чтобы все же можно было разрешить сложность строки? Существует ли стандартное название для колмогоровской сложности с нетюринговыми полными моделями вычислений? Где я мог прочитать больше об этом?

Предположим, что существует некоторая «разрешимая» сложность отличающаяся от колмогоровской сложности на сдвиг, на множитель или, в более общем смысле, на любую разрешимую монотонную неограниченную числовую функцию такую, что .$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)))$

Предположим, что мы имеем , то есть колмогоровская сложность строки быстро растет с . Но индекс также идентифицирует строку и, следовательно, может рассматриваться как верхняя граница (с некоторым постоянным сдвигом). Любое число нуждается только в битах для его представления, что противоречит быстрому росту сложности .s ( n ) n n s ( n ) K ( s n ) n log ( n ) K ( s 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))$

Невычислимость общего KC является следствием неразрешимости проблемы остановки в классе машин, используемых для KC. Если мы сможем решить проблему остановки по классу машин, то мы можем вычислить KC заданной строки в соответствии с ними. Просто запустите все пары машин и входов, которые останавливаются до первой, которая выводит , а затем выберите самую короткую.$x$