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

Посмотрим, как Тьюринг справился с проблемой разрешения. Сначала он предположил, что мечту Гильберта можно воплотить в реальность, то есть существует механический метод, позволяющий за конечное время определить, является данное высказывание истинным или ложным. В частности, этот алгоритм позволяет оценить истинность высказывания «Машина Тьюринга Т останавливается, когда на ее вход подается значение 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 были лишены какого-либо значения. Мы всегда выбирали между белым и черным. В следующей главе мы попытаемся описать мир оттенками серого — более естественно, но менее четко.

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

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