овив свою работу.
Чтобы показать, что эту так называемую проблему остановки (проблему останова) невозможно решить в принципе, запустим программу на машине Тьюринга, которая представляет собой математическую идеализацию цифрового компьютера, не ограниченную временем. (Программа должна быть самоподдерживающейся – все данные должны поступать из самой же программы.) Далее зададимся простым вопросом: будет ли программа работать вечно или же наступит момент, когда она скажет «я закончила» и остановит работу?
Тьюринг продемонстрировал: для того, чтобы заранее определить, остановится ли когда-нибудь та или иная конкретная программа, не существует никакого набора инструкций, которые можно ввести в компьютер, никакого алгоритма. Непосредственно отсюда как раз и вытекает гёделевская теорема о неполноте: если нет механической процедуры для разрешения проблемы остановки, то нет и набора соответствующих аксиом, обладающих полнотой. Если бы они существовали, они дали бы нам механическую процедуру перебора всех возможных доказательств того, остановятся ли программы (хотя это, разумеется, заняло бы долгое время).
Чтобы сделать свой вывод о случайности в математике, я просто взял результат Тьюринга и изменил его формулировку. Получился своего рода математический каламбур. Хотя проблема остановки нерешаема, можно рассмотреть вероятность того, остановится ли когда-нибудь случайно выбранная программа. Начнем с мысленного эксперимента, где используется обычный компьютер «общего назначения», который, если дать ему достаточно времени, способен проделать работу любого компьютера. Иными словами, это универсальная машина Тьюринга.
Не станем спрашивать, остановится ли конкретная программа. Лучше рассмотрим совокупность всех возможных компьютерных программ. Каждой из них придадим определенную вероятность того, что именно ее выберут. Каждый бит информации в случайно выбираемой программе определяется путем подбрасывания монетки, причем для каждого бита этот бросок – независимый. Тогда для программы, содержащей N бит информации, вероятность того, что ее выберут, равна 2-N. Теперь зададимся вопросом, какова общая вероятность того, что эти программы остановятся. Она, эта вероятность остановки, обозначаемая как «омега» (Ω), позволяет ответить на вопрос Тьюринга о том, остановится ли программа, одним-единственным числом от 0 до 1. Если программа никогда не останавливается, Ω = 0. Если же программа всегда останавливается, Ω = 1.
Точно так же, как компьютеры выражают числа двоичной записью, мы можем выразить «омегу» цепочкой нулей и единиц. Можно ли заранее определить, каким будет N-й бит в этой цепочке цифр – нулем или единицей? Иными словами, можно ли вычислить «омегу»? О нет. Более того, я даже могу показать, что эта последовательность нулей и единиц носит случайный характер. Это можно сделать, используя так называемую алгоритмическую теорию информации, которая приписывает ту или иную степень упорядоченности набору данных в зависимости от того, существует ли алгоритм, способный сжать эти данные, представив их в более краткой форме.
К примеру, цепочку регулярно чередующихся нулей и единиц, описывающую какие-то данные как 0101010101… и состоящую в общей сложности из тысячи знаков, можно сжать в более короткую инструкцию: «Повторить „01“ 500 раз». А вот совершенно случайную цепочку цифр нельзя свести к более короткому тексту-программе. Такие цепочки называют алгоритмически несжимаемыми.
Как показывает мой анализ, вероятность остановки является алгоритмически случайной. Ее нельзя сжать, представив как более короткую инструкцию. Чтобы получить на выходе N бит этого числа, необходимо ввести в компьютер программу длиной по меньшей мере N бит. Каждый из N бит «омеги» – несократимый независимый математический факт, такой же случайный, как и результат подбрасывания монетки. К примеру, в «омеге» столько же нулей, сколько и единиц. Но знание всех ее четных бит не поможет нам узнать никакие из ее нечетных бит.
Мой вывод, что вероятность остановки носит случайный характер, согласуется с утверждением Тьюринга о принципиальной неразрешимости проблемы остановки. Как выясняется, это неплохой пример проявления случайности в теории чисел – этом становом хребте математики.
Все это выросло из впечатляющих событий 1980-х, когда Джеймс Джонс из Университета Калгари и Юрий Матиясевич из ленинградского Математического института им. Стеклова обнаружили теорему, доказанную французским математиком Франсуа Эдуардом Люка столетием раньше. Теорема, по сути, дает целочисленный метод преобразования универсальной машины Тьюринга в универсальное диофантово уравнение, эквивалентное компьютеру «общего назначения».
Я решил: забавно будет это расписать. И при помощи большого компьютера записал такое вот уравнение универсальной машины Тьюринга. В нем оказалось 17 тысяч переменных, и оно растянулось на 200 страниц.
Эта штука принадлежит к разновидности так называемых экспоненциальных диофантовых уравнений. Все переменные и константы в нем – неотрицательные целые числа: 0, 1, 2, 3, 4, 5 и т. д. Оно называется экспоненциальным, поскольку в нем есть числа, возводимые в целочисленные степени. В нормальных диофантовых уравнениях показатель степени должен быть константой. Здесь же показатель степени может быть переменной. Иными словами, здесь имеется не только x³, но и xy.
Чтобы преобразовать утверждение о том, что вероятность остановки («омега») носит случайный характер, в утверждение о случайности решений в арифметике, мне требуется внести лишь некоторые небольшие изменения в это двухсотстраничное диофантово уравнение универсальной машины Тьюринга. В результате мое уравнение, носящее случайный характер, также окажется двухсотстраничным. В этом уравнении есть единственный параметр – переменная N. Для каждого конкретного значения этого параметра я задаю вопрос: «Конечное или бесконечное количество целочисленных решений имеет (при данном N) мое уравнение?» Ответ на этот вопрос, как выясняется, эквивалентен расчету вероятности остановки. Этот ответ сообщает на арифметическом языке, каков N-й бит «омеги» – ноль или единица. Если N-й бит «омеги» является нулем, то мое уравнение для данного конкретного значения N имеет конечное количество решений. Если же N-й бит вероятности остановки – единица, то это уравнение для данного значения параметра N имеет бесконечное количество решений. Подобно тому, как N-й бит «омеги» носит случайный характер (это независимый, несократимый факт вроде результата подбрасывания монетки), установление того, конечно или бесконечно количество решений моего уравнения, также носит случайный характер. Точный ответ мы в принципе никогда не сможем узнать.
Чтобы выяснить, конечным или бесконечным будет количество решений в определенных ситуациях, скажем, когда у нас есть К значений параметра N, придется постулировать существование К ответов как К дополнительных независимых аксиом. Нам придется ввести k бит информации в нашу систему аксиом, так что никакого продвижения нас не ждет. Иными словами, здесь k бит информации – несократимые математические факты.
Итак, я нашел крайнюю форму случайности (или несократимости) в области чистой математики – в элементарной теории чисел, которая зародилась еще две тысячи лет назад благодаря древнегреческим математикам. Гильберт полагал, что истины в математике либо черные, либо белые, что каждое утверждение в ней либо истинно, либо ложно. А вот моя работа, похоже, заставляет истины казаться серыми, так что математики в этом смысле присоединяются к специалистам по теоретической физике. Это плохо? Думаю, не обязательно. Мы уже увидели, что и в классической, и в квантовой физике случайность и непредсказуемость играют фундаментальную роль. Я убежден, что эти понятия таятся и в самом сердце чистой математики.
Глава 4. Моя вселенная – мои правила
Философская интерлюдия
После всего, что мы узнали, не помешает поразмыслить над тем, что бы это могло значить. Нам нравится думать, что мы отлично контролируем себя и постепенно все больше осмысливаем Вселенную вокруг нас. А если на самом деле невозможно ни то, ни другое? Углубляясь в выяснение того, насколько значительную роль играет в нашей жизни случайность, можно ведь наткнуться и на кое-какие неприятные истины. Неприятные, но все-таки, без всякого сомнения, увлекательные. К примеру, можно поставить под сомнение свободу нашей воли и познаваемость законов физики. Фундаментальнейшие процессы во Вселенной могут носить чисто случайный характер – и по веским причинам: возможно, тем самым они позволяют нам сохранять свободу воли, а кроме того, защищают будущее Вселенной от предопределенности и препятствуют тому, чтобы к нам поступала информация из грядущего. Да, есть риск погрузиться в пучины экзистенциального кризиса, но все-таки давайте ненадолго предадимся философическим раздумьям. По-моему, сейчас самое время.
Кто здесь главный?
Вы когда-нибудь задавались вопросом, действительно ли ваши решения принадлежат именно вам? Все эти попытки добраться до первопричины того, почему мы делаем именно то, что мы делаем, гарантируют бессонную ночь – или, по крайней мере, так может показаться. А вот физик Влатко Ведрал, бывало, размышлял над этой философской загадкой, чтобы уснуть. Сейчас он сам все объяснит – в том числе и то, почему десятилетия спустя он по-прежнему бьется над проблемой свободы воли.
В детстве мне нравилось перед сном поразмышлять над всякими глубокими вопросами. Один из моих любимых был такой: «Есть ли у нас свобода воли?» Мысленно переключаясь между разными возможностями, я вскоре засыпал: отличная методика для того, чтобы побыстрее отрубиться. Теперь я уже взрослый, и мне повезло: моя работа как раз и подразумевает рассуждения на такие темы. Что же ученый муж имеет сказать касательно вышеупомянутой проблемы?
Большинство из нас, представителей западной культуры, убеждены, что мы обладаем свободой воли, хотя совершенно не ясно, каким образом мы пришли к такому выводу и что вообще мы подразумеваем под этим термином. Если определить свободу воли в обиходных понятиях как способность, позволяющую нам контролировать наши собственные действия, ответ вроде бы сводится к двум противоположным возможностям: «Да, мы обладаем свободой воли» и «Нет, мы не обладаем свободой воли». Впрочем, и та и другая быстро приводит нас к противоречиям.