Том. 22. Сон разума. Математическая логика и ее парадоксы - Хавьер Фресан

— если машина Тьюринга Т(n) останавливается, когда ее входное значение равно n (иными словами, если Р(n, n) равно 1), то С не остановится никогда;

— если машина Тьюринга Т(n) бесконечно долго продолжает работу, если ее входное значение равно n (иными словами, если Р(n, n) равно 0), то С остановится, едва начав работу.

В главе 2 вы увидели, как возникает парадокс лжеца, лишивший покоя мудреца Эпименида: это происходит, когда критянин говорит, что все критяне — лжецы, или когда высказывание описывает само себя так: «это высказывание ложно». Далее мы показали, как Гёдель использовал самоотносимость для формулировки истинного, но недоказуемого высказывания, гласящего: «это высказывание недоказуемо». Теперь читатель наверняка догадается, как следует закончить рассуждения: мы определили машину Тьюринга С, которая останавливается или безостановочно продолжает работу в зависимости от того, как работает другая машина, Т(n). Но что произойдет, если на вход С подать саму машину С, то есть соответствующее ей число с?

Если машина Т(с) остановится, то С не остановится. Если, напротив, Т(с) войдет в бесконечный цикл, то С остановится. Но С и Т(с) — это одна и та же машина! Она не может одновременно вести себя по-разному! Предположив, что проблема остановки имеет решение для любых шип, мы пришли к противоречию: демон самоотносимости нашептывает нам «выбери с», но одна и та же машина будет одновременно вести себя по-разному.

Мечта Гильберта и Лейбница оказалась несбыточной. Самоотносимость сначала побудила Бертрана Рассела сформировать новые, более прочные основы математики, затем позволила Геделю доказать, что оптимизм ученых того времени был неоправданным, а теперь Тьюринг вновь использовал ее, чтобы справиться с проблемой разрешения — на этот раз самоотносимость стала свойством теоретических машин, которые позднее дали начало первым компьютерам.

Мы сказали, что логика описывает не рассуждения повседневной жизни, а способ, которым нужно рассуждать, чтобы гарантированно прийти к истинному результату. В самом деле, пока что мы рассматривали только формулы, в которых значения истинности 0 и 1 были лишены какого-либо значения. Мы всегда выбирали между белым и черным. В следующей главе мы попытаемся описать мир оттенками серого — более естественно, но менее четко.

Глава 6

Хорошо кончается то, что не кончается

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

Маргерит Дюрас

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

Несмотря на внешние различия, все множества, которые мы рассмотрели до этого, обладали одним общим свойством: для любого элемента и любого множества на вопрос «Принадлежит ли этот элемент множеству?» можно было дать только один ответ: да или нет. Описание множества могло быть каким угодно сложным, но ответом на этот вопрос обязательно было бы «да» или «нет». Именно это произошло в примере с числами, десятичная запись которых содержит все возможные последовательности и о которых мы рассказали в предыдущей главе. Неизвестно, принадлежит π этому множеству или нет, но в любом случае на этот вопрос можно дать только один ответ. Предложения логики также подчиняются этой схеме: они либо истинны, либо ложны, и любая другая возможность исключается. Более того, два основных парадокса, которые мы рассмотрели (парадокс Рассела и парадокс лжеца), возникают именно тогда, когда даже с теоретической точки зрения невозможно ответить на вопрос «да» или «нет», невозможно определить, принадлежит некий элемент множеству или нет. Дело не в том, что закон исключенного третьего допускает исключения, а в том, что множество всех множеств, которые не являются элементами самого себя, и выражение «эта фраза ложна» формально некорректны, потому что отношение принадлежности справедливо только для объектов разных типов, а также потому, что понятие истинности принадлежит не языку, а метаязыку.

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

Несколько лет назад во многих странах произвела настоящий фурор настольная игра Scattergories. В этой игре нужно выбрать любую букву алфавита, а затем записать слова из разных областей, которые начинаются с этой буквы. Например, если нам дан список «Спорт. Названия песен. Части тела. Национальная кухня. Оскорбления» и после броска игральной кости, которая имеет форму икосаэдра, выпала буква «К», ответ может звучать так: «Кёрлинг. «Катюша». Колено. Кулебяка. Кретин!». В рекламе игры Scattergories расстроенный мальчик уходит из дома, унося игру с собой, потому что его друзья сказали, что «корабль» не относится к категории «морские животные». В конце концов они решают уступить ему, так как хотят продолжить игру, но в следующем туре мальчик вновь принимается за старое: когда выпадает буква «О», он спрашивает друзей: «А осьминога можно назвать домашним животным?»

В то время как некоторых живых существ затруднительно причислить к животным, множество домашних животных определено еще хуже: к нему, конечно же, принадлежат кошки и собаки, и так же совершенно однозначно в него не входят волки и слоны. Однако хотя некоторые причислят тарантулов к множеству «животных, к которым я не хочу подходить ближе, чем на километр», другие развлекаются тем, что бросают тарантулам сверчков между прутьями клетки. Так же нечетко, как и множество домашних животных, определены и другие множества, с которыми мы имеем дело каждый день, например множество красивых людей, хороших ресторанов и смешных шуток. Первым предложил теорию, описывающую подобные ситуации, польский логик Ян Лукасевич (1878–1956). В 1917 году он представил трехзначную логику, в которой высказывания могли быть не только истинными или ложными, но и «возможными». Например, человек ростом 1,50 м низкий, человек ростом 2 м — высокий, а тот, чей рост составляет 1,75 м, является «возможно, высоким» или «возможно, низким» — все зависит от того, с кем мы его сравниваем: с пигмеями или игроками НБА.

* * *

МЕСТЬ ЛЖЕЦА

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

* * *

Включение в перечень возможных значений истинности значения «возможно» стало настоящим прорывом за пределы черно-белого мира классической логики.