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

За 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) невозможно.