Числа и их записи

Это напоминает мне одну книгу, которую я читал в детстве, — замечательный детский роман Нортона Джастера The Phantom Tollbooth. В нем есть город Диджитополис, а под ним расположена числовая шахта, где добывают числа. Их высекают из камня, и однажды там нашли самое большое число. Оно было гигантским — огромная тройка высотой более четырех метров Здесь допущена примерно та же ошибка, что и в случае с твитом. Такое различие между самим числом и его символическим представлением связано с тем, что иногда называют дихотомией синтаксиса и семантики.

Слова и значения

Есть и другой способ проиллюстрировать это различие. Однажды на торжественном обеде в одном из оксфордских колледжей я сидел за столом для преподавателей. За такими обедами ученые обсуждают самые разные темы. Мы как раз говорили об употреблении слов, и мой коллега Алекс Моран рассказывал о том, как принято говорить на севере Англии. Он сказал:

Я обычно использую «pants» как «trousers».

Именно так он и сказал. А может быть, он сказал:

Я обычно использую pants как trousers.

Так о чем же он говорил — о словах или о самих вещах?

И, пожалуй, для американцев в аудитории стоит пояснить, что в британском английском слово pants иногда обозначает то, что в США мы назвали бы underwear или underpants, то есть нижнее белье. Поэтому его фраза «Я обычно использую pants как trousers» может означать совсем не то, что вам показалось на первый взгляд.

Я, признаться, украдкой заглянул под стол: он, похоже, не носил трусы вместо брюк. Поэтому, думаю, он говорил именно о словах «pants» и «trousers»: он употребляет оба слова в одном и том же значении, «брюки», как это обычно делаем мы в Соединенных Штатах.

Однажды моя дочь Гипатия спросила меня, рифмуется ли всё с самим собой? А я ответил: «Нет‑нет, эти два слова не рифмуются». Разумеется, она спрашивала совсем не об этом. Давайте я запишу ее вопрос:

Рифмуется ли всё с самим собой?

Здесь мы снова сталкиваемся с дихотомией синтаксиса и семантики — с различием между употреблением слова и упоминанием самого слова.

Итак, она спросила: «Рифмуется ли всё с самим собой?» А мой ответ фактически относился к другому вопросу. Если заключить оба выражения в кавычки, получится случай, когда мы не употребляем их в обычном значении, а упоминаем сами слова:

Рифмуется ли слово «всё» со словами «самим собой»?

Нет. Когда мы заключаем «всё» в кавычки, мы говорим о самом слове, а не употребляем его для обозначения всего вообще. Аналогично мы упоминаем выражение «самим собой». Эти два выражения между собой не рифмуются.

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

Например, можно заключить в кавычки только первое выражение и спросить:

Рифмуется ли слово «всё» с самим собой?

И можно ответить: «Ну да, пожалуй. Возможно, любое слово рифмуется с самим собой». Конечно, поэт, который рифмует слово с тем же самым словом, едва ли заслужит похвалы. Но чисто технически, особенно если рассуждать математически, вполне естественно считать отношение «рифмуется с» рефлексивным отношением.То есть каждое слово должно рифмоваться с самим собой. В частности, слово «всё» рифмуется с самим собой. Если произнести «всё» и еще раз «всё», эти слова, разумеется, рифмуются. Поэтому в этом смысле «всё» действительно рифмуется с самим собой.

Или, наоборот, можно заключить в кавычки только второе выражение:

Рифмуется ли всё со словами «самим собой»?

Нет. Ведь, например, слово «гиппопотам» не рифмуется со словами «самим собой». Эти выражения не рифмуются, поэтому ответ здесь отрицательный.

И наконец остается исходный вариант, в котором оба выражения употребляются в их обычном значении:

Рифмуется ли всё с самим собой?

Здесь я бы ответил: да, потому что именно это мы только что и обсуждали. Если понимать «всё» как «каждое слово», то да — каждое слово рифмуется с самим собой. По‑моему, это вполне разумный ответ.

Что значи «наибольшее»

