green_fr (green_fr) wrote,
green_fr
green_fr

Categories:

Pour la Science (№ 405) — описательная сложность

Статья о сложности Колмогорова*. В двух словах, последовательность бит тем сложнее, чем длиннее самая короткая программа, способная воспроизвести ту последовательность.
Очевидно, что выбор языка программирования с какого-то размера последовательностей перестаёт играть существенную роль.
А вот для маленьких последовательностей разброс получается существенный.

Для них можно определить сложность немного по-другому: сложность Соломонова**-Левина.
Определяется следующим образом: возьмём случайную последовательность бит. Запустим её как программу.
Если она зависла — переходим к следующей случайной последовательности.
Если не зависла — запишем то, что она вывела на экран.
Запустив достаточное количество таких случайных программ, мы сможем оценить вероятность выпадания той или иной последовательности. Эта вероятность обратно пропорциональна сложности.

Я очень долго втыкал, каким образом вероятность у двух последовательностей может быть разной.
В конце концов понял, но пересказать не смогу, статья на французском, могу отсканировать.

* Красивый пример гипер-коррекции: французское Kolmogorov я перевёл назад на русский как «Холмогоров» :-)
** Тоже вопрос с переводом: Ray Solomonoff, конечно, сын русских эмигрантов, но его родителей звали Phillip Julius и Sarah Mashman Solomonoff — я не уверен, как надо писать его фамилию. А русская Викпиедия о нём пока что не знает.


Затем описание программы, которая всё это считает, через машины Тьюринга.

Понравился термин «Castor affairé à n états» (занятой бобёр с n состояниями) — применяется к машине Тьюринга в n состояний, которая работает дольше остальных своих коллег до полной остановки (при условии, что остановка вообще будет). На практике используют для определения (и отключения) «зависших» машин.

А ещё — нумерология в действии — машин Тьюринга с двумя состояниями существует ровно 10 000. Для того, чтобы оценить «круглость» числа: с тремя состояниями их 7 529 526, с четырьмя — 11 019 960 576.
Tags: pour la science
Subscribe

  • Михаил Сегал

    Посмотрел недавно (спасибо, Самуил!) фильм Рассказы и сразу влюбился в режиссёра. Вот бывает такое (у меня буквально пару раз в жизни бывало), когда…

  • Black mirror

    На France Culture когда-то рассказали про очередной сериал (предыдущий мой улов там был  Le bureau des légendes). По описанию настолько захотелось…

  • Инверсия добра и зла

    Писал про «Инферно», упустил интересный момент. Там сюжет крайне актуальный: злодей пытается заразить всю планету неведомым науке вирусом. Мотивация…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 3 comments