Вычислимость и разрешимость

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

Тезис Черча. Числовая функция тогда и только тогда алгоритмически вычислима, когда она частично рекурсивна.

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

Подмножество множества натуральных чисел M⊂Nназывается разрешимым, если его характеристическая функция

χ_M(x)=1 при x∈M, χ_M(x)=0 при x∉M

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

Подмножество множества натуральных чисел M⊂Nназывается перечислимым, если оно является областью значений некоторой общерекурсивной функции f. Перечислимость множества M означает, что его элементы могут быть последовательно выписаны (возможно с повторениям) с помощью некоторой эффективной процедуры. Всякое непустое разрешимое множество M является перечислимым.

Доказательство. Несложно определить перечисляющую функцию f. Пусть m – произвольный элемент множества M. Определяем по рекурсии:

f(0)=m; f(x+1)=χ_M(x)(x+1)+(1−χ_M(x+1))f(x),

то есть f(x+1)=x+1, если x+1∈M, и f(x+1)=f(x), если x+1∉M.􀀀

Обратное, вообще говоря, неверно. Не всякое перечислимое множество является разрешимым. Перечислимое множество разрешимо лишь в том случае, когда перечислимо также и его дополнение.

В конце п. 4.4 было показано, что частично рекурсивные функции можно эффективно перенумеровать, используя их рекурсивные описания. Некоторые номера соответствуют общерекурсивным функциям. Обозначим множество таких номеров через M и покажем, что множество M неперечислимо.

Теорема.Множество номеров общерекурсивных функций не перечислимо.

Доказательство. Предположим противное. Пусть ϕ(x) – общерекурсивная функция, множеством значений которой является M. Тогда последовательность ϕ(0), ϕ(1), ϕ(2),… содержит номера всех общерекурсивных функций, и только их. Следуя диагональному методу, определим функцию g(x) формулой

g(x)=f_ϕ(x)(x)+1.

Это определение дает алгоритм вычисления значений функции g(x). В соответствии с тезисом Черча, функция g(x) частично рекурсивна, и, значит, общерекурсивна, поскольку функция g(x) определена для любого x. Значит, функция g(x) должна получить свой номер при перечислении с помощью ϕ(x). Пусть этот номер равен n, то есть g(x)=f_ϕ(n)(x). Но тогда g(n)=f_ϕ(n)(n)+1=g(n)+1, что невозможно.􀀀

Вообще неперечислимые и неразрешимые семейства функций – это не «экзотика», а, скорее, норма.

Приведем без доказательства следующую теорему.

Терема (Райс). Никакое нетривиальное семейство вычислимых функций не является алгоритмически разрешимым.

Иными словами, если C – некоторое семейство вычислимых функций такое, что есть функции, входящие в это семейство, а есть и не входящие в него, то множество номеров функций из C неразрешимо. Не существует алгоритма, который бы позволял по номеру функции сказать, входит она в C или нет.

Так, по номеру функции нельзя узнать, является ли она монотонной, периодической и т.п. Заметим, что, нумеруя частично рекурсивные функции, мы на самом деле нумеровали их рекурсивные описания, то есть вычисляющие их алгоритмы. Теорема Райса утверждает, что по номеру алгоритма нельзя узнать, периодична ли, например, функция, вычисляемая в соответствии с этим алгоритмом.