Проблема решения, может или нет быть выведено то или иное отдельное предположение, на первый взгляд гораздо больше должна занимать инженеров — это проблема, которая затрагивает специфические и конкурентные вопросы. Безусловно, она интересует и математика, но для всех остальных она должна казаться значительно менее важной, чем сама фундаментальная проблема — что мы не в состоянии доказать все.
Но нет. Даже если этот вопрос может показаться скучным — ответ на него определенно таковым не является.
В своих лекциях Ньюман спрашивал, можем ли мы создать своего рода «механический процесс», который был бы применим к математической задаче с целью определить, имеет ли она решение. В сущности, это было как раз то, о чем спрашивал Гильберт: существует ли рецепт, который может нам сказать, способны ли мы вывести специфические следствия из теории? Желательно, чтобы это был способ, который не потребует слишком много воображения и при этом действительно будет механическим — алгоритм, как называют это математики.
«Механический процесс». Алан Тьюринг принял во внимание выражение Ньюмана. Он подумал о машинах — машинах, которые могли бы считать. В 1935 подобные машины уже существовали — но они не представляли особого интереса. И Тьюринг начал рассматривать принцип работы подобных машин: что нужно, чтобы машина могла решить математическую задачу и определить, может ли предположение быть получено из теоретической системы?
Требовалось не так уж много. Тьюринг изобрел простую логическую машину, которая не слишком много умела. Она могла выполнять несколько инструкций: писать, читать и выполнять в своей памяти исправления. Немногим больше, чем обычная печатная машинка.
Но Тьюринг оснастил свою логическую машину бесконечно большой памятью. Он предусмотрел для машины возможность записывать свою деятельность на рулоне бумаги бесконечно долго. Эта бумага могла перемещаться вперед и назад, так что машина — как и печатная машинка — работала на определенном участке в определенный момент времени. Этот бесконечный рулон бумаги — лента — был бесконечным вот почему: на самом деле неважно, насколько точно машина выполняла свои инструкции. Ведь у нее было достаточно памяти и достаточно времени.
Тьюринг понял, что такая простая машина — которая известна сегодня как машина Тьюринга — могла бы на самом деле решить многие задачи Гильберта по дедукции — и как раз потому, что Гедель изобрел элегантный логический маневр, благодаря которому можно было рассматривать любой вид математических конструкций под видом чисел. Это была универсальная машина, способна решить любые арифметические задачи. Любые известные выполнимые вычисления можно было выполнить на машине Тьюринга, которая, следовательно, воплотила принцип счетной машины в ее чистом и обобщенном виде.
Но вскоре Тьюринг понял и кое-что еще: алгоритм может быть написан так, что будет для машины «не пережевываемым» в понятной для нее манере. Были числа, к которым она не могла подобраться. И не потому, что числа были слишком большими — а потому, что алгоритм был слишком непостижим: невозможно было сказать, сможет ли машина справиться с числом, пока операция не была выполнена — а это могло занять бесконечно много времени. Таким образом никто не мог знать, удастся ли ему получить результат в течение конечного периода времени.
Это значит, что
Гильберта была неразрешимой. Мы не можем создать алгоритм, который говорил бы нам, может ли что-либо быть выведено из математической системы.
Это заключение важно само по себе — и к нему одновременно и независимо пришел и другой ученый — американский логик Алонзо Черч.
Но в открытиях Тьюринга есть и еще одна интересная вещь: ему удалось сделать сразу два открытия одновременно, летним днем, лежа на лугу. В своей биографии Алана Тьюринга Эндрю Ходжес описывает это так:
«Алан доказал, что не существует никакой «чудесной машины», которая могла бы разрешать все математические задачи. Но в процессе он открыл кое-что столь же чудесное — идею универсальной машины, которая могла бы взять на себя работу любой машины».
Тьюринг создал теорию машин, которые могли считать. Несколько лет спустя Вторая мировая война привела к тому, что значительные ресурсы были брошены на срочное развитие электронных компьютеров, особенно в Великобритании и США. Британцы пользовались ими, чтобы расшифровать секретные немецкие коды коммуникации. Американцы использовали их, помимо всего прочего, для создания атомной бомбы.
Со времен Второй мировой войны компьютеры стали обычным делом. Уже десятки лет человек увлечен идеей тех бесконечных возможностей, которыми наделили нас компьютеры и которые позволяют нам контролировать мир и следить абсолютно за всем.
Но факт заключается в том, что как только была изобретена концепция и теория вычислительных машин, Алан Тьюринг тут же осознал: мы не можем вычислить все. Человеческий разум оказался в состоянии сформулировать идею об универсальной вычислительной машине в тот самый момент, когда стало ясно: мы не в состоянии вычислить все механически. Существуют вопросы, возможность ответа на которые приходит только тогда, когда эти ответы получены — но не раньше.
Глубина этих отношений может оказаться для нас чуждой. Тезис Черча-Тьюринга просто утверждает, что мы можем вычислить все, что уже было вычислено. Вы можете делать все то, что, как вам известно, вы можете делать. А узнать, можете ли вы это сделать, вы сможете только после того, как уже сделаете!
Сегодня, когда компьютеры стали вездесущими, эта идея более знакома нам как «проблема остановки Тьюринга»: если говорить в целом, можем ли мы определить, когда компьютер закончит определенное вычисление? Ответом будет «нет»: мы не можем знать заранее, когда компьютер закончит вычисление (если, конечно, раньше он этого не делал).
Аналогично мы не можем знать, закончит ли компьютер вычисления вообще — до тех пор, пока он их не закончил. Пока он не закончил, мы не знаем, закончит ли он или будет продолжать работать вечно.
Это, конечно, не касается простых вычислений повседневной жизни — относительно них у нас есть большой опыт. Но мы знаем это только потому, что у нас уже есть подобный опыт. Нет принципиальных универсальных логических правил, которые могли бы сказать нам то, что было бы нам не известно.
Тезис Черча-Тьюринга и проблема остановки Тьюринга говорят нам о том, что мы не можем получить знаний иначе, чем через опыт. Невозможно заранее сказать, что произойдет.
В этом отношении компьютеры сходны с искателями истины и маленькими детьми. Все, что мы можем сделать — это ждать, пока они закричат: «Я закончил!».
«Большинство математиков, возможно, предпочли бы ограничить разглашение информации о текущем статусе математики «членами семьи», — писал в 1980 году Морис Клайн в своем предисловии к книге о том, как математика теряет уверенность. — Если об этих проблемах узнает общественность, это будет так же нехорошо, как распространять сведения о чьих-то проблемах в браке».
И действительно, в течение многих последних лет прошло несколько волн кризиса. Последовательность этих событий подытожил Руди Рукер в своей книге, опубликованной в 1987 году: «Теорема Геделя показывает, что человеческая мысль является более сложной и менее механической, нежели мы могли ранее полагать. Но после первоначального волнения 30-х годов результат свелся к небольшому количеству технической математики. Теорема Геделя стала частной собственностью представителей математической логики, и многие из этих академиков впадают в высокомерие при любом предположении о том, что эта теорема может иметь какое-то значение для реального мира».
Философы тоже не слишком преуспели, хотя в начале 30-х годов польский философ Альфред Тарский действительно представил сходные с Геделем аргументы, демонстрирующие, что мы никогда не сможем вывести истины из системы, находясь внутри нее.
Но теорема Геделя все же стала широко известной, и не в последнюю очередь потому, что в 1979 году американский ученый-компьютерщик Дуглас Хофстадтер опубликовал очень красивую, очень сложную и очень знаменитую книгу «Godel, Escher, Bach и Kомпания», в которой он указывает на духовное родство Иоганна Себастьяна Баха (1685–1750), чью музыку современники находили чересчур «математической», графического художника Мориса Эшера (1898–1972), до сих пор не вполне признанного коллегами, и Курта Геделя (1906–1978), информация о котором только сейчас распространяется в широких кругах.
Существовала и другая причина, почему мир начал замечать Геделя: стало ясно, что феномен, на который он указал, не был ограничен только странными парадоксами древних греков. Недоказуемость и неразрешимость являются фундаментальными характеристиками нашего мира.
Дальнейшее развитие теоремы Геделя в 60-е годы шло под различными названиями — теория алгоритмической информации, алгоритмическая степень интеграции, алгоритмическая случайность. Но какое бы название мы ни выбрали, отцов-основателей этого направления было три: Рэй Соломонофф, Андрей Холмогоров и Грегори Чаитин.
Сложно? На самом деле все не так сложно, как кажется. На самом деле с помощью этой теории можно гораздо проще выразить то, что открыли Гедель и его последователи. Она дает нам разумное определение того, чем на самом деле является случайность — а это важно, так как это дает нам намек на то, что такое порядок.
Отправной точкой здесь являются числа. Что такое случайное число? Так как все три эти джентльмена были математиками, у них была склонность к бинарным числам — то есть числам, которые состоят только из нулей и единиц: 010110100110 …
Такие числа сложно воспринимать визуально — но если перед ними поставить запятую, то они будут выглядеть как старые добрые десятичные дроби: 0.10110100110. Является ли это число случайным? На самом деле мы просто записали серию случайных двоичных цифр. Но была ли это просто случайность?
Мы могли с таким же успехом 12 раз бросить монетку, обозначив «орла» как 1 и «решку» как 0. В этом случае, конечно, число было бы случайным? Можем попробовать: 100010000111 — нет, никакого обмана: мы бросили монетку 12 раз. Но если мы сделаем это еще раз, число, конечно, будет другим: 110011010000.
Конечно, можно было сделать и что-то совсем другое. К примеру, можно было устроить проверку нашего знания бинарных номеров, написав, допустим, 0.010101010101.
Вот это уже не кажется случайным — это последовательность 01. Такую последовательность можно было выразить проще: 0 точка 6 раз 01. Но на самом деле этот пример довольно хитрый, так как выразить данное число можно даже более кратко: это бинарное представление 1/3.
Смысл заключается в том, что определенные числа могут быть представлены в гораздо более краткой форме. К примеру, 111111111111111111 можно записать как «18 раз единица».
Если использовать десятичную систему, 0.42857142857 можно записать как 3/7, а 1234567891011121314151617181920 как «последовательность цифр от 1 до 20».
Но могут ли последовательности, которые мы получаем, бросая монетку, также быть записаны в краткой форме? Нет, не могут. Ведь они в сущности являются информацией о 12 последовательных событиях, полностью независимых друг от друга. Не существует системы, которая могла бы определить, появится ли в следующей позиции 0 или 1. Да, мы вполне можем ожидать, что много раз выпадут нули или единицы, а вся последовательность при этом будет состоять примерно из одинакового количества тех и других, так как мы ожидаем выпадения «орлов» и «решек» с примерно одинаковой вероятностью. Однако порядок их будет произвольным. В нем не будет системы.
Конечно, мы можем подбросить монетку 12 раз и получить последовательность 010101010101, которая может быть выражена очень кратко — но это не будет происходить слишком часто. На самом деле примерно можно подсчитать, что нам для этого придется подбрасывать монетку тысячи раз, прежде чем мы сможем получить эту последовательность (и любую другую специфическую последовательность). Не стоит принимать это во внимание.
Таким образом, случайные числа нельзя описать более кратко. Но другие — можно, к примеру, 0.42857142857 может быть записано как 3/7.
Таким образом, различия между случайными и упорядоченными числами может быть выражено так: случайные числа — это числа, которые нельзя описать более коротким образом, а упорядоченные — можно. Именно это мы и подразумеваем под порядком.
Теория этих трех джентльменов гласит, что таким образом мы получаем очень хорошую теорию порядка и случайности. Случайность — это то, что не может быть выражено более кратко в виде алгоритма. Случайные числа — это числа, которые нельзя выразить короче, чем они есть.
Противоположный случай — упорядоченные числа. «3/7» — это правило арифметики, алгоритм, который говорит нам, как получить последовательность 0.42857142857 (если мы согласимся иметь дело только с первыми 12 цифрами). Таким образом, эта последовательность является менее случайной, чем 0.32857142877, где изменены две цифры и, вероятно, получилось число, которое не может быть выражено простой дробью.
Но можем ли мы быть уверены? Кто сказал, что 0.35657142877 не является некоей простой дробью — ведь, возможно, мы просто в спешке это просмотрели?
Возможно, найдется читатель, который найдет алгоритм для последовательности 0.35657142877, который будет короче, чем сама последовательность. Если это произойдет, будет доказано, что последовательность не является случайной. Но до тех пор мы можем предполагать, что она таковой является.
Тем не менее никто не знает, что именно может предпринять хитрый читатель: и в определенном смысле именно это и доказал Гедель.
Мы не можем установить одно общее правило, которое будет говорить нам, как установить, является ли число случайным или нет — может ли оно быть выражено более коротко или нет. Это есть прямое следствие открытия Геделя. Это теорема Геделя — именно то, что он доказал.
Мы знаем, что число может быть выражено в более краткой форме, только тогда, когда понимаем, что это возможно. До тех пор мы не можем этого утверждать.
Случайных чисел больше, чем упорядоченных. Большинство чисел невозможно представить в более коротком виде, нежели они уже есть. Это можно понять интуитивно благодаря способу, по которому мы (возможно) создаем случайные числа: мы просто смотрим на упорядоченное число 3/7), записываем его в десятичной форме — и меняем две цифры. Результат (предположительно) будет представлять собой случайное число. Но мы можем изменить и две другие цифры, или поменять уже измененные цифры на другие. Результат (предположительно) тоже будет случайным числом. (Важно, что алгоритм, описывающий способ создания «беспорядочных» номеров, не может быть выражен более кратко, нежели само число — иначе все пойдет насмарку. Число 0.32857142877 может быть представлено как 3/7 — 0.1 + 2 X 10~10 — это почти короче, чем само число, которое в этом случае точно не будет случайным).
Есть возможность доказать, что число не является случайным, так как оно может быть описано в более коротком виде — другими словами, в виде алгоритма. Но невозможно сказать, что число не может быть описано более кратко.
Это и есть открытие Геделя: мы можем сказать, что такое порядок, когда его увидим. Но мы не можем сказать, что это не является порядком только потому, что мы его не видим — и никакие математики, логика или компьютер не смогут нам в этом помочь.
Порядок есть порядок. Остальное остается неопределенным.
Безусловно, три джентльмена расширили эти идеи. Самый короткий путь описания серии цифр также может быть выражен в виде самой короткой инструкции, которую мы можем дать машине для распечатывания этого номера. В ситуации со случайным числом нам придется сказать машине всю последовательность, в то время как числа вида 0.42857142857 могут вводиться более кратко — как s/t.
Идея, таким образом, заключается в определении алгоритмического информационного контента серии чисел как самого короткого алгоритма, который заставит машину Тьюринга распечатать эту последовательность. Эта концепция известна также как алгоритмическая степень интеграции или алгоритмическая случайность.
Но — можем возразить мы — это значит, что случайные числа содержат больше информации, чем упорядоченные. И это действительно так. Информационное содержание выражается тем, насколько сложной является передача сообщения. Более длинный разговор по телефону потребуется для описания результата подбрасывания 12 раз, чем числа 3/7, так как случайное — это то, что не может быть сказано короче.