§ 12.11. Тезис Чёрча

Вернемся к поставленной нами задаче — построить класс вычислимых функций. Рещая эту задачу, мы последовательно построили класс элементарных функций, затем класс примитивно-рекурсивных функций и, наконец, класс общерекурсивных функций. Решили ли мы поставленную задачу? Потребуется ли нам расширять и класс общерекурсивных функций?

Многочисленные попытки расширения класса общерекурсивных функций не привели к успеху. В 1936 г. Чёрч выдвинул тезис, согласно которому всякая эффективно вычислимая функция (эффектно разрешимый предикат) является общерекурсивной (см. [110]).

В силу этого тезиса класс вычислимых функций совпадает с классом общерекурсивных функций.

Тезис Чёрча нельзя доказать, так как в нем, с одной стороны, фигурирует расплывчатое понятие вычислимой функции, а с другой стороны — точное математическое понятие общерекурсивной функции. Этот тезис является научной гипотезой, в пользу которой высказан ряд важных доводов и которую не удалось опровергнуть. Одним из таких доводов является то, что различные уточнения понятия «алгоритм», сделанные разными авторами, оказались равносильными. Так, например, описанный в § 12.4 нормальный алгоритм Маркова оказался сводимым к общерекурсивным функциям.

Выше мы отождествили понятия «алгоритм» и «вычисление значений арифметической функции».

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

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

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

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

Первый пример. Мы могли бы получить полное представление о том, какие системы равенств Е определяют общерекурсивные функции, и смогли бы эффективно перенумеровать все общерекурсивные функции, если бы имелся алгоритм, позволяющий по гёделевскому номеру системы равенств Е узнать, определяет ли система Е общерекурсивную функцию.

Иначе говоря, проблема была бы решена, если бы существовала, например, такая общерекурсивная функция :

Удалось доказать [42], что подобной общерекурсивной функции не существует. Поэтому оказывается алгоритмически неразрешимой проблема распознавания того, какие системы Е определяют общерекурсивные функции. Множество общерекурсивных функций оказалось счетным, но не эффективно.

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

(12.32)

(для предиката, соответственно ) .

Так как примитивно-рекурсивные функции могут быть эффективно перенумерованы, то задача может быть сведена к нахождению такой вычислимой функции :

Эта функция оказалась не общерекурсивной и, следовательно, невычислимой.

Условие (12.32) можно несколько ослабить, и все-таки задача остается алгоритмически неразрешимой.

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

Алгоритмически неразрешима также следующая задача: для любого примитивно-рекурсивного предиката узнать, справедливо ли

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

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

В гл. VIII и IX таким методом доказана алгоритмическая неразрешимость двух основных проблем теории конечных автоматов и последовательностных машин.