Диагональный метод — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 11: Строка 11:
 
|proof = От противного. Пусть <tex>U(n, x)</tex> — всюду определенная вычислимая универсальная функция для класса всюду определенных вычислимых функций одного аргумента. Воспользуемся теперь диагональным методом. Рассмотрим всюду определенную вычислимую функцию одного аргумента <tex>d(x) = U(x, x) + 1</tex>. <tex>\exists n \in N : d(x) = U(n, x)</tex> в силу того, что <tex>U(n, x)</tex> — универсальная для соответствующего класса функций. Так как <tex>d(x)</tex> всюду определена, то она не зависает на аргументе <tex>n</tex>. Значит <tex>d(n) = U(n, n)</tex>, но в то же время <tex>d(n) = U(n, n) + 1</tex>. Противоречие.
 
|proof = От противного. Пусть <tex>U(n, x)</tex> — всюду определенная вычислимая универсальная функция для класса всюду определенных вычислимых функций одного аргумента. Воспользуемся теперь диагональным методом. Рассмотрим всюду определенную вычислимую функцию одного аргумента <tex>d(x) = U(x, x) + 1</tex>. <tex>\exists n \in N : d(x) = U(n, x)</tex> в силу того, что <tex>U(n, x)</tex> — универсальная для соответствующего класса функций. Так как <tex>d(x)</tex> всюду определена, то она не зависает на аргументе <tex>n</tex>. Значит <tex>d(n) = U(n, n)</tex>, но в то же время <tex>d(n) = U(n, n) + 1</tex>. Противоречие.
 
}}
 
}}
Отметим, что функция <tex>u(n) = U(n, n)</tex> называется диагональной функцией (отсюда и пошло название метода).
+
Отметим, что функция <tex>u(n) = U(n, n)</tex> называется диагональной (отсюда и пошло название метода).
 
== Литература ==
 
== Литература ==
 
[http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf ''Н. К. Верещагин,  А. Шень.'' '''Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции.''' — М.: МЦНМО, 1999, с. 16]
 
[http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf ''Н. К. Верещагин,  А. Шень.'' '''Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции.''' — М.: МЦНМО, 1999, с. 16]

Версия 14:31, 13 января 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]\forall[/math] вычислимой функции [math]f[/math] [math]\exists n \in N : f(x) = U(n, x)[/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