![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
green_frСтатья о сложности Колмогорова*. В двух словах, последовательность бит тем сложнее, чем длиннее самая короткая программа, способная воспроизвести ту последовательность.
Очевидно, что выбор языка программирования с какого-то размера последовательностей перестаёт играть существенную роль.
А вот для маленьких последовательностей разброс получается существенный.
Для них можно определить сложность немного по-другому: сложность Соломонова**-Левина.
Определяется следующим образом: возьмём случайную последовательность бит. Запустим её как программу.
Если она зависла — переходим к следующей случайной последовательности.
Если не зависла — запишем то, что она вывела на экран.
Запустив достаточное количество таких случайных программ, мы сможем оценить вероятность выпадания той или иной последовательности. Эта вероятность обратно пропорциональна сложности.
Я очень долго втыкал, каким образом вероятность у двух последовательностей может быть разной.
В конце концов понял, но пересказать не смогу, статья на французском, могу отсканировать.
* Красивый пример гипер-коррекции: французское Kolmogorov я перевёл назад на русский как «Холмогоров» :-)
** Тоже вопрос с переводом: Ray Solomonoff, конечно, сын русских эмигрантов, но его родителей звали Phillip Julius и Sarah Mashman Solomonoff — я не уверен, как надо писать его фамилию. А русская Викпиедия о нём пока что не знает.
Затем описание программы, которая всё это считает, через машины Тьюринга.
Понравился термин «Castor affairé à n états» (занятой бобёр с n состояниями) — применяется к машине Тьюринга в n состояний, которая работает дольше остальных своих коллег до полной остановки (при условии, что остановка вообще будет). На практике используют для определения (и отключения) «зависших» машин.
А ещё — нумерология в действии — машин Тьюринга с двумя состояниями существует ровно 10 000. Для того, чтобы оценить «круглость» числа: с тремя состояниями их 7 529 526, с четырьмя — 11 019 960 576.
Очевидно, что выбор языка программирования с какого-то размера последовательностей перестаёт играть существенную роль.
А вот для маленьких последовательностей разброс получается существенный.
Для них можно определить сложность немного по-другому: сложность Соломонова**-Левина.
Определяется следующим образом: возьмём случайную последовательность бит. Запустим её как программу.
Если она зависла — переходим к следующей случайной последовательности.
Если не зависла — запишем то, что она вывела на экран.
Запустив достаточное количество таких случайных программ, мы сможем оценить вероятность выпадания той или иной последовательности. Эта вероятность обратно пропорциональна сложности.
Я очень долго втыкал, каким образом вероятность у двух последовательностей может быть разной.
В конце концов понял, но пересказать не смогу, статья на французском, могу отсканировать.
* Красивый пример гипер-коррекции: французское Kolmogorov я перевёл назад на русский как «Холмогоров» :-)
** Тоже вопрос с переводом: Ray Solomonoff, конечно, сын русских эмигрантов, но его родителей звали Phillip Julius и Sarah Mashman Solomonoff — я не уверен, как надо писать его фамилию. А русская Викпиедия о нём пока что не знает.
Затем описание программы, которая всё это считает, через машины Тьюринга.
Понравился термин «Castor affairé à n états» (занятой бобёр с n состояниями) — применяется к машине Тьюринга в n состояний, которая работает дольше остальных своих коллег до полной остановки (при условии, что остановка вообще будет). На практике используют для определения (и отключения) «зависших» машин.
А ещё — нумерология в действии — машин Тьюринга с двумя состояниями существует ровно 10 000. Для того, чтобы оценить «круглость» числа: с тремя состояниями их 7 529 526, с четырьмя — 11 019 960 576.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2011-07-07 08:27 am (UTC)у меня Чака Паланика называть Палаником язык еле поворачивается: какой же он Паланик, если он Палагнюк (с украинским "г")(Palahniuk)?.. :-)
Флорыщак, опять же...
no subject
Date: 2011-07-07 09:14 am (UTC)Это вообще крайне интересная тема. Меня всегда ужасно интересует компрессия, в частности я пытался даже написать программу сжатия числа любой длины до нескольких байт, используя заранее известную бесконечную последовательность (например, пи). Ничего не вышло, правда :)
no subject
Date: 2011-07-07 12:47 pm (UTC)Но со сжатием там проблема принципиальная, ведь нельзя сделать алгоритм, который гарантированно сжимал бы любую последовательность. То есть с пи индекс часто будет длиннее, чем исходная последовательность.