18. Проблема зависания

(Проклятая арабская пещера, 1610 год)

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

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

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

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

Сет Ллойд

За 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 миллиарда секунд человек по имени Алан Тьюринг пришел к похожему заключению.)

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

Когда путник сказал «Ты должен знать, что я буду делать!», джинн с этим согласился и на скорую руку соорудил сравнительно простой проверочный алгоритм D, который при подаче на вход I определенных данных на выходе должен был выдать решение, к которому путник придет, если ситуация будет описываться с помощью данных I. Джинн запустил рутинные вычисления на одном из блоков джинниума, но результатов пришлось ждать очень долго, и джинн понял, что алгоритм зациклился, хотя и не понял, почему. Сколько времени потеряно! Следующей мыслью джинна было написать другой алгоритм, H, чтобы исправить ситуацию: он должен был бы проанализировать D и I, и если D (I) не смог бы закончить работу, он выдал бы результат «НЕИЗВЕСТНО», а в противном случае просто вернул бы алгоритм D (I).

Джинн нахмурился. В его великолепной памяти сразу всплыли воспоминания о том, что 63 миллиарда секунд назад он уже шел этим путем. Функция H, которую джинн только что планировал смастерить, была практически той же самой функцией H, которую он пытался создать тогда. Он даже использовал ту же самую букву! Таким образом, поиск этой функции был одной из тех ненавидимых джинном задач, которые он так и не сумел решить.

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

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

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