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

Материал из Викиконспекты
Перейти к: навигация, поиск

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

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

Определение:
Функция [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] называется диагональной (отсюда и пошло название метода).

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

Определение:
Нумерация (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]U(n,x)[/math]- произвольная вычислимая универсальная функция. Теперь возьмем перечислимое множество [math]D[/math] всех [math]U[/math]-номеров всех функций таких, что их область определения непуста. Пусть функция [math]d[/math] есть всюду определенная функция перечисляющая множество [math]D[/math]. Рассмотрим функцию [math]V(i, x)[/math], для которой [math]V(0, x)[/math] не определено ни при каком [math]x[/math], а [math]V(i+1, x) = U(d(i), x)[/math]. То есть, функция [math]V_0[/math] нигде не определена, а функция [math]V_{i+1}[/math] совпадает с [math]U_{d(i)}[/math]. Очевидно, функция [math]V[/math] вычислима и универсальна (по построению), а единственным [math]V[/math]-номером нигде не определённой функции является число [math]0[/math]. Тогда нумерация, соответствующая этой функции является неглавной.

Литература

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

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

Godel numbering on Wiki