Физики давно обсуждают вопрос предсказуемости. В начале XIX века классические детерминистические законы Исаака Ньютона заставили Пьера Симона де Лапласа решить, что будущее Вселенной, возможно, навсегда предопределено.

А потом появилась квантовая механика. Ее теории лежат в основе нашего теперешнего понимания природы вещества. Она описывает очень маленькие объекты – например, электроны и другие элементарные частицы. Одной из самых противоречивых особенностей квантовой механики стало то, что она ввела в физику вероятность и случайность как основополагающие факторы. Как известно, это очень расстроило Альберта Эйнштейна, который возмущенно заявил: мол, Бог не играет в кости.

А несколько десятилетий спустя научный мир был снова удивлен: исследования в области нелинейной динамики показали, что даже классическая ньютоновская физика зиждется на случайности и непредсказуемости. Так случайность и непредсказуемость начали казаться каким-то объединяющим физическим принципом.

Кажется, этот же принцип распространяется и на математику. Некоторые теоремы, связанные с теорией чисел, невозможно доказать, поскольку, задавая необходимые вопросы, мы получаем результаты, эквивалентные результатам случайного подбрасывания монетки.

Мои выкладки шокировали бы многих математиков XIX века, убежденных, что уж математические истины всегда можно доказать. Например, в 1900 году математик Дэвид Гильберт прочел ставшую знаменитой лекцию, где перечислил 23 нерешенные проблемы как вызов для математиков нового века. Шестая проблема касалась установления фундаментальных универсальных истин – аксиом – в физике. Один из ее аспектов затрагивал теорию вероятностей. Для Гильберта вероятность выступала просто как практический инструмент, берущий начало в физике и помогающий описывать реальный мир, где доступно лишь ограниченное количество информации.

Десятая проблема Гильберта касалась решения так называемых диофантовых уравнений (названных так в честь древнегреческого математика Диофанта). Это алгебраические уравнения, имеющие дело лишь с целыми числами. Гильберт спрашивает: «Существует ли способ определить, будет ли алгебраическое уравнение иметь целочисленное решение?»

Гильберт вряд ли догадывался, что между шестой и десятой проблемой существует тонкая взаимосвязь. В основе всех его рассуждений лежало настолько фундаментальное для него положение, что он даже не сформулировал его на своей лекции в виде проблемы или вопроса: Гильберт неизменно исходил из того, что у каждой математической задачи есть решение. Может быть, нам не хватает ума, трудолюбия или времени, чтобы его найти, но в принципе всякая математическая проблема должна быть разрешимой. Так полагал Гильберт. Для него это была абсолютная истина.

Однако сегодня математикам ясно: Гильберт стоял на зыбкой почве. Да, есть связь между шестой проблемой Гильберта, которая имеет отношение к теории вероятностей, и его десятой проблемой – касательно целочисленных решений для алгебраических уравнений. И эта связь приводит к неожиданному и даже в чем-то устрашающему результату. Оказывается, случайность таится в самом сердце традиционнейшей отрасли чистой математики – теории чисел.

Как выясняется, ответы на простые и ясные математические вопросы не всегда просты. Так, в элементарной теории чисел вопросы, затрагивающие диофантовы уравнения, способны порождать ответы совершенно случайного характера – с виду не черные и не белые, а серые. Ответы случайны, ибо единственный путь доказательства сводится к постулированию каждого ответа как добавочной независимой аксиомы. Эйнштейн ужаснулся бы, узнав, что Бог преспокойно играет в кости не только в квантовой и классической физике, но и в чистой математике.

Откуда столь неожиданный вывод? Вернемся к Гильберту. Он утверждал, что если вы построили формальную систему аксиом, должна существовать механическая процедура для определения того, является ли то или иное математическое доказательство верным, и эти аксиомы должны обладать полнотой и внутренней непротиворечивостью. Внутренняя непротиворечивость системы аксиом означает, что вы не можете доказать противоположные утверждения. Полнота системы означает, что вы можете доказать истинность или ложность любого утверждения, существующего в ее рамках. Из этого следует, что механическая процедура, о которой мы говорили, должна гарантировать: истинность всех математических утверждений можно доказать или опровергнуть механическим путем.

