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

Число ?

Первый шаг к открытию числа ? был сделан в знаменитой статье, опубликованной ровно через 250 лет после издания эссе Лейбница. В 1936 году на страницах ?Трудов Лондонского математического общества? (Proceedings of the London Mathematical Society) Алан Тьюринг впервые представил математическую модель простой универсальной вычислительной машины. Кроме того, он задался вопросом: можно ли определить, остановится когда-нибудь компьютерная программа или нет? Так была сформулирована знаменитая проблема останова.

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