Посмотрим, как Тьюринг справился с проблемой разрешения. Сначала он предположил, что мечту Гильберта можно воплотить в реальность, то есть существует механический метод, позволяющий за конечное время определить, является данное высказывание истинным или ложным. В частности, этот алгоритм позволяет оценить истинность высказывания «Машина Тьюринга Т останавливается, когда на ее вход подается значение n». Как мы уже указывали, благодаря методу «гёделизации» мы можем сопоставить каждой машине Тьюринга число так, что в нем будет закодирована вся структура машины. Если n — число, описывающее некую машину Тьюринга, мы будем обозначать эту машину как Т(n). В этой нотации проблема, которую мы хотим решить, может быть записана так: остановится ли машина Тьюринга Т(n), если на ее вход подать число m? Следует подчеркнуть, что если идеальная машина, которую представлял себе Гильберт, существует, то она сможет дать ответ на этот вопрос не в каких-то конкретных случаях, а для любых значений m и n.
Следовательно, речь идет о функции двух переменных, которая для данной пары чисел (m, n) определяет, остановится ли машина Тьюринга, описываемая числом n, когда ей на вход будет подана лента, на которой будет записано число m. Вернемся к примеру с числом π и обозначим за f число машины Тьюринга, которая просматривает десятичные знаки π в поиске требуемой последовательности. При вводе параметров (9, f) наша функция вернет значение 1, если среди знаков π обнаружится последовательность из девяти девяток подряд (так как в этом случае машина остановится), в противном случае — 0 (в этом случае машина будет продолжать работу бесконечно).
Если мы предположим, что существует машина Тьюринга Р, решающая эту проблему, мы получим противоречие. Чтобы убедиться в этом, повторим еще раз принцип действия Р: это машина Тьюринга, на вход которой подаются пары чисел (m, n) и выходным значением которой может быть одно из двух значений: 1, если машина Тьюринга Т(n) при заданном исходном значении m в определенный момент остановится, и 0 — в противном случае. Иными словами, либо не существует машины Тьюринга, обозначаемой числом n (так как не все натуральные числа обозначают какую-либо машину Тьюринга), или же она существует, но программа выполняется бесконечно долго при введенном параметре m. Такая программа, представляющая собой настоящий кошмар для специалистов по информатике, называется бесконечным циклом. Здесь важно, что если бы в нашем распоряжении находилась такая машина Т, мы с легкостью смогли бы создать другую машину Тьюринга (обозначим ее через С), входным значением которой было бы одно число m и которая действовала бы следующим образом:
— если машина Тьюринга Т(n) останавливается, когда ее входное значение равно n (иными словами, если Р(n, n) равно 1), то С не остановится никогда;
— если машина Тьюринга Т(n) бесконечно долго продолжает работу, если ее входное значение равно n (иными словами, если Р(n, n) равно 0), то С остановится, едва начав работу.
В главе 2 вы увидели, как возникает парадокс лжеца, лишивший покоя мудреца Эпименида: это происходит, когда критянин говорит, что все критяне — лжецы, или когда высказывание описывает само себя так: «это высказывание ложно». Далее мы показали, как Гёдель использовал самоотносимость для формулировки истинного, но недоказуемого высказывания, гласящего: «это высказывание недоказуемо». Теперь читатель наверняка догадается, как следует закончить рассуждения: мы определили машину Тьюринга С, которая останавливается или безостановочно продолжает работу в зависимости от того, как работает другая машина, Т(n). Но что произойдет, если на вход С подать саму машину С, то есть соответствующее ей число с?
Если машина Т(с) остановится, то С не остановится. Если, напротив, Т(с) войдет в бесконечный цикл, то С остановится. Но С и Т(с) — это одна и та же машина! Она не может одновременно вести себя по-разному! Предположив, что проблема остановки имеет решение для любых шип, мы пришли к противоречию: демон самоотносимости нашептывает нам «выбери с», но одна и та же машина будет одновременно вести себя по-разному.
Мечта Гильберта и Лейбница оказалась несбыточной. Самоотносимость сначала побудила Бертрана Рассела сформировать новые, более прочные основы математики, затем позволила Геделю доказать, что оптимизм ученых того времени был неоправданным, а теперь Тьюринг вновь использовал ее, чтобы справиться с проблемой разрешения — на этот раз самоотносимость стала свойством теоретических машин, которые позднее дали начало первым компьютерам.
Мы сказали, что логика описывает не рассуждения повседневной жизни, а способ, которым нужно рассуждать, чтобы гарантированно прийти к истинному результату. В самом деле, пока что мы рассматривали только формулы, в которых значения истинности 0 и 1 были лишены какого-либо значения. Мы всегда выбирали между белым и черным. В следующей главе мы попытаемся описать мир оттенками серого — более естественно, но менее четко.
Глава 6Хорошо кончается то, что не кончается
Чтобы получить даже мельчайшую крупицу нового знания, требуется долгое и трудное самоотречение, пойти на которое готовы лишь немногие, чистые душой.
Маргерит Дюрас
Возможно, он знал, что делал, когда повел ее в ресторан, куда ходили только японцы. Возможно, он не сомневался в своем обаянии. Если ему не удастся поразить спутницу начитанностью и рассказами о своих путешествиях, он еще может спасти свидание, удивив ее одним из экзотических блюд. Когда официантка, не столь красивая, как того требует история, осведомилась о выборе десерта, все складывалось благополучно. Он немного знал японский, поэтому когда официантка спросила, как следует приготовить чайный трюфель: «со сливками, без сливок или как-то еще», мужчина, хоть и был несколько смущен, тем не менее решительно сказал: «Как-то еще». Вскоре официантка вернулась и, улыбаясь, подала тарелку трюфелей, на которой было налито совсем немного сливок, не касавшихся самого блюда. Мужчина и женщина посмотрели друг на друга и одновременно сказали: «Проклятые азиаты! Им неизвестен принцип непротиворечивости».
Несмотря на внешние различия, все множества, которые мы рассмотрели до этого, обладали одним общим свойством: для любого элемента и любого множества на вопрос «Принадлежит ли этот элемент множеству?» можно было дать только один ответ: да или нет. Описание множества могло быть каким угодно сложным, но ответом на этот вопрос обязательно было бы «да» или «нет». Именно это произошло в примере с числами, десятичная запись которых содержит все возможные последовательности и о которых мы рассказали в предыдущей главе. Неизвестно, принадлежит π этому множеству или нет, но в любом случае на этот вопрос можно дать только один ответ. Предложения логики также подчиняются этой схеме: они либо истинны, либо ложны, и любая другая возможность исключается. Более того, два основных парадокса, которые мы рассмотрели (парадокс Рассела и парадокс лжеца), возникают именно тогда, когда даже с теоретической точки зрения невозможно ответить на вопрос «да» или «нет», невозможно определить, принадлежит некий элемент множеству или нет. Дело не в том, что закон исключенного третьего допускает исключения, а в том, что множество всех множеств, которые не являются элементами самого себя, и выражение «эта фраза ложна» формально некорректны, потому что отношение принадлежности справедливо только для объектов разных типов, а также потому, что понятие истинности принадлежит не языку, а метаязыку.
В некотором смысле теория множеств и логика находятся на вершине отвесной скалы: истинное расположено на самом краю, и достаточно легкого дуновения ветерка, чтобы отправиться в свободное падение по направлению к ложному. Однако большую часть земной поверхности занимают не отвесные скалы, а пологие склоны.
Несколько лет назад во многих странах произвела настоящий фурор настольная игра Scattergories. В этой игре нужно выбрать любую букву алфавита, а затем записать слова из разных областей, которые начинаются с этой буквы. Например, если нам дан список «Спорт. Названия песен. Части тела. Национальная кухня. Оскорбления» и после броска игральной кости, которая имеет форму икосаэдра, выпала буква «К», ответ может звучать так: «Кёрлинг. «Катюша». Колено. Кулебяка. Кретин!». В рекламе игры Scattergories расстроенный мальчик уходит из дома, унося игру с собой, потому что его друзья сказали, что «корабль» не относится к категории «морские животные». В конце концов они решают уступить ему, так как хотят продолжить игру, но в следующем туре мальчик вновь принимается за старое: когда выпадает буква «О», он спрашивает друзей: «А осьминога можно назвать домашним животным?»
В то время как некоторых живых существ затруднительно причислить к животным, множество домашних животных определено еще хуже: к нему, конечно же, принадлежат кошки и собаки, и так же совершенно однозначно в него не входят волки и слоны. Однако хотя некоторые причислят тарантулов к множеству «животных, к которым я не хочу подходить ближе, чем на километр», другие развлекаются тем, что бросают тарантулам сверчков между прутьями клетки. Так же нечетко, как и множество домашних животных, определены и другие множества, с которыми мы имеем дело каждый день, например множество красивых людей, хороших ресторанов и смешных шуток. Первым предложил теорию, описывающую подобные ситуации, польский логик Ян Лукасевич (1878–1956). В 1917 году он представил трехзначную логику, в которой высказывания могли быть не только истинными или ложными, но и «возможными». Например, человек ростом 1,50