Универсальная функция — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение универсальной функции)
(Вычислимость универсальной функции)
Строка 17: Строка 17:
 
{{Теорема
 
{{Теорема
 
|statement = Для класса вычислимых функций одного аргумента существует вычислимая универсальная функция.
 
|statement = Для класса вычислимых функций одного аргумента существует вычислимая универсальная функция.
|proof = Занумеруем программы нашего языка натуральными числами. Рассмотрим функцию <tex>U(n, x) = p_n(x)</tex>, где <tex>p_n</tex> — <tex>n</tex>-ая программа в указанной нумерации. <tex>\forall</tex> вычислимой функции <tex>f</tex> <tex>\exists n \in N : f(x) = p_n(x) = U(n, x)</tex>. <tex>\forall n \in N</tex> <tex>U_n(x) = U(n, x) = p_n(x)</tex>, очевидно, является вычислимой функцией. Значит <tex>U(n, x)</tex> — универсальная функция для класса вычислимых функций одного аргумента. Очевидно, что <tex>U(n, x)</tex> вычислима. Действительно, для того, чтобы вычислить <tex>U(n, x)</tex>, достаточно вернуть вывод программы <tex>p_n</tex> на входе <tex>x</tex>.
+
|proof = Занумеруем программы нашего языка натуральными числами. Рассмотрим функцию <tex>U(n, x) = p_n(x)</tex>, где <tex>p_n</tex> — <tex>n</tex>-ая программа в указанной нумерации. Для любой вычислимой функции <tex>f</tex> <tex>\exists n \in N : f(x) = p_n(x) = U(n, x)</tex>. <tex>\forall n \in N</tex> <tex>U_n(x) = U(n, x) = p_n(x)</tex>, очевидно, является вычислимой функцией. Значит <tex>U(n, x)</tex> — универсальная функция для класса вычислимых функций одного аргумента. Очевидно, что <tex>U(n, x)</tex> вычислима. Действительно, для того, чтобы вычислить <tex>U(n, x)</tex>, достаточно вернуть вывод программы <tex>p_n</tex> на входе <tex>x</tex>.
 
}}
 
}}
 
{{Теорема
 
{{Теорема
Строка 24: Строка 24:
 
}}
 
}}
 
Отметим, что функция <tex>u(n) = U(n, n)</tex> называется диагональной (отсюда и пошло название метода).
 
Отметим, что функция <tex>u(n) = U(n, n)</tex> называется диагональной (отсюда и пошло название метода).
 
  
 
===Главная нумерация===
 
===Главная нумерация===

Версия 22:14, 18 января 2014

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

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

Определение:
Функция [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]

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

Литература

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

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

Godel numbering on Wiki