Есть красочное объяснение того, как работает эта механическая процедура. Речь идет о так называемом алгоритме Британского музея. В рамках мысленного эксперимента (неосуществимого на практике, т. к. он требует бесконечного времени) систему аксиом, выраженных формальным языком математики, прогоняют через все возможные доказательства, причем порядок их следования выстроен согласно их размерам и лексикографической структуре (просто для того, чтобы соблюдать какой-то порядок). Вы устанавливаете, какие из этих доказательств верны, т. е. какие из них отвечают определенным правилам и могут быть приняты как справедливые. В принципе, если набор аксиом обладает внутренней непротиворечивостью и полнотой, можно определить истинность/ложность любой соответствующей теоремы. От математиков больше не требуется изобретательность, талант или вдохновение для того, чтобы доказывать теоремы. Математика становится механической.

Конечно же, на самом деле математика совсем не такая. Курт Гёдель, австрийский логик, и Алан Тьюринг, отец компьютера, показали: невозможно получить и аксиоматическую математическую теорию (обладающую внутренней непротиворечивостью и полнотой), и механическую процедуру, призванную решать, каким является произвольное математическое утверждение – истинным или ложным, доказуемым или недоказуемым.

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

Чтобы показать, что эту так называемую проблему остановки (проблему останова) невозможно решить в принципе, запустим программу на машине Тьюринга, которая представляет собой математическую идеализацию цифрового компьютера, не ограниченную временем. (Программа должна быть самоподдерживающейся – все данные должны поступать из самой же программы.) Далее зададимся простым вопросом: будет ли программа работать вечно или же наступит момент, когда она скажет «я закончила» и остановит работу?

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

Чтобы сделать свой вывод о случайности в математике, я просто взял результат Тьюринга и изменил его формулировку. Получился своего рода математический каламбур. Хотя проблема остановки нерешаема, можно рассмотреть вероятность того, остановится ли когда-нибудь случайно выбранная программа. Начнем с мысленного эксперимента, где используется обычный компьютер «общего назначения», который, если дать ему достаточно времени, способен проделать работу любого компьютера. Иными словами, это универсальная машина Тьюринга.

Не станем спрашивать, остановится ли конкретная программа. Лучше рассмотрим совокупность всех возможных компьютерных программ. Каждой из них придадим определенную вероятность того, что именно ее выберут. Каждый бит информации в случайно выбираемой программе определяется путем подбрасывания монетки, причем для каждого бита этот бросок – независимый. Тогда для программы, содержащей N бит информации, вероятность того, что ее выберут, равна 2^-N. Теперь зададимся вопросом, какова общая вероятность того, что эти программы остановятся. Она, эта вероятность остановки, обозначаемая как «омега» (Ω), позволяет ответить на вопрос Тьюринга о том, остановится ли программа, одним-единственным числом от 0 до 1. Если программа никогда не останавливается, Ω = 0. Если же программа всегда останавливается, Ω = 1.

Точно так же, как компьютеры выражают числа двоичной записью, мы можем выразить «омегу» цепочкой нулей и единиц. Можно ли заранее определить, каким будет N-й бит в этой цепочке цифр – нулем или единицей? Иными словами, можно ли вычислить «омегу»? О нет. Более того, я даже могу показать, что эта последовательность нулей и единиц носит случайный характер. Это можно сделать, используя так называемую алгоритмическую теорию информации, которая приписывает ту или иную степень упорядоченности набору данных в зависимости от того, существует ли алгоритм, способный сжать эти данные, представив их в более краткой форме.

К примеру, цепочку регулярно чередующихся нулей и единиц, описывающую какие-то данные как 0101010101… и состоящую в общей сложности из тысячи знаков, можно сжать в более короткую инструкцию: «Повторить „01“ 500 раз». А вот совершенно случайную цепочку цифр нельзя свести к более короткому тексту-программе. Такие цепочки называют алгоритмически несжимаемыми.

