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

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

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

abababababababababababababababababababababababababababababababab 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf 

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

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

Визначення

Щоб визначити колгомівську складність, ми повинні спочатку задати мову опису рядків. Така мова опису може бути задана на будь-якій мові програмування, такій як Lisp, Паскаля або Java- байт -код. Якщо P - програма, результатом якої є рядок х, то P - опис х. Довжиною опису є довжина P як рядка. У ході визначення довжини P довжини підпрограм, що використовуються в P, повинні бути обчислені. Довжина будь-якої цілої константи n, яка з'являється в P, це кількість біт, потрібних для подання 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.
• Вьюгин В.В. Колмогоровская сложность и алгоритмическая случайность.