Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

Чайтин, парадокс Берри, элегантные программы, the halting problem

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

Вот несколько лекций Чайтина, написанных для неспециалистов и дающих хороший обзор его подхода:
  • 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; и в частности, ограничивающий в принципе нашу возможность доказывать случайность строк.

Окончание следует позже, ибо устал.
Subscribe
  • Post a new comment

    Error

    default userpic

    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.
  • 18 comments