Аннотация:
Рассмотрим двоичное слово $x_0$ колмогоровской сложности $K(x_0)\geq n$. Вопрос
состоит в следующем: найдутся ли два других слова $x_1$ и $x_2$ таких, что выполнены
следующие приблизительные равенства $K(x_i|x_j)\approx n$ и $K(x_i|x_j,x_k)\approx n$
для всех $0\leq i,j,k\leq2$, $i\ne j\ne k$, $i\ne k$? Доказано, что ответ положителен,
если требовать выполнения равенств с точностью до аддитивного члена вида
$O(\log K(x_0))$, и отрицателен с большей точностью, а именно с точностью
до $O(\log n)$.
УДК:
621.391.1:51
Поступила в редакцию: 18.02.2002 После переработки: 25.04.2003