Коллектив авторов - Теорема Геделя о неполноте [Фейк]

Число ? представляет собой непознаваемую часть математики. Компьютерная программа конечной длины позволяет определить лишь конечное число битов этого числа; все последующие остаются во мраке неизвестности (изображение: www.sciam.ru)

Разумеется, запустив программу, вы можете со временем обнаружить, что она остановилась. Фундаментальная проблема заключается в том, чтобы решить, когда вы сдадитесь и престанете ждать, если программа не останавливается. Для множества частных случаев она может быть решена, но Тьюринг показал, что общего решения не существует. Никакой алгоритм и никакая математическая теория не позволят определить, какая программа остановится, а какая нет. (Современное доказательство данного положения Тьюринга можно найти на сайте Scientific American.) Кстати, употребляя слово ?программа? в современном смысле, я имею в виду совокупность самой компьютерной программы и данных, которые она обрабатывает.

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

Поскольку число ? выражает вероятность, оно должно быть больше нуля, но меньше единицы, т.к. некоторые программы останавливаются, а некоторые ? нет. Число ?, записанное в двоичном коде, будет иметь вид вроде 0,1110100... Последовательность битов после запятой неприводима, а сами они оказываются неприводимыми математическими фактами (каждый факт состоит в том, является ли данный бит нулем или единицей).

Как определяется число ?

Чтобы понять, как определяется число ?, рассмотрим упрощенный пример. Допустим, что из всех программ некоего компьютера останавливаются всего три, которые представляют собой 110, 11100 и 11110, длиной 3, 5 и 5 битов соответственно. Если для выбора программ мы будем бросать монету, чтобы определять значение каждого очередного бита случайным образом, вероятности получения каждой из них будут равны соответственно 1/23, 1/25 и 1/25, , поскольку вероятность получения единицы или нуля для каждого бита равна 1/2. Тогда вероятность останова программы для такого компьютера будет определяться выражением:

? = 1/23 + 1/25 + 1/25 = 0,001 + 0,00001 + 0,00001 = 0,00110.

Здесь двоичные числа выражают вероятность случайного выбора одной из трех останавливающихся программ. Поскольку программа 110 останавливается, мы не рассматриваем программы длиной больше трех битов, начинающиеся с 110, например, 1100 и 1101, т. е. мы не добавляем к сумме 0,0001 для каждой из них. Мы считаем все более длинные программы (1100 и т. д.) с таким началом включенными в программу 110, которая останавливается. Другими словами, данные программы являются самоограничивающимися, поскольку после их остановки последующие биты не запрашиваются.

Число ? можно определить как бесконечную сумму, и каждая программа длиной N битов вносит в нее свой вклад, равный ?N. Иными словами, каждая N-битовая программа, которая останавливается, добавляет единицу к N-ному биту двоичного представления числа ?. Сложив все биты, соответствующие остановившимся программам, мы можем получить точное значение ?. Создается впечатление, что ? можно вычислить точно, как √2 или ?. Однако это не так: число ? строго определено и имеет вполне конкретное значение, но рассчитать его невозможно, поскольку это позволило бы решить проблему останова, у которой действительно нет решения. Если говорить конкретнее, знание первых N битов числа ? позволяет определить, остановится ли когда-нибудь любая программа длиной до N битов, из чего следует, что для нахождения N битов числа ? требуется программа длиной не менее N битов. Заметьте, я не утверждаю, что нельзя определить некоторое число битов числа ?. Например, зная, что компьютерные программы 0, 10 и 110 останавливаются, мы можем говорить, что с точностью до первых трех битов ? имеет вид 0,111. Дело в том, что первые N битов ? нельзя вычислить с помощью программы, которая была бы существенно короче N битов.

Самое главное, что ? дает нам бесконечное число неприводимых битов. Любая программа конечной длины, сколько миллиардов битов она бы ни содержала, не поможет нам определить оставшиеся биты, которых бесконечно много. Иными словами, при любом конечном наборе аксиом мы имеем бесконечное число истин, которые не могут быть доказаны с помощью этого набора.

Почему число ? несжимаемо?

Попробуем доказать, что число несжимаемо, т. е. его первые N битов невозможно определить с помощью программы длиной существенно меньше N битов. Проанализируем свойства ? в свете поставленной Тьюрингом проблемы останова. Используем утверждение, что для программ длиной до N битов задача не может быть решена с помощью программы меньшей длины.

Для демонстрации несжимаемости числа ? покажем, что знание первых его N битов позволяет решить задачу Тьюринга для программ длиной до N битов. Из этого будет следовать, что никакая программа длиной меньше N битов не может вычислить первые N битов ?. (Если бы такая программа существовала, с ее помощью можно было бы вычислить первые N битов ?, а затем использовать их в решении задачи Тьюринга для программ длиной N битов ? задача невыполнимая с помощью столь короткой программы.)

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