Универсальная функция

Определение универсальной функции

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

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

Функция [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]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]\Sigma[/math]. Программа будет иметь номер [math]n[/math], если ее код - [math]n[/math]-е слово среди всех слов над алфавитом [math]\Sigma[/math], отсортированных сначала по возрастанию длины, а при равной длине - в лексикографическом порядке. При этом если [math]n[/math]-я программа не компилируется, будем считать, что она всегда зависает. Рассмотрим функцию [math]U(n,x):\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}\cup\perp[/math] такую, что [math]U(n,x)=p_n(x)[/math], где [math]p_n[/math] - [math]n[/math]-я программа. Заметим, что по определению вычислимой функции существует программа, вычисляющая ее. Но в заданной нумерации у любой программы есть номер. Таким образом для любой вычислимой функции [math]f[/math] существует номер [math]n: U(n,x)=f(x)[/math]. И наоборот - [math]f_n=U(n)[/math] - является вычислимой функцией. Вычисляющая программа для [math]U[/math] содержит интерпретатор для зафиксированного языка программирования, по номеру программы (первый аргумент) восстанавливает ее код, и передает ей второй аргумент, возвращая результат ее работы. Таким образом [math]U_n(x)=U(n,x)[/math] - вычислима для любого [math]n\in\mathbb{N}[/math], и [math]\forall f(x) \exists n\in\mathbb{N}: f(x)=U(n,x)[/math], [math]f(x)[/math] - вычислима, значит U(n,x) - универсальная функция.

[math]\triangleleft[/math]

Вычислимость универсальной функции

Теорема:

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

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

[math]\triangleright[/math]

Занумеруем программы нашего языка натуральными числами. Рассмотрим функцию [math]U(n, x) = p_n(x)[/math], где [math]p_n[/math] — [math]n[/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] называется диагональной (отсюда и пошло название метода).

Перечислимое неразрешимое множество

Теорема:

Существует перечислимое неразрешимое множество

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

[math]\triangleright[/math]

Возьмем вычислимую функцию [math]f(x)[/math] не имеющую всюду определенного вычислимого продолжения. Тогда область определения [math]F[/math] этой функции будет искомым множеством. Действительно, [math]F[/math] перечислимо. Предположим, что [math]F[/math] разрешимо. Но тогда функция [math]g(x)[/math] равная [math]f(x)[/math] при [math] x \in F [/math] и равная [math]0[/math] если [math] x \notin F [/math] является вычислимым всюду определенным продолжением функции [math]f[/math]. Пришли к противоречию, значит [math]F[/math] неразрешимо.

[math]\triangleleft[/math]

Главная нумерация

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

Нумерация (numbering) множества [math]X-[/math] это такое всюду определенное отображение [math] f : \mathbb{N} \rightarrow X[/math], область значений которого есть все множество [math]X[/math].

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

Нумерация, заданная двуместной универсальной функцией [math]U(n,x)[/math] называется главной (Гёделевой) (Godel numbering), если для любой двуместной вычислимой функции [math]V(n,x)[/math] существует вычислимая, всюду определенная функция [math]S:\mathbb{N}\rightarrow\mathbb{N}[/math] такая, что [math]V(n,x)=U(S(n),x)[/math].

Теорема:

Существует главная нумерация.

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

[math]\triangleright[/math]

Рассмотрим универсальную функцию, построенную ранее, и нумерацию, соответствующую ей. Обозначим программу, вычисляющую функцию [math]V(n,x)[/math] как [math]v(n,x)[/math]. Построим программу (назовем ее [math]s[/math]) с одним параметром - [math]m[/math], которая генерирует код программы [math]v(n,x)[/math], но с фиксированным [math]n = m[/math], и возвращает ее номер в заданной нумерации. Построенная программа вычисляет искомую функцию для универсальной двуместной функции [math]U[/math] и двуместной функции [math]V[/math], то есть [math]V(n,x)=U(S(n),x)[/math], где [math]S[/math] - функция, вычисляемая программой [math]s[/math]. Из вычислимости [math]v[/math] следует существование [math]V[/math], и за конечное время мы можем вернуть номер любой программы в выбранной нумерации. Таким образом [math]S[/math] - вычислимая, всюду определенная.

[math]\triangleleft[/math]

С помощью главной нумерации можно пронумеровать все программы. Также, используя главную нумерацию не сложно определить номер программы, являющуюся композицией двух программ (то есть состоящей из двух подпрограмм и основной функции, возвращающей результат композиции исходных программ). Пусть нам необходимо по номерам функций [math]p[/math] и [math]q[/math] определить номер функции-композиции [math]p[/math] и [math]q[/math]

Теорема:

Существует такая функция [math]c[/math], которая всюду определена и которая по номерам функций [math]p[/math] и [math]q[/math] дает номер [math]c(p, q)[/math] их композиций. То есть выполняется свойство [math]U(c(p,q),x) = U(p, U(q,x))[/math]

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

[math]\triangleright[/math]

Для начала зафиксируем вычислимую нумерацию пар (взаимно однозначное соответствие [math]\langle u, v \rangle \leftrightarrow [u, v][/math] между [math] N \times N [/math] и [math]N[/math]; число [math][u, v][/math] назовем номером этой пары. Возьмем некоторую функцию [math]V([p,q],x)=U(p, U(q,x))[/math]. Исходя из определения главной нумерации существует такая вычислимая, всюду определенная функция [math]S: V(n,x)=U(s(n),x)[/math] для всех [math]n[/math] и [math]x[/math]. А тогда [math]V([p,q],x)=U(S[p,q], x)[/math], что значит функция с, определяемая как [math]c(p,q)=S([p,q])[/math], будет искомой.

[math]\triangleleft[/math]

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

Приведем пример вычислимой нумерации множества [math]R[/math]. Для этого упорядочим все дроби, образующие все множество [math]R[/math] по неубыванию суммы числителя и знаменателя. В случае равенства упорядочим по увеличению числителя. Полученная нумерация, очевидно, вычислима.

Литература

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

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

Godel numbering on Wiki