Итак. На конкурс наибольшего числа, которое можно уместить в твите, мне прислали еще одну заявку. Вот этот твит: человек просто написал число ноль. Можно было бы сказать: «Ну очевидно же, что это не самое большое число, которое можно уместить в твите». Но вообще‑то все зависит от того, какой порядок мы используем. Например, при обычном числовом порядке ноль — совсем небольшое число. Более того, если считать ноль натуральным числом, то это наименьшее натуральное число. Но что, если расположить числа в каком‑нибудь другом порядке — например, по алфавиту? Тогда, возможно, ноль оказался бы последним числом, то есть наибольшим числом в алфавитном порядке. Если представить себе книгу всех чисел, расположенных по алфавиту, то ноль находился бы где‑то в самом ее конце. И в этом смысле ноль был бы очень большим числом — если судить по алфавитному порядку.

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

Как записывать огромные числа

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

В общем виде это выглядит как . Такое выражение представляет собой итерированное возведение в степень. Однако здесь возникает потенциальная неоднозначность, поскольку эту запись можно понимать двумя способами. С одной стороны, ее можно интерпретировать как . То есть сначала вычисляется , а затем возводится в полученную степень. Это правоассоциативная интерпретация итерированного возведения в степень. С другой стороны, запись можно было бы понять как . Здесь сначала вычисляется , а уже затем полученный результат возводится в степень .

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

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

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

Поэтому я мог бы заполнить весь твит итерированными степенями, например написать

и продолжать эту степенную башню, пока не закончится место в твите.

Гуглоплекс и сжимаемые описания

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

Кстати, насколько я слышал, название компании Google связано именно с этим числом — отсюда и название поисковика. Хотя написание, конечно, отличается: математический термин googol заканчивается на ‑ol, тогда как название компании Google — на ‑le.

Есть еще одно число, которое называется гуголплексом. Оно равно десяти в степени гугол: . Таким образом, перед нами еще один пример итерированного возведения в степень.

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

В десятичной записи гуголплекс представляет собой единицу, после которой следует гугол нулей:

У гуголплекса есть одно интересное свойство: его чрезвычайно легко описать. Я только что это сделал. Его описание без труда поместилось бы в твите: .

Но теперь подумаем о типичном числе, меньшем гуголплекса. Как мы уже сказали, десятичная запись самого гуголплекса — это единица, за которой следует гугол нулей. Поэтому у типичного числа, меньшего гуголплекса, десятичная запись будет выглядеть примерно как случайная последовательность из порядка гугола цифр. И возникает вопрос: способны ли мы вообще удержать такое число в своем сознании как отдельный объект мысли?

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

Предположим, вы исключительно быстро умеете произносить цифры. Сколько времени потребовалось бы, чтобы перечислить все цифры типичного числа, меньшего гуголплекса? Вам пришлось бы произнести порядка гугола цифр, то есть цифр. Допустим, вы способны произносить миллион цифр в секунду, то есть цифр в секунду. Физики говорят нам, что возраст Вселенной составляет примерно 13,8 миллиарда лет, а это меньше секунд. Следовательно, даже если бы в вашем распоряжении было секунд и каждую секунду вы произносили по миллиону цифр, то всего успели бы произнести лишь цифр. Но вам нужно произнести цифр.

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

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

Главная мысль здесь такова: если нам удалось кратко описать какое‑то гигантское число, это вовсе не означает, что столь же кратко можно описать каждое меньшее число. Более того, коротких описаний просто не хватит на все такие числа.

Гугол‑бэнг и иерархия операций

Теперь я хочу описать еще одно число, которое называю гугол‑бэнгом (googolbang). Запишем его здесь. Гугол‑бэнг получается, если взять гугол и вычислить его факториал: . Это означает, что нужно перемножить Или, если идти сверху вниз,

В общем случае запись ‑bang означает просто факториал : . Это всего лишь шутливый способ говорить о функции факториала.

Теперь я хочу сравнить два числа — гуголплекс и гугол‑бэнг. Какое из них больше? Получается небольшая занимательная задача: что больше — гугол‑бэнг или гуголплекс? Вспомним, что гуголплекс равен десяти в степени гугол: . Если представить его в виде произведения, получится

А гугол‑бэнг в силу определения факториала равен

Здесь тоже ровно гугол множителей, то есть множителей. Но почти все множители во втором произведении гораздо больше 10. Лишь несколько самых маленьких множителей в конце меньше 10, тогда как все остальные больше 10, причем многие — несравненно больше.

Поэтому довольно легко увидеть, что гугол‑бэнг намного больше гуголплекса: огромное превосходство большинства множителей с избытком компенсирует те несколько маленьких множителей в конце, которые меньше 10.

