Сложность по Колмогорову
- Колмогоровская сложность — мера сложности описания строки.
- Алгоритмическая информация связана с предсказанием и использованием универсального априорного распределения вероятностей.
- Существует несколько вариантов колмогоровской сложности или алгоритмической информации.
- Теорема: C(x) ≤ K(x) + 2 log2 C(x).
- Теорема: существует c такой, что C(x) ≤ |x|.
- Теорема: K(x|y) ≤ K(x) ≤ K(x, y) ≤ максимум (K(x|y) + K(y), K(y|x) + K(x)).
- Теорема: K(xy) ≤ K(x, y).
- Теорема: K(x, y) = K(x|y, K(y)) + K(y) = K(y, x).
- Теорема: для любой вычислимой функции f, K(f(x)) ≤ K(x) + K(f).
- Наивная попытка создания программы для вычисления K не работает из-за невычислимости проблемы остановки.
- Теорема: существуют строки сколь угодно большой колмогоровской сложности.
- Пересказана только часть статьи. Для продолжения перейдите к чтению оригинала.
Полный текст статьи: