UK 
English
Polski
Español
Deutsch
日本語
Italiano
Português (BR)
Français
العربية
Nederlands
中文
한국어
हिन्दी
Türkçe
Tiếng Việt
Русский
Bahasa Indonesia
فارسی
বাংলা
ไทย
Filipino
Kiswahili
اردو
Bahasa Melayu
தமிழ்
עברית
Ελληνικά
ਪੰਜਾਬੀ
አማርኛ
မြန်မာဘာသာ
ខ្មែរ
ქართული
नेपाली
Монгол хэл
Հայերեն
සිංහල
ລາວ
Čeština
Română
Magyar
Български
Svenska
Dansk
Suomi
Norsk
Slovenčina
Hrvatski
Српски
Slovenščina
Lietuvių
Latviešu
Eesti
Íslenska
Shqip
Македонски
Bosanski
Malti🧮 Складність Колмогорова: найкоротший опис
Стисніть бітовий рядок наживо за допомогою справжнього алгоритму у стилі LZ77 і використовуйте довжину стиснення як чесний, обчислюваний проксі верхньої межі для (доведено необчислюваної) складності Колмогорова.
Про складність Колмогорова
Складність Колмогорова K(x) рядка x, формалізована незалежно Реєм Соломоновим, Андрієм Колмогоровим і Грегорі Чейтіним, — це довжина найкоротшої програми, яка виводить x на фіксованій універсальній машині. Рядок на кшталт тисячі повторень "01" має низьку K(x): крихітна програма («вивести 01, 500 разів») породжує його. Рядок, що виглядає як результат кидків чесної монети, зазвичай має K(x), близьку до власної довжини, оскільки коротшого опису, ніж сам рядок, не існує. Найважливіше: K(x) доведено необчислювана — наслідок, тісно пов'язаний із проблемою зупинки: жоден алгоритм не може взяти довільний рядок і вивести його справжню мінімальну довжину програми, оскільки такий алгоритм можна було б використати для виявлення програм, що не зупиняються, коротших за будь-яку задану межу.
Оскільки справжня величина недосяжна, ця симуляція використовує справжню, чесно позначену обчислювану заміну: спрощений компресор LZ77 з фіксованою шириною, який реально працює з будь-яким бітовим рядком, який ви йому дасте. Він ковзає вікном назад по рядку, знаходить найдовший раніше бачений збіг у кожній позиції й випромінює реальний потік буквальних токенів і токенів збігів. Отримана кількість бітів — справжня верхня межа K(x) — ніколи не справжнє значення, і ніколи не доведено точна — але цього достатньо, щоб зробити основну інтуїцію конкретною: структуровані рядки стискаються сильно, а рядки, що виглядають випадковими для цього компресора, майже не стискаються.
Часті запитання
Що таке складність Колмогорова насправді?
K(x) — це довжина в бітах найкоротшої програми, яка, виконана на фіксованому універсальному комп'ютері (фіксованій еталонній машині), виводить рядок x і зупиняється. Це властивість самого рядка, а не якогось конкретного компресора — але вона може бути визначена лише відносно вибору машини, і різні машини змінюють K(x) щонайбільше на адитивну константу (теорема інваріантності).
Чому складність Колмогорова необчислювана?
Якби якийсь алгоритм міг обчислити K(x) для будь-якого x, ви могли б використати його, щоб знайти для будь-якого n найкоротший рядок, складність якого доведено перевищує n — але опис «найкоротшого рядка зі складністю, більшою за n» сам є коротким описом нібито нестисливого рядка, суперечність, відома як строго формалізований парадокс Беррі. Формально, обчислення K(x) дало б змогу розв'язати проблему зупинки, що неможливо. Це справжній, фундаментальний результат про нерозв'язність, а не інженерне обмеження, яке могло б виправити швидше обладнання.
Якщо K(x) необчислювана, що насправді демонструє ця симуляція?
Вона демонструє справжній, обчислюваний проксі: довжину виводу реального алгоритму стиснення (спрощеного LZ77), що працює з вашим рядком прямо зараз, у вашому браузері. Коротка стиснена довжина — вагомий доказ низької складності: програма, яка відновлює стиснені токени, сама є коротким валідним описом. Довга стиснена довжина — набагато слабший доказ: вона лише показує, що цей конкретний компресор не знайшов структури, яку можна використати, а не те, що коротшого опису не існує взагалі.
Чому "структурований" пресет Туе-Морса не стискається так сильно, як повторюваний пресет?
Послідовність Туе-Морса (біт n = парність кількості одиниць у двійковому представленні n) має крихітне рекурсивне породжувальне правило, тому її справжня складність Колмогорова дуже низька — але вона навмисно вільна від перекриттів і за побудовою уникає довгих повторюваних пробігів. Компресор LZ77 зі змінним вікном переважно зіставляє буквальні підрядки, тому він лише частково використовує цю структуру. Це чесне обмеження проксі: низька складність не гарантує, що якийсь конкретний компресор її знайде.
Чому випадковий пресет майже не стискається?
Кожен біт вибирається незалежно за допомогою Math.random(), тому в середньому немає повторюваного підрядка, який могло б використати ковзне вікно, окрім того, що очікується випадково в короткому вікні. Довжина виводу LZ77 залишається близькою до початкової довжини, що є саме такою поведінкою, яка очікується від колмогоровсько-випадкового (або алгоритмічно випадкового) рядка: істотно коротшого опису не існує.
Чи справді Math.random() випадковий?
Ні — це детермінований генератор псевдовипадкових чисел, зерно для якого браузер задає внутрішньо. Для цілей цієї демонстрації він статистично поводиться як незалежні кидки монети й є прийнятною практичною заміною; філософськи «справді випадкове» джерело потребувало б фізичного процесу, такого як радіоактивний розпад чи квантовий шум вимірювання.
Як тут насправді обчислюється стиснена довжина в бітах?
Кодер випромінює послідовність токенів: або буквальний біт, або посилання (зі зміщенням, довжиною) назад на раніше знайдений відповідний пробіг (мінімальна довжина збігу 3, максимальне вікно 48 бітів, максимальний збіг 32 біти). Кожен токен коштує один прапорцевий біт плюс або один буквальний біт, або фіксовану кількість бітів для полів зміщення й довжини, розміреність яких відповідає межам вікна й збігу. Сума цих витрат дає реальну, чесно обчислену довжину закодованих бітів — спрощений родич стадії LZ77 всередині DEFLATE (ZIP, gzip, PNG).
Чи завжди кращий компресор наближається до справжньої K(x)?
Кращий, розумніший компресор (арифметичне кодування, більші вікна, контекстне моделювання або повний перебір коротких програм) загалом знайде більше структури й дасть тісніші верхні межі. Але жодна скінченна родина компресорів не може довести, що досягає K(x) точно для будь-якого входу, оскільки це означало б обчислення самої необчислюваної функції. Кожен реальний компресор, хоч би яким гарним він був, завжди дає лише ще одну верхню межу.
Який зв'язок між складністю Колмогорова та ентропією Шеннона?
Ентропія Шеннона вимірює середній інформаційний вміст символів, узятих з відомого розподілу ймовірностей — статистичну величину на рівні розподілу. Складність Колмогорова вимірює інформаційний вміст одного конкретного, окремого рядка, без жодного посилання на розподіл. Для довгих рядків, породжених незалежно й однаково розподілено з джерела, очікувана складність Колмогорова на символ збігається до швидкості ентропії джерела, пов'язуючи ці дві ідеї, не роблячи їх тотожними.
Стисніть бітовий рядок наживо за допомогою справжнього алгоритму у стилі LZ77 і використовуйте довжину стиснення як чесний, обчислюваний проксі верхньої межі для доведено необчислюваної складності Колмогорова.
2D · HTML5 Canvas 2D · ціль 60 FPS · працює повністю на стороні клієнта, без встановлення