Таким образом, .

То есть гугол‑бэнг больше гуголплекса.

Можно немного усложнить эту задачу, разрешив многократно применять такие суффиксы. Например, я мог бы написать в твите что‑нибудь вроде:

googol‑bang‑plex‑bang‑bang‑plex‑plex‑bang.

Здесь суффикс plex означает операцию , а bang, как мы уже знаем, означает .

Эти операции можно применять последовательно. Например: googol‑bang‑plex‑bang‑bang‑plex‑plex‑bang, и так далее. Можно было бы просто заполнить весь твит такими суффиксами.

Но тогда возникает уже более интересная задача. Допустим, на конкурс прислали две такие последовательности. Нужно определить, какая из них задает большее число. Например, предыдущую запись пришлось бы сравнить с чем‑нибудь вроде: googol‑plex‑bang‑plex‑bang‑bang‑bang‑plex, и так далее. Для всевозможных последовательностей этих суффиксов нужно научиться сравнивать размеры получающихся чисел. Это далеко не всегда очевидно с первого взгляда. Однако, если немного подумать, оказывается, что существует алгоритм, позволяющий определить, какое из таких чисел больше.

Можно добавить еще один суффикс — назовем его stack, то есть «стек». Рассмотрим гугол‑стек (googolstack). Гугол‑стек — это итерированная степень

где в степенной башне находится гугол десяток, то есть ее высота равна .

Иными словами, это степенная башня

Это число уже намного, намного больше как гугол‑бэнга, так и гуголплекса, поскольку итерированное возведение в степень растет чрезвычайно быстро.

Но теперь, конечно, можно говорить уже о целой иерархии операций googol, googolplex, bang и stack. Например, можно рассматривать такие числа, как гугол‑стек. В общем случае ‑stack означает степенную башню из десяток высоты :

Поэтому можно образовывать такие выражения, как googol‑bang‑plex‑stack или googol‑stack‑stack‑stack‑bang‑plex‑stack, и так далее. И чтобы определить победителя конкурса на наибольшее число, которое можно уместить в твите, нам пришлось бы научиться сравнивать числа, задаваемые такими выражениями.

Стрелочная нотация Кнута

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

Одна стрелка вверх означает обычное возведение в степень. Например,

В общем случае

Это исходный уровень рекурсивного определения.

Теперь перейдем на следующий уровень. Рассмотрим . Это означает

причем выражение группируется справа. Иными словами,

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

Таким образом, двойная стрелка задает тетрацию — ту самую операцию stack, о которой мы говорили раньше: .

Можно подняться еще на один уровень. Тройная стрелка строится по тому же принципу, только теперь многократно повторяется операция с двумя стрелками. То есть мы итерируем тетрацию. Это можно записать так:

где число членов равно .

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

Легко увидеть, насколько стремительно растут числа, задаваемые стрелочной нотацией Кнута.

Эти идеи связаны с функцией Аккермана, которую Аккерман ввел в начале XX века. Все эти уровни можно объединить единым рекурсивным определением.

Удобно записать стрелок как . Тогда базовый уровень можно задать умножением: . A означает следующую цепочку из членов:

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

За пределами нотации Кнута

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

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

В этом смысле мы выходим на уровень выше нотации Кнута. Разумеется, затем можно рассмотреть две усиленные двойные стрелки. Это такая же итерация, как раньше, где число членов равно :

Далее можно определить ‑кратную итерацию усиленных двойных стрелок и так далее, продолжая рекурсию за пределы предыдущих уровней. Таким способом можно описывать поистине гигантские числа. Например, после введения этих обозначений я могу предложить собственную заявку на конкурс наибольшего числа. Разумеется, можно определить и версии с тройной усиленной стрелкой ⤊, с четверной усиленной стрелкой ⟰ и так далее:

Итак, для определенности пусть моей заявкой будет число, полученное из трех и трех с помощью четверной усиленной стрелки: . Это совершенно необъятное число.

Возможно, некоторые из вас слышали о числе Грэма, которое также можно описать посредством итерирования стрелочной нотации:

Но только что записанное число намного, намного больше числа Грэма.

Колмогоровская сложность

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

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

