Космологические коаны. Путешествие в самое сердце физической реальности - Энтони Агирре

так?» Джинн отвечает: «Ну, положим, ты еще не сделал того, что собираешься сделать, поэтому я пока не решил».

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

Ты видишь, что он замер и сосредоточился; потом на его лицо набежала тень. Спустя минуту или две ты начал сомневаться в том, что джинн вообще собирается отвечать или принимать решение. А затем ты понимаешь, что он попросту не обращает на тебя внимания, и потихонечку уходишь из пещеры.

Любой человек, который при принятии решений руководствуется набором правил (например, законами физики), в общем случае заранее не может знать, примет ли он решение, и если да, то каково оно будет… Гораздо эффективнее просто поступать, как считаешь нужным, а не моделировать свои действия.

Сет Ллойд

За 63 миллиарда секунд до появления в пещере странника джинн понял нечто весьма неприятное. Ему всегда нравилось прокручивать внутри себя алгоритмы, выделяя небольшую часть ресурсов джинниума для того, чтобы при подаче последовательности инструкций на заданный вход I получить из блоб-хранилища джинниума выходные данные О. В результате проведения множества таких экспериментов джинн заметил, что блоб либо выдавал результат очень быстро (джинниум был очень эффективен), либо зависал на бесконечное время, если алгоритм содержал внутри себя что-то наподобие бесконечного цикла. Обычно джинн мог обнаружить такое зацикливание сразу, но в случае более сложных и интересных алгоритмов оказалось, что понять, зависнет программа или нет, на удивление сложно. Проблема оказалась даже еще сложнее: иногда компьютер надолго — чуть ли не на несколько минут — останавливался, а потом внезапно выдавал ответ.

И джинн решил раз и навсегда покончить с проблемой, создав тщательно продуманную программу, названную им Н, которая бы выполнялась в выделенном сегменте джинниума. Эта программа Н должна была сказать джинну, нормально или нет работает некий другой алгоритм. Если при подаче рассматриваемого алгоритма на вход I он в конце концов мог бы выдать ответ, то H выдала бы результат «ПРИЕМЛЕМО». Если же алгоритм содержал бесконечный цикл, то H выдала бы результат «СКУЧНО». То есть H (A, I) должна была быть алгоритмом, принимающим на вход некоторый другой алгоритм A и одновременно входные данные I — и выдающим на выходе либо результат «СКУЧНО», либо «ПРИЕМЛЕМО». Джинн был очень доволен этой идеей и приступил к написанию и тестированию все более совершенных программ Н.

Написание программы H оказалось более трудным делом, чем джинн предполагал, но он не понимал, почему. Тогда он начал размышлять в более общих терминах и предположил, что алгоритм Н уже существует и нужно только проанализировать, как он будет вести себя в разных ситуациях. Это безусловно приятное упражнение заняло много времени. На 43123-ой секунде джинн обнаружил любопытное свойство, возникающее, когда алгоритм H применялся к алгоритму A, код которого использовался и в качестве входных данных, то есть когда выполнялась программа H (A, A). Во время этих многочисленных экспериментов, на 43645-ой секунде, джинн придумал небольшой забавный алгоритм M (I), содержащий следующий трюк:

Шаг 0. Принять входные данные I.

Шаг 1. Вызвать H (I, I).

Шаг 2. Если H возвращает результат «ПРИЕМЛЕМО», то в М бесконечное зацикливание.

Шаг 3. В противном случае на выходе результат «ДЖИНН ЛУЧШЕ ВСЕХ».

Джинн наслаждался извращенностью этого алгоритма, который делал что-то скучное (зацикливался), если входной алгоритм I удовлетворительно выполнялся при получении на вход собственного кода (т. е. H (I, I) возвращал «ПРИЕМЛЕМО»), и делал что-то вполне удовлетворительное (останавливался), если H определял, что алгоритм I зависает когда он сам подается на вход (H (I, I) возвращает «СКУЧНО»). Играть было весело, и джинн развлекался этим 23,4 секунды. А на 43669-ой секунде он сделал судьбоносный шаг и решил посмотреть, что будет, если подать сам алгоритм M на вход M.

Джинн рассудил, что каждый раз, когда M подается на некоторый вход, может быть два исхода: или бесконечный цикл, или результат на выходе «ДЖИНН ЛУЧШЕ ВСЕХ». Поэтому он рассмотрел оба эти исхода по очереди.

Сперва он предположил, что М(М) возвращает «ДЖИНН ЛУЧШЕ ВСЕХ». В принципе это было бы неплохо. То есть, на самом деле, это было бы очень даже хорошо: так как программа M не выполнялась вечно, то программа H (M, M), которая и проверяет, завершится ли M (M), вернулась бы с результатом «ПРИЕМЛЕМО»! Однако… из самой программы M следует, что если H (M, M) вернет «ПРИЕМЛЕМО», то М будет выполняться бесконечно. Но программа М не выполнялась бесконечно, ведь она по предположению выводила результат «ДЖИНН ЛУЧШЕ ВСЕХ». Уфф!

Итак, рассуждал джинн, алгоритм M должен бесконечно зацикливаться, если на его вход подается М. Но это означает, как он понял, что H (M, M) вернулась бы с результатом «СКУЧНО», однако парадокс в том, что тогда M выдал бы результат «ДЖИНН ЛУЧШЕ ВСЕХ». Уфф!

Джинн до глубины души ненавидел парадоксы. Но он не мог найти способ обойти это противоречие. Как только он допускал, что может написать безошибочный алгоритм H (A, I), из этого сразу следовало, что он может написать алгоритм M, результат действия которого, если его применять к нему самому, окажется парадоксален. Единственное, что оставалось джинну — это признаться самому себе, что написать идеальный алгоритм H (A, I) невозможно.

Этот вывод взбесил джинна. Мало того, что он застрял в крошечной лампе в крошечной пещере, так еще и прямая логика не могла ему подсказать, чего он не мог делать! Однако в течение следующих 63 миллиардов секунд он с этим примирился. И решил, что если он хочет понять, работает ли алгоритм нормально или содержит бесконечный цикл, то ему лучше просто передать его в блоб джинниума, подождать и посмотреть на результат. (Примерно через 73,3 миллиарда секунд человек по имени Алан Тьюринг пришел к похожему заключению[56].)

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

Когда путник сказал «Ты должен знать, что я буду делать!», джинн с этим согласился и на скорую руку