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

  • Клаус Барби, Лионский палач

    Ехали мимо Лиона, у дороги стоит очередной туристический указатель: Les enfants d’Izieu. Нам это словосочетание ни о чём не говорило, полезли…

  • Подсчёт голосов на выборах

    Вчера у нас были выборы, сразу на уровне департамента и региона. Я сходил проголосовать (Анюта в Германии, доверенностью мы не занялись), на месте…

  • Демография Франции 2020 года

    Был вчера на работе, за обедом разговорились о рождаемости: у коллеги летом будет ребёнок, он ищет место в яслях, надеется, что спад рождаемости…

  • 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