Например, колмогоровская сложность гуголплекса очень мала, потому что его чрезвычайно легко описать. Можно написать программу, вычисляющую . Такая программа будет очень короткой. Ее без труда можно было бы уместить в твите, хотя само получаемое число колоссально.

Или возьмем, например, число вроде googol‑plex‑plex‑plex‑stack. Для него также существует очень короткая программа, которая его вычисляет, несмотря на то что само число имеет совершенно невероятный размер.

Итак, мы снова сталкиваемся с явлением, о котором уже говорили. Гуголплекс — чрезвычайно большое число, но его колмогоровская сложность очень мала. В то же время типичные числа, меньшие гуголплекса, мы даже не смогли бы удержать в сознании как отдельные объекты мысли: чтобы просто перечислить все их цифры, не хватило бы всего времени, прошедшего с момента Большого взрыва.

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

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

Позвольте привести доказательство этого факта. Предположим от противного, что колмогоровскую сложность можно вычислять в общем случае. То есть допустим, что существует вычислимая процедура, позволяющая для любого заданного числа определить его колмогоровскую сложность. Для любого фиксированного уровня сложности существует лишь конечное число чисел, сложность которых не превосходит этого уровня. Причина проста: существует лишь конечное число программ ограниченной длины. Следовательно, колмогоровская сложность чисел в конечном счете должна становиться сколь угодно большой. Но если бы мы умели вычислять эту сложность, то могли бы просто искать число с достаточно большой сложностью. Действительно, если сложность вычислима, я могу последовательно перебирать числа и каждый раз спрашивать: «Какова сложность этого числа? А следующего? А следующего за ним?» И так далее. Я мог бы продолжать этот процесс до тех пор, пока не обнаружил бы число с очень большой колмогоровской сложностью. Более того, можно написать программу, которая автоматически выполняла бы такой поиск. Это всего лишь простой цикл: проверить одно число, затем следующее, затем еще одно — и продолжать до тех пор, пока не найдется число, колмогоровская сложность которого больше длины самой программы, выполняющей этот поиск. После этого программа останавливается и выдает найденное число.

Иными словами, если бы колмогоровская сложность была вычислима, мы могли бы построить алгоритм, который выдавал бы число с колмогоровской сложностью, превышающей длину самой программы, реализующей этот алгоритм. Но это противоречие. Ведь по определению колмогоровская сложность числа — это длина самой короткой программы, способной это число породить. Следовательно, наша поисковая программа не может породить число, колмогоровская сложность которого превышает длину самой этой программы: ведь тогда сама поисковая программа уже была бы более короткой программой, порождающей это число. А это непосредственно противоречит определению колмогоровской сложности. Таким образом, в общем случае невозможно с помощью алгоритма точно определить колмогоровскую сложность заданного числа. Не существует вычислимой процедуры, которая позволяла бы вычислять ее точное значение.

Парадокс наибольшего твитуемого числа

Теперь вернемся к парадоксу наибольшего числа, которое можно уместить в твите. Я утверждаю, что для этого конкурса существует заявка, которая совершенно точно должна победить. Вот она. Мы уже привели следующий аргумент: возможных твитов существует лишь конечное число. Некоторые из этих твитов описывают числа. Следовательно, чисел, которые можно описать в твите, тоже лишь конечное множество. А значит, среди них должно существовать наибольшее. Поэтому теперь моей новой заявкой на конкурс будет:

наибольшее число, которое можно уместить в твите

Эта фраза сама помещается в твит и, по определению, обозначает наибольшее число, которое вообще можно описать с помощью твита. Именно это и означает данная фраза. Никто не сможет затвитить число, большее этого. Ведь если какое‑то число можно описать в твите, то наибольшее число, которое можно уместить в твите, должно быть как минимум не меньше него — именно потому, что оно является наибольшим среди всех таких чисел. Так что эта заявка определенно должна выиграть конкурс.

Но тут кто‑нибудь может заметить: «Постойте‑ка. Что здесь происходит?». Ведь тогда можно отправить следующий твит:

наибольшее число, которое можно уместить в твите, плюс один

Это число больше наибольшего числа, которое можно уместить в твите. И тем не менее его описание тоже помещается в твит. В этом и состоит парадокс наибольшего числа, которое можно уместить в твите. Он показывает, что выражение «наибольшее число, которое можно уместить в твите», возможно, вообще нельзя считать осмысленным определением. Ведь если оно действительно имеет определенный смысл, то осмысленным должно быть и следующее выражение:

