Диагональный метод

Определение:

Функция [math]U : N \times N \rightarrow N \cup \lbrace \bot \rbrace[/math] называется универсальной (universal function) для класса вычислимых функций одного аргумента, если [math]\forall n \in N[/math] [math]U_n(x) = U(n, x)[/math] является вычислимой функцией и [math]\forall[/math] вычислимой функции [math]f[/math] [math]\exists n \in N : f(x) = U(n, x)[/math]

Менее формально, для универсальной функции должно выполняться следующее: "сечение" функции [math] U_n [/math] является вычислимой функцией и все вычислимые функции одного аргумента встречаются среди [math]U_n[/math] (отсюда универсальность). Универсальная функция нужна, например, для того, чтобы показать, что существует перечислимое неразрешимое множество (на самом деле это множество таких [math] n [/math], для которых [math] U(n, n) [/math] определено).

Аналогично определяется универсальная функция для класса всюду определенных вычислимых функций одного аргумента.

Теорема:

Для класса вычислимых функций одного аргумента существует вычислимая универсальная функция.

Доказательство:

[math]\triangleright[/math]

Занумеруем программы нашего языка натуральными числами. Рассмотрим функцию [math]U(n, x) = p_n(x)[/math], где [math]p_n[/math] — [math]n[/math]-ая программа в указанной нумерации. [math]\forall[/math] вычислимой функции [math]f[/math] [math]\exists n \in N : f(x) = p_n(x) = U(n, x)[/math]. [math]\forall n \in N[/math] [math]U_n(x) = U(n, x) = p_n(x)[/math], очевидно, является вычислимой функцией. Значит [math]U(n, x)[/math] — универсальная функция для класса вычислимых функций одного аргумента. Очевидно, что [math]U(n, x)[/math] вычислима. Действительно, для того, чтобы вычислить [math]U(n, x)[/math], достаточно вернуть вывод программы [math]p_n[/math] на входе [math]x[/math].

[math]\triangleleft[/math]

Теорема:

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

Доказательство:

[math]\triangleright[/math]

От противного. Пусть [math]U(n, x)[/math] — всюду определенная вычислимая универсальная функция для класса всюду определенных вычислимых функций одного аргумента. Воспользуемся теперь диагональным методом. Рассмотрим всюду определенную вычислимую функцию одного аргумента [math]d(x) = U(x, x) + 1[/math]. [math]\exists n \in N : d(x) = U(n, x)[/math] в силу того, что [math]U(n, x)[/math] — универсальная для соответствующего класса функций. Так как [math]d(x)[/math] всюду определена, то она не зависает на аргументе [math]n[/math]. Значит [math]d(n) = U(n, n)[/math], но в то же время [math]d(n) = U(n, n) + 1[/math]. Противоречие.

[math]\triangleleft[/math]

Отметим, что функция [math]u(n) = U(n, n)[/math] называется диагональной (отсюда и пошло название метода).

Литература

Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999, с. 16

В. А. Успенский Лекции о вычислимых функциях — М.: ГИФМЛ, 1960, с. 203