Коллектив авторов - Теорема Геделя о неполноте [Фейк]

Из теоремы Геделя непосредственно следует алгоритмическая неразрешимость проблемы распознавания истинности любых замкнутых формул достаточно содержательно богатой формальной системы. Однако, существование алгоритмически неразрешимых проблем можно показать и независимо от теоремы Геделя. В теории алгоритмов получено большое число результатов, касающихся неразрешимости тех или иных массовых проблем (см., например, (14 )). Наиболее известные результаты - это алгоритмическая неразрешимость так называемой "десятой проблемы Гильберта" (проблемы отыскания единого метода решения произвольных диофантовых уравнений - алгебраических уравнений, решения которых ищутся в целых числах), а также - одни из наиболее простых результатов теории алгоритмов - алгоритмическая неразрешимость "проблемы остановки".

Для дальнейшего анализа нам было бы весьма полезно рассмотреть каким образом доказываются подобные результаты. Рассмотрим, к примеру, как доказывается алгоритмическая неразрешимость "проблемы остановки". "Проблема остановки" - это проблема поиска универсального алгоритма, позволяющего по записи произвольного алгоритма (например, функциональной таблицы машины Тьюринга), а также по записи произвольного "входа" - установить остановится ли вычислительное устройство, действующее в соответствие с данным алгоритмом и обрабатывающее данный "вход", или же оно будет работать бесконечно долго.

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

Эта теорема доказывается весьма просто. Первый шаг заключается в том, что вводится понятие самоприменимости алгоритма. Алгоритм называется самоприменимым, если он эффективно перерабатывает текст, соответствующий его собственной записи, в некоторый результат за конечное число шагов. В противном случае - если алгоритм не останавливается, продолжает работать бесконечно долго - то он называется несамоприменимым.

Вначале доказывается следующее утверждение: не существует алгоритма применимого ко всем несамоприменимым алгоритмам и только к ним. Доказательство заключается в указании на противоречивость понятия о таком алгоритме. Зададимся вопросом: является ли данный алгоритм самоприменимым? Если он самоприменим, то, очевидно, он несамоприменим (поскольку применим лишь к несамоприменимым алгоритмам). Если же он несамоприменим, то он самоприменим (поскольку применим ко всем несамоприменимым алгоритмам).

Исходя из этого результата можно также доказать несуществование алгоритма, способного универсальным образом распознавать несамоприменимость произвольных алгоритмов. Действительно, если такой алгоритм существует, то можно построить и алгоритм, применимый ко всем несамоприменимым алгоритмам и только к ним.

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

1. Выполнить В, перейти к п. 2.

2. Если получен ответ "да", то перейти к п. 3, в противном случае перейти к п. 4.

3. Окончить процесс.

4. Перейти к п. 4.

Этот алгоритм останавливается, если рассматриваемый в качестве входа алгоритм несамоприменим, и не останавливается (зацикливает на п. 4) в противном случае.

Используя данный результат можно также показать, что не существует и алгоритм, распознающий универсальным образом самоприменимость (поскольку в противном случае можно построить алгоритм, который распознает несамоприменимость).

И, наконец, можно показать, что алгоритмически неразрешимой является проблема распознавания применимости произвольного алгоритма к произвольному "входу". Допустим обратное. Пусть Е - алгоритм, который по заданному произвольному алгоритму и заданному на входе "слову" распознает применимость данного алгоритма к данному "слову". Нетрудно построить алгоритм, который позволяет установить является ли заданное "слово" кодом данного алгоритма. Обозначим такой алгоритм буквой Р.

Тогда можно построить алгоритм Н:

1. Применить Р. Перейти к п. 2.

2. Если Р дал ответ "да", перейти к п. 3, иначе - к п. 4.

3. Выполнить алгоритм Е. Конец.

4. Перейти к п. 4.

Алгоритм Н является алгоритмом, распознающим самоприменимость произвольных алгоритмов. Следовательно, он не возможен, а значит не возможен и алгоритм Е.

Итак, существуют алгоритмически неразрешимые проблемы и, соответственно, алгоритмически невычислимые функции. Доказательство невычислимости, как мы видели, осуществляется путем "редукции к абсурду", т.е. показывается, что из предположения о существовании алгоритма, вычисляющего данную функцию, вытекает существование абсурдного, внутренне противоречивого объекта, вроде алгоритма применимого ко всем несамоприменимым алгоритмам и только к ним.

Как отмечалось выше, геделевский аргумент можно сформулировать как утверждение об алгоритмической невычислимости функции сознания. Невозможно написать программу для машины Тьюринга или любой другой универсальной вычислительной машины, которая была бы способна имитировать работу человеческого мозга и, таким образом, имитировать в любых ситуациях поведение человека. Этот аргумент можно сформулировать и несколько иначе, в виде утверждения, что человек обладает способностью решать алгоритмически неразрешимые проблемы. Эти формулировки, однако, не являются эквивалентными. В самом деле, любая подлинно случайная последовательность является "невычислимой" в том смысле, что никакой алгоритм не позволит нам гарантированно предсказать каждый следующий элемент в этой последовательности. Но отсюда, однако, не следует, что генератор случайных чисел может оказать нам какое-то содействие в решении каких-либо конкретных алгоритмически неразрешимых проблем.

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

Итак, мы выяснили суть геделевского аргумента. Впервые данный аргумент был, видимо сформулирован Дж. Лукасом в 1961 году в статье (1).

В последнее время подобные идеи активно отстаивает Р. Пенроуз (2, 3, 11). Пенроуз, в частности, использует геделевский аргумент для обоснования тезиса о квантовой природе человеческого сознания. (Этот вопрос мы более подробно рассмотрим ниже). Рассмотрим вкратце ту форму, которую Пенроуз придает геделевскому аргументу.