?

Log in

No account? Create an account
Чайтин, парадокс Берри, элегантные программы, the halting problem - По делам сюда приплыл, а не за этим [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

Чайтин, парадокс Берри, элегантные программы, the halting problem [ноя. 21, 2002|11:22 pm]
Anatoly Vorobey
Почитал вчера немного Чайтина, которого несколько лет не касался, и то, что читал, успел забыть. Чайтин - математик, много лет занимающийся проблемами алгоритмической сложности (сложности Колмогорова) и доказавший много интересных результатов. На его домашней странице можно найти сетевые копии практически всех его работ, кстати - очень удобно.

Вот несколько лекций Чайтина, написанных для неспециалистов и дающих хороший обзор его подхода:
  • The Berry Paradox (простая и ясная, рекомендую начать с неё; сравнивает подход Чайтина с теоремой о неполноте Гёделя)
  • Information-Theoretic Computational Complexity (те же идеи, но больше истории предмета)
  • Paradoxes of Randomness - больше о числе Омега, меньше конкретных подробностей.

Первая статья объясняет первый красивый (и одновременно простой) результат Чайтина лучше всех, но в ней есть одна неточность и одно довольно-таки плохо объяснённое обстоятельство. Я вчера потратил некоторое время на то, чтобы всё себе уяснить, и раз уж сделал это, то перескажу это вкратце здесь. Таким образом, это нечто вроде моей версии мини-введения в темы, к-ми занимается Чайтин. Три основных результата, которых можно легко достичь с минимумом усилий - это невозможность док-ва случайности строки, невозможность док-ва элегантности программы, и альтернативное док-во невозможности решения проблемы остановки (the halting problem). Всё это объяснено и вкратце доказано ниже.


Итак, мы исследуем алгоритмическую сложность строк, состоящих из символов; для удобства будем использовать только символы 0 и 1, но это ограничение несущественно. Интуитивно понятно, что строка "11111111111" в каком-то смысле "проще", чем строка "10100101100". Но как это интуитивное понимание формализовать? Классическая теория алгоритмической сложности работает с бесконечными объектами: например, насколько сложно вычислить какую-то функцию f(n), где сложность выражается в виде времени вычисления и зависит от n - исходных данных. Классическая теория не может ответить на вопрос: "какова сложность строки 10001?" - этот вопрос в ней бессмысленен.

Колмогоров (и независимо от него Чайтин, по его утверждению) придумали следующее решение. Назовём сложностью строки символов минимальную длину программы, которая, если её запустить без каких-либо входных данных, напечатает на выходе данную строку. Длина программы, как и длина строки, измеряется в битах. Что такое "программа"? Для наглядности можно выбрать любой знакомый язык программирования и иметь в виду программы, написанные на этом языке.
При более строгом подходе нужно выбрать математическую модель компьютера - например, машину Тюринга; при этом "программа" - закодированное в виде двоичной строки описание машины Тюринга, а "бежит" эта программа на универсальной машине Тюринга (машине, которая умеет запускать любую другую машину Тюринга, данную ей в виде ввода).

Соль этого подхода в том, что чем более "закономерна" строка, тем короче можно написать программу для её вычисления. Пусть у нас есть строка длиной n символов; насколько короткой или длинной может быть самая короткая программа, выдающая эту строку на выходе? Во-первых, всегда можно просто ввести саму искомую строку внутрь программы, как бы "сохранить данные в виде кода"; тогда длина программы, печатающей строку, будет n+c, где c - какая-то постоянная константа: длина небольшой процедуры, которая проходит по сохранённой внутри самой программы строке и печатает её. Т.к. c - константа, мы видим, что для достаточно больших n максимальная сложность строки длиной n будет примерно n. Т.е. существенно больше n (например, хотя бы 2*n) она быть не может. Но сложность может быть и намного меньшей, чем n. Посмотрим, например, на строку, состоящую из n единиц. Это очень "простая" строка. Мы можем написать программу, её выдающую на выходе, следующим образом: программа просто бежит в цикле, и выдаёт одну единицу за другой, и делает это ровно n раз. При этом длина такой программы будет log(n)+c, где c - какая-то постоянная величина, константа, а log(n) отражает длину числа n, записанного внутри программы (программа должна "знать" число n, чтобы знать, когда остановиться; записать число n занимает log(n) двоичных знаков, где логарифм здесь и далее берётся по основанию 2. Почему логарифм? Потому что кол-во двоичных знаков, требующихся для записания числа n, как раз равно с точностью до округления log(n) ).

Для больших n сложность log(n)+c - намного меньше, чем n+c (наш верхний предел для сложности), так что здесь есть настоящее улучшение. Но не стоит полагать, что только очевидно "простые" строки можно таким образом выдать с помощью коротких программ. Например, посмотрим на строку, состоящую из миллиона (n=миллион) первых знаков числа пи, в двоичной записи. Несмотря на то, что она "выглядит" совершенно случайной, её сложность равна сложности строки, состоящей из одний единиц - log(n)+c. Это потому, что мы можем написать функцию для последовательного вычисляния числа пи (эта функция займёт число бит c - постоянная величина), и нам нужно будет только знать, после скольких знаков остановиться, т.е. опять-таки знать число n, что требует log(n) бит.

Следуя этой интуиции, согласно которой "закономерные" строки имеют меньшую сложность Колмогорова (т.к. их можно выдать с помощью более коротких программ, использующий их "закономерности"), назовём строку случайной, если её сложность больше или равна её длине, т.е. n. Случайные строки - это те строки, которые нельзя "сжать", используя их закономерности (ведь программу, выдающую строку, можно рассматривать в виде её "сжатого вида"). Довольно легко показать, что для каждого n подавляющее большинство строк длиной n - случайны. Интуитивно это можно увидеть так: ведь строк длиной n есть 2n (напомню, что мы рассматриваем только строки из двух символов). А программ длиной меньше n намного меньше, чем 2n. Это потому, что общее число двоичных строк длиной меньше n (всех строк длиной 0, 1, 2, ..., n-1) примерно равно 2n (точнее, оно равно 2n-1: например, 1+2+4+8+16=32-1). Но из этих строк далеко не все являются закодированными в двоичном виде программами; а из тех, которые являются, далеко не все кодируют программы, которые вообще при запуске когда-то останавливаются; а из этих далеко не все выдают на выходе именно строки длиной n. Этот аргумент можно записать более точно и добавить к нему ещё более убедительные подробности, но и так ясно, что большинству из 2n разных строк длиной n придётся довольствоваться минимальными программами длиной примерно n или больше n, чтобы их выдать на выходе; просто нет достаточного количества коротких программ!

Итак, случайных, "несжимаемых" строк - очень много, на самом деле подавляющее большинство. Но понятно, с другой стороны, что доказать, что какая-то конкретная строка действительно случайна - задача не из лёгких. Предположим, вам дают какую-то строку длиной миллион символов. Как теперь проверить, есть "короткая" программа для её вычисления, или нет? Может быть, эти миллион символов - как раз знаки числа пи, и тогда эта программа есть (см. выше). А если нет, может быть, это миллион знаков какой-то другой легко вычислимой математической константы, и поди их все проверь. Или же это может быть какое-то лёгкое видоизменение другой "закономерной" строки (напр. знаки числа пи, но к каждой цифре прибавили 1); как все такие возможности отследить?

Ясно, что "случайность" какой-то конкретной строки доказать сложно. Но Чайтин показал большее - он показал, что по сути дела в большинстве случаев это сделать невозможно.

Его доказательство является остроумной формализацией известного парадокса Берри. Парадокс Берри обычно формулируют так. В русском языке есть всего конечное кол-во фраз, состоящих не более чем из ста слов, которые описывают какое-то конкретное натуральное число. Например, число 25 можно описать так: "двадцать пять", а можно так: "пять в квадрате" итп. Но т.к. кол-во слов в языке конечно, кол-во фраз из не более ста слов тоже конечно, хоть и очень велико, а значит, все эти фразы могут описать только конечное кол-во натуральных чисел. Тогда есть числа, к-е описать с помощью фразы из менее ста слов невозможно; среди этих чисел есть минимальное - минимальное число, которое невозможно описать фразой из не более ста слов. Но вот я его только что описал при помощи выделенной фразы в прошлом предложении - и эта фраза занимает менее ста слов. Парадокс.

Вот каким образом Чайтин применяет идею парадокса Берри к алгоритмической сложности строк. Возьмём какую-то математическую формальную систему, в которой мы можем формальным образом доказывать математические теоремы. Например, в качестве такой системы можно взять теорию множеств, и тогда, как известно, практически всю современную математику можно описать в рамках этой формальной системы. Т.е. у нас есть некоторое количество аксиом и дедуктивных правил, и любую теорему можно доказать при помощи формального доказательства - последовательности строк, в которой каждая строка - либо аксиома, либо получена из предыдущих строк при помощи одного из дедуктивных правил; а последняя строка - искомая теорема. В принципе практически любой результат современной математики можно таким образом доказать из аксиом теории множеств при помощи формального доказательства (хотя на практике такие доказательства столь велики и неудобны, что математики всегда используют более удобные и адекватные методы рассуждений, которые, однако, в принципе можно формализовать).

В выбранной нами формальной системе (которая, напомню, заключает в себе возможности современной математики) можно, наверное, доказать какие-то утверждения типа "строку X невозможно вычислить с помощью программы длиной не больше N бит". Для того, чтобы это утверждение прояснить, нужно понять, как формально выглядит это утверждение. Но это сделать довольно легко; например, можно формализовать утверждение, которые выглядит так:
"для любой строки длиной меньше, чем N, верно, что если эта строка кодирует какую-то машину Тюринга, и если эта машина при запуске в конце-концов останавливается и выдаёт на выходе какую-то строку, то та строка, которую она выдаёт на выходе, не тождественна X"

Легко видеть, что это утверждение как раз и означает, что сложность строки X равна как минимум N (или больше); а его уже легко формализовать более подробно - я этим не буду заниматься. В результате такой формализации мы получим формальное утверждение φX,N, которое означает "сложность X больше или равна N"; φX,N зависит от X и N.

Итак, для каких-то строк X и чисел N наша формальная система может доказать φX,N. Например, предположим, что длина любой программы - как минимум 20 двоичных символов (которые нужны, чтобы закодировать какой-то минимум необходимой информации про программу). Тогда тривиально можно доказать, что для любой строки X её сложность больше или равна 20; если мы это можем тривиально доказать сами, то существует и формальное доказательство в нашей системе (потому что она формализует всю силу современной математики).

Чайтин, однако, доказал следующий замечательный результат: есть какое-то число N, так что наша формальная система не может доказать ни для какой строки, что её сложность больше или равна N. Например, если N=миллион, это значит, что мы не можем в принципе найти ни одной строки, сложность которой больше или равна миллиону. В частности, мы не можем найти ни одной случайной строки длиннее миллиона символов (т.к. сложность случайной строки больше её длины). Результат Чайтина накладывает, таким образом, очень строгие ограничения на нашу возможность доказывать случайность строк; мы можем это делать до какой-то длины, но не больше - дальше сколько мы ни будем биться, какие бы сложные матматические методы мы ни использовали, всё равно никогда не докажем.

Как же это доказать? Собственно, осталось уже немного.

Предположим, что для какого-то числа N мы можем доказать в нашей формальной системе утверждения вида φX,N, для каких-то строк X. Т.е. для каких-то строк X мы можем показать, что их сложность больше или равна N, при помощи формального доказательства. Из всех таких строк X выберем ту, для которой соответствующее формальное доказательство самое короткое. Назовём эту строку X0.

Теперь напишем программу, которая ведёт себя следующим образом. Она перебирает одну за другой все строки длиной 1, потом длиной 2, потом длиной 3 итп. Для каждой такой строки программа проверяет, не является ли она двоичным представлением формального доказательства в нашей системе (это сделать легко); и если является, то программа проверяет корректность этого формального доказательства, тот факт, что оно действительно составлено "по правилам"; и если это так, то наша программа проверяет, что за теорему это доказательство доказывает (для этого она попросту смотрит на последнюю строку в цепочке доказательства). Когда она находит док-во, доказывающее утверждение вида φX,N для любой строки X и нашего заданного N, то программа останавливается и печатает на выходе это X.

Легко видеть, что эта программа напечатает строку X0, просто по определению этой строки (т.к. именно её док-во - самое короткое из всех доказательств φX,N для заданного N - она найдёт первым). Эта наша программа - аналог фразы "наименьшее число, к-е невозможно определить при помощи не более ста слов" в парадоксе Берри.

(тут есть крохотная техническая тонкость: что если есть несколько строк с одинаковой минимальной длиной доказательств φX,N? Тогда в качестве X0 мы выберем ту из них, которая меньше других в каком-то заранее выбранном порядке; а программу модифицируем так, чтобы она сначала проверяла все док-ва данной длины, и если есть несколько док-в, доказывающих φX,N для разных X, чтобы печатала наименьшее из этих X в том же порядке. Тогда мы всё равно добъёмся того, что программа напечатает X0 - это то, что нам нужно)

Какова длина нашей программы? В ней есть только одно данное переменной длины - а именно, число N, для записи которого требуется log(N) бит. Все остальные её части - часть, генерирующая все возможные строки, часть, проверяющая, что строка кодирует доказательство, и часть, проверяющая, не доказывает ли это док-во утверждение типа φX,N - все они вместе имеют какую-то постоянную длину c, зависящую от нашей формальной системы (внимание: строка X не является частью программы!) Только запись числа N надо варьировать, если мы его меняем. Поэтому длина нашей программы - log(N)+c.

Но наша программа печатает число X0, сложность которого по определению больше N (у нас есть формальное доказательство этого!). Если N настолько велико, что N > log(N)+c (а для достаточно больших N это будет выполняться), мы получаем противоречие: сложность строки X0 больше N, но у нас есть программа длиной меньше N, которая его печатает.

Единственный выход из такого противоречия для таких больших N - это признать, что не существует ни одного формального доказательства утверждения вида φX,N; то есть, невозможно доказать ни для одной строки, что её сложность больше N. Потому что если хотя бы для одной строки такое док-во существовало, мы могли бы определить X0 и придти к вышеозначенному противоречию.

Это и есть искомый результат Чайтина, ограничивающий в принципе нашу возможность доказывать, что сложность строки больше какого-то N; и в частности, ограничивающий в принципе нашу возможность доказывать случайность строк.

Окончание следует позже, ибо устал.
СсылкаОтветить

Comments:
From: squadette
2002-11-21 01:58 pm
"Вот каким образом Чайтин применяет идею парадокса Чайтина к алгоритмической сложности строк. "

парадокс придумал Берри, а памятник поставили Чайтину.
(Ответить) (Thread)
[User Picture]From: avva
2002-11-21 02:04 pm

Ох, я это писал так быстро, что буду рад, если все ошибки окажутся столь же тривиальными.
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2002-11-21 03:03 pm

Хорошо излагаешь.
(Ответить) (Thread)
[User Picture]From: avva
2002-11-22 05:25 am

Спасибо!
(Ответить) (Parent) (Thread)
[User Picture]From: malaya_zemlya
2002-11-21 09:04 pm
Я вот чего не понимаю:
В стате про парадокс Берри, Чайтин приводит сворй знаменитый результат с числом Омега

2. Consider the binary representation of the halting probability Omega, which is the probability that a program chosen at random halts. You can't prove what one of the bits of Omega is. More precisely, N bits of axioms are needed to be able to determine N bits of Omega.

А потом говорит следующее:
Results (2) and (3) are extreme cases. They are accidental mathematical assertions that are true for no reason at all. In other words, the questions considered in (2) and (3) are irreducible; essentially the only way to prove them is to assume them as new axioms. So in this extreme case, what you get out of a set of axioms is only what you put in.

Но ведь Чайти сам-то догадался про эти резльтаты! Не ангелы ему нашептали, А даже если и ангелы... другим он его объяснил и многие из них поняли и согласились.
Это что, доказательство неалгоритмизируемости человеческого мышления в стиле Роджера Пенроуза или я что-то не так понял? Или факт существования Омеги доказуем в в какой-то более-менее приличной формальной системе, а только само значание Омеги - нет?
(Ответить) (Thread)
[User Picture]From: avva
2002-11-22 02:09 am
Или факт существования Омеги доказуем в в какой-то более-менее приличной формальной системе, а только само значание Омеги - нет?

Именно так. Доказать существование Омеги не представляет особой сложности; доказать конкретное значение Омеги - даже в виде приближения, напр. определить первые несколько знаков - невозможно без привлечения новых аксиом.
(Ответить) (Parent) (Thread)
[User Picture]From: malaya_zemlya
2002-11-25 01:47 pm
Ок. По поводу Омеги.. Чайтин долго и тщательно выписывает алгоритм нахождения omega(n,t) то есть вероятности, что n-битная программа остановится за t шагов, даже приводит соответствующую программу на LISPe. Потом он устремляет эти параметры к бесконечности.

Неясно, почему эта последовательность вообще должна к чему-то сходится. Я написал простейший тест на Си с самым минимальным набором команд. Судя по результатам, omega(n,t) действительно более-менее возрастает с ростом числа битов, но не совсем монотонно. Так, что утверждение о существовании предела нужно как-то обосновать. Если взять случайную останавливающуюся программу и в конце нее дописать несколько битов, то она может и перестать останавливаться.


(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-11-25 03:05 pm

Re:

Честно говоря, тут мне просто нечего ответить. Я не читал соотв. текстов Чайтина года 4 где-то, и просто не помню, как именно он аргументирует определение омеги, а сейчас пока до этого руки не дошли. Надеюсь, что дойдут в ближайшем будущем, но, увы, не уверен.
(Ответить) (Parent) (Thread)
[User Picture]From: malaya_zemlya
2002-11-25 04:40 pm

Re:

Спасибо. Уже нашел ответ на свой вопрос - в A century of controversy over the foundations of mathematics.

Самый простой способ (немного отличающийся от исконно Чайтинского, но несущественно) обойти вопросы о сходимости:

omega = Сумма 2^(-|p|-1)

где сумма берется по всем останавливающимся программммам p, а |p| - это длина программы p в битах.

Тогда сразу видно, что эта последовательность неубывающая и ограниченная сверху числом 1. Значит сходится.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2002-11-22 05:31 am

"Интуитивно это можно увидеть..."

Интуитивно не получается...

..."программа" - закодированное в виде двоичной строки описание машины Тюринга, а "бежит" эта программа на универсальной машине Тюринга (машине, которая умеет запускать любую другую машину Тюринга, данную ей в виде ввода)... А программ длиной меньше n намного меньше, чем 2^n...

Всё это верно для ОДНОЙ универсальной машины Тьюринга. Если универсальных машин Тюринга не одна, то количество программ мб больше 2^n. Но это так, мелкая придирка. Очень интересно почитать продолжение.

И ещё. Всё же очень режет слух использование слова "случайная". Далось это слово Колмогорову... Назвал бы просто: "сложная".
(Ответить) (Thread)
[User Picture]From: avva
2002-11-22 05:33 am

Re: "Интуитивно это можно увидеть..."

Всё это верно для ОДНОЙ универсальной машины Тьюринга. Если универсальных машин Тюринга не одна, то количество программ мб больше 2^n.

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

Продолжение скоро будет.
(Ответить) (Parent) (Thread)
[User Picture]From: averros
2002-11-25 01:17 am
В общем-то утверждение о невозможности доказательства случайности - совсем не-интуитивно только потому что интуиция (точнее, pattern recognition) у человека довольно специфично настроено на вполне ограниченный класс структур. Всё, что не попадает в этот класс просто сваливается в "случайно".

Эксперименты некого Вольфрама с клеточными автоматами вполне показывают, что даже 1D автоматы с очень простыми правилами могут генерировать неожиданно "случайные" строки. (А также то, что эквивалент машины Тьюринга вполне можно сделать из бинарного 1D автомата, зависящего только от соседних клеток :)

В общем-то тот же результат об алгоритмическом сжатии строк можно получить, просто рассмотрев представление omega number (определяемого как предел отношения количества останавливающихся машин Тьюринга ко всем машинам Тьюринга с длиной описания менее N бит, при N->inf) в виде строки. Это число нельзя вычислить (хотя можно получать оценки сверху) - соответственно, оно не имеет Колмогоровской сложности вообще :)
(Ответить) (Thread)
From: iliat
2002-11-28 05:44 pm

Пасиб!

Толик , у тебя есть очень редкий дар: доходчиво обьяснять сложные вещи.
Может ввести "Vorobey's complexity", как оценку сложности научных концепций
(т.е. длина самого доходчивого обьяснения) ?
П.С. Хотел бы я прочитаь учебник по теории множеств, написанный тобой.
(Ответить) (Thread)
[User Picture]From: alex_vinokur
2007-01-20 04:14 pm

Huffman coding and Turing machine

Занимались ли Вы связью между сжатием (в частности, кодами Хаффмэна) и машиной Тьюринга? Чайтин уделил этому некоторое внимание:
http://groups.google.com/groups?th=6fad94515647d76c
http://www.cs.umaine.edu/~chaitin/turing.html

(Ответить) (Thread)
[User Picture]From: yakov_sirotkin
2008-05-30 02:34 pm
Прошу прощения за комментарий к столь почтенному посту, но я тут почитал статью мэтра и нашёл там такие строки: But for any computational task, once you fix the computer programming language, once you decide on the computer programming language, and if you have in mind a particular output, there's got to be at least one program that is the smallest possible. There may be a tie, there may be several, right?, but there's got to be at least one that's smaller than all the others. But you can never be sure that you've found it!

Я, кончено, идиот, но по-моему мы можем тупо перебрать все программы длины не больше, чем у найденной и посмотреть, какой у них будет вывод.
(Ответить) (Thread)
[User Picture]From: avva
2008-06-01 02:05 am
В общем случае не можем, потому что некоторые из них могут не останавливаться, а мы это, возможно, не сможем распознать.
(Ответить) (Parent) (Thread)
[User Picture]From: yakov_sirotkin
2008-06-01 05:22 am
Это мы на машине Тьюринга не можем, а у реальной машины конечное число состояний.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2008-06-01 05:40 am
У машины Тьюринга тоже конечное число состояний - это лента у нее бесконечная. Не вполне понимаю ваше возражение.
(Ответить) (Parent) (Thread)