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

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

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

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

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

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

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

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

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

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

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

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