наибольшее число, которое можно уместить в твите, плюс один.

Но это число тоже можно описать в твите. И в то же время оно больше любого числа, которое можно уместить в твите, поскольку оно на единицу больше самого наибольшего такого числа.

Так что же, черт возьми, здесь происходит? Ведь исходное рассуждение казалось совершенно неоспоримым. Возможных твитов лишь конечное число. Некоторые из них описывают числа. Следовательно, существует лишь конечное число чисел, которые можно описать в твите. Значит, среди них обязательно должно быть наибольшее. Следовательно, я могу говорить о «наибольшем числе, которое можно уместить в твите»: это вроде бы вполне осмысленное понятие. Но тогда я могу написать в твите: «наибольшее число, которое можно уместить в твите, плюс один». Получается парадокс. Это число должно быть больше любого числа, которое можно описать в твите, и тем не менее мы только что сами описали его в твите.

Так что же происходит с нашим конкурсом на наибольшее число?

Парадокс Берри

Это приводит нас к другому парадоксу, который называется парадоксом Берри. Берри был библиотекарем в Оксфорде в начале XX века, и Бертран Рассел отзывался о нем как о единственном человеке в Оксфорде, способном понимать логику. Разумеется, во времена Берри не существовало ни Twitter, ни твитов. Но он сформулировал парадокс, связанный с числами, которые можно описать словами. Берри предложил рассмотреть следующее число. Назовем его числом Берри :

B = “наименьшее число, которое нельзя определить менее чем десятью словами”.

В этой русской формулировке девять слов: «наименьшее», «число», «которое», «нельзя», «определить», «менее», «чем», «десятью», «словами».

Число слов конечно, а значит, конечно и число фраз, состоящих менее чем из десяти слов. Некоторые из этих фраз определяют числа. Следовательно, существуют числа, которые нельзя определить менее чем десятью словами. Но теперь посмотрите, что получилось: мы только что определили число девятью словами. Но по определению  — это наименьшее число, которое невозможно определить менее чем десятью словами. Получается, что мы определили девятью словами число, которое по самому своему определению нельзя определить менее чем десятью словами. Получается своего рода противоречие. Если считать, что у нас есть корректное понятие того, что значит определить число с помощью заданного количества слов, то эта фраза должна определять некоторое конкретное число. Но этого не может быть, поскольку тогда оно, в некотором смысле, должно было бы оказаться меньше самого себя.

Это практически тот же парадокс, что и парадокс наибольшего числа, которое можно уместить в твите. Хотя не совсем тот же. В случае парадокса Берри аналогом будет скорее не твит «наибольшее число, которое можно уместить в твите, плюс один», а твит:

наименьшее число, которое нельзя уместить в твите.

Совпадают ли эти два числа?

Можно было бы рассуждать так: «наибольшее число, которое можно уместить в твите, плюс один» больше любого числа, которое можно уместить в твите, а значит, само уже не должно помещаться в твит. Если наивно считать вполне осмысленным вопрос о том, можно ли задать то или иное число с помощью твита, то может показаться, что

наименьшее нетвитуемое число=наибольшее твитуемое число плюс один

Но на самом деле это неверно. Я утверждаю, что наименьшее число, которое нельзя уместить в твите, намного меньше гуголплекса. Причина проста: возможных твитов недостаточно много.

Число возможных твитов составляет примерно , где  — количество допустимых символов Unicode. А это число намного меньше гуголплекса: . Следовательно, невозможно, чтобы каждое число вплоть до гуголплекса можно было задать отдельным твитом: для этого просто не хватило бы различных твитов. Значит, уже среди чисел, меньших гуголплекса, обязательно найдутся числа, которые невозможно задать твитом. В частности, наименьшее такое число тоже будет меньше гуголплекса. Поэтому оно никак не сможет выиграть наш конкурс. Ведь я легко могу превзойти наименьшее нетвитуемое число, просто написав в твите гуголплекс, который, как мы уже видели, описывается очень коротко: .

Таким образом, парадокс Берри ближе по своей структуре к наименьшему числу, которое нельзя уместить в твите, чем к «наибольшему числу, которое можно уместить в твите, плюс один». Впрочем, можно сформулировать вариант парадокса Берри и во втором духе. Например:

