Speaker
Description
В этой работе рассматривается Колмогоровская сложность перечисления множеств. Существует два конкурирующих определения сложности: детерминированное $(I(S))$ и рандомизированное $(H(S))$. Можно показать, что $I(S) \geq H(S) + c$. Соловей [1] доказал, что выполняется $I(S) \leq 3 H(S) + 2 \log H(S) + c$. В этой работе, предполагая, что рандомизированная машина Тьюринга перечисляет множество в определенном порядке, доказывается, что оценку Соловея можно улучшить. А именно, если машина перечисляет числа в порядке возрастания, то верна оценка $I(S) \leq H(S) + 2 \log H(S) + c$. Если же машине разрешено перечислять числа в порядке увеличения их длины двоичной записи, то верна оценка $I(S) \leq 2 H(S) + 2 \log H(S) + c$. Этот результат можно применить, если рассмотреть конечный автомат вместо рандомизированной машины Тьюринга.
