Существуют ли такие x, что K (xx) <K (x), где K - колмогоровская полнота.

Обозначим через колмогоровскую сложность строки . Существуют ли такие строки, что . (Здесь - это сцепление с самим собой). Похожий , но другой вопрос был задан здесь , но контрпример дается в ответ на этот вопрос не работает для этого. $K(x)$ $x$ $K(xx)<K(x)$ $xx$ $x$

cc.complexity-theory kolmogorov-complexity Суни Якобсен
источник

Ответы:

Я не специалист по колмогоровской сложности, но я думаю, что такой x можно построить для любой функции сложности K следующим образом. Поскольку 1, 11, 1111, 11111111,…, 1 ^{2 ⁿ} ,… является кодировкой натурального числа n , K (1 ^{2 ⁿ} ) не может быть o (log n ). Однако когда n = 2 ^м , очевидно, K (1 ^{2 ⁿ} ) = K (1 ^{2 ^{2 ^м}} ) = O (log m ) = O (log log n ). Следовательно, последовательность K (1), K (11), K (1111), K (11111111),…, K (1 ^{2 ⁿ} ),… не может быть слабо монотонно возрастающей, что означает, что существует строка x в форме 1 ^{2 ⁿ} такая, что K ( xx ) <K ( x ).

Цуёси Ито
источник

@ Tsuyoshi, есть несжимаемая строка

такая, что

x

$x$

K (x x) < K (x)

$K(xx)\lt K(x)$

Мухаммед Аль-Туркистани

Я думаю, что

и K (1 ^ {2 ^ n}) = Ω (log n) противоречат друг другу. Что он имеет в виду: если

то

. В противном случае доказательство кажется хорошим.

K (1^{2^{2^{m}}}) = O (\log m)

$K(1^{2^{2^m}})=O(\log m)$

f (n) = o (\log n)

$f(n)=o(\log n)$

K (1^{2^{n}}) \neq O (f (n))

$K(1^{2^n})\neq O(f(n))$

Сунь Якобсен

Это похоже на работу. Действительно, я думаю, что это дает вам бесконечную последовательность таких строк. Тем не менее, либо я что-то неправильно понимаю, либо утверждение правила цепочки для Сложности Колмогорова, которое появляется в Википедии ( en.wikipedia.org/wiki/Chain_rule_for_Kolmogorov_complexity ), тогда неверно. Первоначально я думал, что определение википедии здесь может не применяться, так как там вы должны быть в состоянии знать, где заканчивается X и начинается Y, в то время как здесь это, кажется, не требуется, но когда Y = X, вы можете добавить это к описанию в O (1), говоря «разделить в середине».

Абель Молина

@Sune: Обозначение Ω (⋅) имеет несколько несколько разных определений. «K (1 ^ 2 ^ n) = Ω (log n)» в моем ответе означает «limsup K (1 ^ 2 ^ n) / log n> 0», и это не противоречит «K (1 ^ 2 ^ 2»). ^ m) = O (log m) ». Я отредактировал ответ, чтобы прояснить этот момент. Смотрите также Какому определению асимптотической скорости роста мы должны учить?

Цуёси Ито

@turkistany и все: обратите внимание, что всегда верно, что K (xx)> K (x) -c для некоторой константы, я думал, что на это следует обратить внимание. Это также означает, что нам нужно очень точное определение несжимаемого, если мы хотим изучить этот вопрос. Я думаю, что ответ снова да, но у меня нет доказательств.

Домоторп

Да. Сложность Коломогорова на практике зависит от вашей модели. Машина Тьюринга, Java-программа, C ++-программа, ... если в вашей модели есть идиосинкразия, которая позволяет этому происходить на конечном наборе входных данных, это не проблема.

Лучший вопрос заключается в том, как много из этого поведения вы можете избежать, и при этом модель будет универсальной.

Чад Brewbaker
источник

Я думаю, что лучший вопрос: существует ли такой x для всех моделей? Я не знаю, что такое «модель» формально, но кажется, что ответ Цуёси работает для всех разумных языков программирования.

Сунь Якобсен

Вы можете назначить

0

$0$ в

x x

$xx$ и что-то большее для

x

$x$ и еще есть универсальная модель.

Каве

@Tsuyoshi:

Я не очень хорошо понял ваше доказательство.

Предположим, что мы выбрали стандартную машину Тьюринга в качестве «языка описания», определяющего $K(s)$ как число состояний самой маленькой ТМ, которая начинается с пустой ленты и останавливается после печати строки $s$ в теме.

Вы доказали, что мы можем построить $TM_{ss}$ который "печатает" строку $ss = 1111...1 = 1^{2^{n+1}}$ на ленте и построен с меньшим количеством состояний, чем $TM_{s}$ который "печатает" строку $s = 1^{2^n}$ ?

Можно ли применить ваше доказательство к колмогоровской сложности на ТМ?

OK! Я получил это ... когда $n+1 = 2^{m}$ $TM_{ss}$ can be "powered" with a new "inner loop" (we add some states but we can remove many states that in $TM_{s}$ are needed for "counting" $n$ ) ... Thanks!

(sorry, but I don't know how to post this as comment)

Marzio De Biasi
источник

To write a comment on a post made by someone other than you which is not an answer to your question, you need reputation point at least 50.

Tsuyoshi Ito