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

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

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

Две вычислимые функции (англ. computable function) [math]f_1[/math] и [math]f_2[/math] равны при заданных аргументах, если при этих аргументах вычисляющие программы для этих функций зависают, либо равны значения, возвращаемые ими: [math]f_1(x) = f_2(x)[/math] [math]f_1(x) = \bot[/math] и [math] f_2(x) = \bot[/math]

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

Функция [math]U : \mathbb{N}\ \times \mathbb{N}\ \rightarrow \mathbb{N}\ \cup \lbrace \bot \rbrace[/math] называется универсальной (англ. universal function) для класса вычислимых функций одного аргумента, если [math]\forall n \in \mathbb{N}\[/math] [math]U_n(x) = U(n, x)[/math] («сечение» функции [math]U[/math] при фиксированном [math]n[/math]) является вычислимой функцией и для любой вычислимой функции [math]f[/math] [math]\exists n \in \mathbb{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] — вычислима, значит [math]U(n,x)[/math] — универсальная функция.

[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 \mathbb{N}\ : f(x) = p_n(x) = U(n, x)[/math]. [math]\forall n \in \mathbb{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 \mathbb{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-[/math] универсальная функция, соответствующая главной нумерации. Множество тех [math]n[/math], при которых функция [math]U_n[/math] является нигде не определённой, неразрешимо.

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

[math]\triangleright[/math]

Покажем, что если бы это множество было разрешимо, то любое перечислимое множество было бы разрешимо (что не так). Пусть [math]W-[/math] произвольное перечислимое неразрешимое множество. Введем функцию [math]V[/math] от двух аргументов такую, что [math]V(n,x) = 0[/math] если [math] n \in W [/math], и неопределенную в противном случае. Эта функция имеет сечения двух типов: сечение есть нулевая функция, либо нигде не определенная функция. Поскольку [math] U [/math] соответствует главной нумерации, то существует вычислимая всюду определённая функция [math]s[/math] такая, что [math]V (n, x) = U(s(n), x)[/math] для любых [math]n[/math] и [math]x[/math], то есть [math]V_n = U_{s(n)}[/math]. Тогда при [math] n \in W [/math] значение [math]S_n[/math] есть [math]U[/math]-номер нулевой функции, иначе [math]U[/math]-номер нигде не определенной функции. Поэтому если бы множество [math]U[/math]-номеров нигде не определённой функции разрешалось бы некоторым алгоритмом, то применяя этот алгоритм к [math]s(n)[/math] мы могли бы узнать принадлежность [math]n[/math] к множеству [math]W[/math]. То есть множество [math]W[/math] было бы разрешимым в противоречии с нашим предположением.

[math]\triangleleft[/math]

Также мы можем заключить, что нигде не определённая функция имеет бесконечно много номеров в любой главной нумерации (множество номеров нигде не определённой функции неразрешимо, а любое конечное множество разрешимо). А также отметим, что множество номеров нигде не определённой функции не только не разрешимо, но и не перечислимо. Его дополнение [math]-[/math] множество всех номеров всех функций с непустой областью определения — перечислимо (При вычислении [math]U(n,x)[/math] для всех [math]n, x[/math] мы можем печатать те [math]n[/math], для которых нашло [math]x[/math] такое, что [math]U(n,x)[/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. ISBN 5-900916-36-7

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

• Wikipedia — Godel numbering