Колмогоровська складність

Колмогоровська складність — довжина найкоротшої програми, яка генерує заданий рядок. Термін названий на честь математика Андрія Колмогорова (1903—1987).

Прикладом нескінченного неперіодичного десяткового дробу є число пі (${\displaystyle \pi }$) — ${\displaystyle 3,141592\dots }$. Запис десяткового дробу числа ${\displaystyle \pi }$ хоч і нескінченний, має дуже низьку колмогорівську складність, оскільки існує дуже проста програма, яка генерує будь-яку кількість його цифр. Колмогоровська складність варіюється для різних комп'ютерів (точніше, машин Тюрінга або об'єктів, ізоморфних до них). Через нерозв'язність задачі зупинки не може існувати алгоритм, який би обчислював колмогоровську складність з гарантованим успіхом.

Складність та ентропія конструктивних об'єктів

Складність та ентропія конструктивних об'єктів, відома як колмогоровська складність, складність Колмогорова, стохастична складність в алгоритмічній теорії інформації, складність об'єкту(або тексту) — є міра обчислювальних ресурсів, що необхідні для того, щоб точно визначити цей об'єкт.
Висловлює можливість фрактального опису.
Наприклад, розглянемо два рядки довжиною 64 символу, що містять тільки символи в нижньому регістрі і цифри:

abababababababababababababababababababababababababababababababab
4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf

Перший рядок має простий опис природною мовою, а саме ab 32 рази, що складається з 10 символів. Другий рядок не має очевидного простого опису з використанням того ж набору символів, крім власне самої цього рядка, довжина якої становить 64 символу.

Більш формально, складність рядка — це довжина опису цього рядка на деякій універсальній мові опису. Здатність складності до зміни стосовно вибору мови опису обговорюється нижче. Можна показати, що колмогорівська складність будь-якого рядка не може бути більшою кількох байт, ніж довжина самого цього рядка. Рядки, колгомівська складність яких слабко залежить від розміру самого рядка, не вважаються складними.

Означення

Щоб означити колгомівську складність, ми повинні спочатку задати мову опису рядків. Така мова опису може бути задана на будь-якій мові програмування, такій як Лісп, Паскаль або Джава-байт-код. Якщо ${\displaystyle P}$ — програма, що генерує рядок х, то ${\displaystyle P}$ — опис х. Довжиною опису є довжина P як рядка. Під час визначення довжини цілої константи ${\displaystyle n}$, яка з'являється в ${\displaystyle P}$ — це кількість бітів, що використовуються для запису ${\displaystyle n}$, (приблизно) log₂n.

Ми можемо альтернативно вибрати кодування для машини Тюринга, де кодування — функція, що встановлюється у відповідність кожній машині Тюринга M бітовий рядок <M> \langle М \rangle. Якщо М — машина Тьюринга, яка на вхід ω дає на виході рядок х, то об'єднана рядок \langle М \rangle ж є опис для х. Це теоретичний підхід, який є більш відповідним для побудови детальних формальних доказів і бажаний у дослідницькій літературі. Двійкове лямбда -числення може дати найбільш просте визначення складності. У цій статті ми використовуємо неформальний підхід.

Будь рядок с має як мінімум один опис, тобто програму

function GenerateFixedString()
   return s

Якщо опис s, d(s) мінімальної довжини тобто використовує найменшу кількість символів, то воно називається мінімальним описом s, а довжина d(s), то есть количество символов в этом описании, — колмоговська складність s, K(s). Символьно
K(s)=|d(s)|.

Розглянемо, як вибір мови опису впливає на значення K і покажемо, що ефект від зміни мови опису є обмеженим. Теорема. Якщо К₁ і К₂ — функції складності,що відносяться до мов опису L₁ i L₂ то існує константа с (залежна тільки від мов L₁ i L₂) така, що
для будь якого s |К₁(s)-К₂(s)|<=c.

Джерела

• Верещагин Н. К. Курс колмогоровской сложности.
• Верещагин Н. К., Шень В. А. Колмогоровская сложность и алгоритмическая случайность. — МЦНМО, 2013.
• Вьюгин В. В. Колмогоровская сложность и алгоритмическая случайность.