Хавьер Фресан - Том. 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 ). Но что произойдет, если на вход С подать саму машину С , то есть соответствующее ей число с ?

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