наибольшее число, которое можно определить менее чем двадцатью словами, плюс один.

Само это описание содержит менее двадцати слов, и мы снова получаем аналогичную проблему.

Так что же на самом деле происходит с парадоксом твитуемых чисел, парадоксом Берри и всеми подобными конструкциями?

Программы и проблема остановки

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

Разумеется, некоторые присланные программы могут вообще не выдавать числа. Какая‑нибудь программа может вывести бессмысленную строку символов. Другая может вообще никогда не завершить работу: она будет выполняться бесконечно и так и не выдаст ответа. Но чтобы определить победителя конкурса, вам, как судье, необходимо выяснить, какие программы действительно завершают работу и выдают числа, а затем сравнить полученные числовые результаты.

Прежде всего, даже если рассматриваемые программы действительно завершают работу и выдают числа, вам необходимо уметь сравнивать эти числа по величине. Например, это связано с вопросом о том, что больше: googol‑plex‑bang или googol‑bang‑plex, а также с аналогичными вопросами для гораздо более длинных последовательностей таких операций. Впрочем, если потребовать, чтобы каждая программа непосредственно выводила десятичные цифры соответствующего числа, сравнивать результаты, возможно, станет немного проще. Но все равно остается другая проблема: необходимо определить, остановится ли программа вообще, то есть завершит ли она когда‑нибудь свою работу.

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

В 1936 году Алан Тьюринг ввел понятие машины Тьюринга и исследовал возможность существования алгоритмически неразрешимых задач. Сегодня мы знаем, что проблема остановки — вопрос о том, завершит ли когда‑нибудь заданная компьютерная программа свою работу, — алгоритмически неразрешима. Эта ситуация напоминает проблему колмогоровской сложности. Более того, неразрешимость проблемы остановки можно вывести из невычислимости колмогоровской сложности.

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

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

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

Но теперь перед нами открывается возможность взглянуть на проблему конкурсов вроде конкурса на наибольшее число, которое можно уместить в твите, гораздо глубже. Возникает вопрос: существует ли вообще объективный факт относительно того, остановится та или иная программа или нет?

Мы знаем, что проблема остановки алгоритмически неразрешима. Из этого следует, что для любой выбранной нами формальной теории оснований математики — например, арифметики Пеано, теории множеств Цермело — Френкеля или какой‑либо другой стандартной аксиоматизации математики — обязательно существуют программы, причем сравнительно небольшие, которые в действительности не останавливаются, но данная теория не способна доказать, что они не останавливаются. И это заставляет задуматься над тем, в каком именно смысле существует определенный факт относительно того, остановятся такие программы или нет.

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

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

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

«наибольшее число, которое можно уместить в твите»

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

Это один из способов понять, как разрешается парадокс наибольшего числа, которое можно уместить в твите.

Неопределимость определимости

Этот момент, связанный с логической неразрешимостью в контексте конкурсов на наибольшее число, можно сформулировать так: возможно, даже наши фундаментальные математические аксиомы не определяют ответ на вопрос, задает ли некоторое описание вообще какое‑либо число. И они могут не определять, задает ли одно описание число, большее, чем число, задаваемое другим описанием.

Возможно, это связано и с парадоксом Берри, где мы говорим о

наименьшем числе, которое нельзя определить менее чем десятью словами.

Один из способов разобраться с этим парадоксом — спросить: что именно мы понимаем под определимостью? И является ли сама определимость определимой?

Альфред Тарский глубоко исследовал этот вопрос и доказал замечательную теорему, известную как теорема Тарского о невыразимости истины. Если, например, взять формальный язык арифметики, то вопрос о том, определяет ли данная формула некоторое число, нельзя в общем случае выразить средствами самого этого языка. Именно здесь проявляется содержание теоремы Тарского о невыразимости истины.

Таким образом, в строгом формальном смысле получается, что определимость не может быть определена изнутри того же самого языка. Если воспринимать парадокс Берри наивно, то может показаться, что слово «определимый» совершенно безобидно и мы прекрасно понимаем выражение «наименьшее число, которое нельзя определить менее чем десятью словами».

Но стоит разобраться глубже и применить аппарат математической логики, в частности теорему Тарского, как становится ясно, что здесь незаметно совершается недопустимый переход между уровнями языка. Мы пользуемся понятием «определимый» так, словно оно само доступно для определения внутри того же формального языка.

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