Когда функция, отображающая строку с его сложностью Колмогорова, остается без префикса?

Question

В Алгоритмическая случайность и сложность от Дауни и Хиршфельдта, на странице 129 заявлено, что

$ qquad displaystyle sum_ {k ( sigma) down-arrow} 2^{-k ( sigma)} leq 1 $,

где $ k ( sigma) down -arrow $ означает, что $ k $ останавливается на $ sigma $, $ sigma $ является бинарной строкой. $ K $ обозначает сложность Kolmogorov, без префикса.

Когда $ k $ остановится? Я думаю, что это только останавливается на конечном количестве входов, поскольку классическое доказательство некомпьютируемости сложности Колмогорова дает верхнюю границу в домене $ k $. Но тогда конечный набор входов, на которые можно выбрать $ K $ остановки произвольным (нужно просто хранить конечное количество сложностей в исходном коде).

Так хорошо ли эта сумма? Другими словами, хорошо ли определен домен $ k $?

Answer 1

Я думаю ты прав; $ K $ - это конкретная функция, которая не может быть рассчитана. Автор, вероятно, означает использовать немного (произвольная) приблизительная реализация; Так что нет, это не кажется четко определенным, если вы педантично. Вы также можете назвать это злоупотреблением обозначениями.

Считайте это вместо этого:

$ qquad displaystyle forall {m in mathcal {m} _k}. sum_ {m ( sigma) down-arrow} 2^{-k ( sigma)} leq 1 $

с $ mathcal {m} _k = {m mathrm {tm} mid m ( sigma) ! downarrow ampision m ( sigma) = k ( sigma) } $ Все машины Тьюринга, которые вычисляют подфункции $ k $.

По сути, это означает: граница содержится независимо от того, какие строки ваша реализация может вычислить сложность Колмогорова.

---

Как отмечает Карл в комментариях, вполне вероятно, что нотация не имеет ничего общего с остановкой или вычислением, поскольку $ k $ не вычисляется. Прочитайте $ sum_ {k ( sigma) ! Downarrow} $ в качестве суммы, в диапазоне над доменом $ k $.