Как показывает мой анализ, вероятность остановки является алгоритмически случайной. Ее нельзя сжать, представив как более короткую инструкцию. Чтобы получить на выходе N бит этого числа, необходимо ввести в компьютер программу длиной по меньшей мере N бит. Каждый из N бит «омеги» – несократимый независимый математический факт, такой же случайный, как и результат подбрасывания монетки. К примеру, в «омеге» столько же нулей, сколько и единиц. Но знание всех ее четных бит не поможет нам узнать никакие из ее нечетных бит.

Мой вывод, что вероятность остановки носит случайный характер, согласуется с утверждением Тьюринга о принципиальной неразрешимости проблемы остановки. Как выясняется, это неплохой пример проявления случайности в теории чисел – этом становом хребте математики.

Все это выросло из впечатляющих событий 1980-х, когда Джеймс Джонс из Университета Калгари и Юрий Матиясевич из ленинградского Математического института им. Стеклова обнаружили теорему, доказанную французским математиком Франсуа Эдуардом Люка столетием раньше. Теорема, по сути, дает целочисленный метод преобразования универсальной машины Тьюринга в универсальное диофантово уравнение, эквивалентное компьютеру «общего назначения».

Я решил: забавно будет это расписать. И при помощи большого компьютера записал такое вот уравнение универсальной машины Тьюринга. В нем оказалось 17 тысяч переменных, и оно растянулось на 200 страниц.

Эта штука принадлежит к разновидности так называемых экспоненциальных диофантовых уравнений. Все переменные и константы в нем – неотрицательные целые числа: 0, 1, 2, 3, 4, 5 и т. д. Оно называется экспоненциальным, поскольку в нем есть числа, возводимые в целочисленные степени. В нормальных диофантовых уравнениях показатель степени должен быть константой. Здесь же показатель степени может быть переменной. Иными словами, здесь имеется не только x³, но и x^y.

Чтобы преобразовать утверждение о том, что вероятность остановки («омега») носит случайный характер, в утверждение о случайности решений в арифметике, мне требуется внести лишь некоторые небольшие изменения в это двухсотстраничное диофантово уравнение универсальной машины Тьюринга. В результате мое уравнение, носящее случайный характер, также окажется двухсотстраничным. В этом уравнении есть единственный параметр – переменная N. Для каждого конкретного значения этого параметра я задаю вопрос: «Конечное или бесконечное количество целочисленных решений имеет (при данном N) мое уравнение?» Ответ на этот вопрос, как выясняется, эквивалентен расчету вероятности остановки. Этот ответ сообщает на арифметическом языке, каков N-й бит «омеги» – ноль или единица. Если N-й бит «омеги» является нулем, то мое уравнение для данного конкретного значения N имеет конечное количество решений. Если же N-й бит вероятности остановки – единица, то это уравнение для данного значения параметра N имеет бесконечное количество решений. Подобно тому, как N-й бит «омеги» носит случайный характер (это независимый, несократимый факт вроде результата подбрасывания монетки), установление того, конечно или бесконечно количество решений моего уравнения, также носит случайный характер. Точный ответ мы в принципе никогда не сможем узнать.

Чтобы выяснить, конечным или бесконечным будет количество решений в определенных ситуациях, скажем, когда у нас есть К значений параметра N, придется постулировать существование К ответов как К дополнительных независимых аксиом. Нам придется ввести k бит информации в нашу систему аксиом, так что никакого продвижения нас не ждет. Иными словами, здесь k бит информации – несократимые математические факты.

Итак, я нашел крайнюю форму случайности (или несократимости) в области чистой математики – в элементарной теории чисел, которая зародилась еще две тысячи лет назад благодаря древнегреческим математикам. Гильберт полагал, что истины в математике либо черные, либо белые, что каждое утверждение в ней либо истинно, либо ложно. А вот моя работа, похоже, заставляет истины казаться серыми, так что математики в этом смысле присоединяются к специалистам по теоретической физике. Это плохо? Думаю, не обязательно. Мы уже увидели, что и в классической, и в квантовой физике случайность и непредсказуемость играют фундаментальную роль. Я убежден, что эти понятия таятся и в самом сердце чистой математики.