Викиконспекты - Вклад участника [ru]

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

2014-01-19T16:26:16Z

178.66.42.139: /* Главная нумерация */

===Определение универсальной функции===
В этом разделе равенство двух вычислимых функций при заданных аргументах понимается в том смысле, что при этих аргументах вычисляющие программы для этих функций зависают, либо равны значения, возвращаемые ими.
{{Определение
|definition = Функция <tex>U : N \times N \rightarrow N \cup \lbrace \bot \rbrace</tex> называется '''универсальной (universal function)''' для класса [[Вычислимые функции|вычислимых функций]] одного аргумента, если <tex>\forall n \in N</tex> <tex>U_n(x) = U(n, x)</tex> является вычислимой функцией и для любой вычислимой функции <tex>f</tex> <tex>\exists n \in N : f(x) = U(n, x)</tex>
}}
Менее формально, для универсальной функции должно выполняться следующее: "сечение" функции <tex> U_n </tex> является вычислимой функцией и все вычислимые функции одного аргумента встречаются среди <tex>U_n</tex> (отсюда универсальность). Универсальная функция нужна, например, для того, чтобы показать, что существует перечислимое неразрешимое множество (на самом деле это множество таких <tex> n </tex>, для которых <tex> U(n, n) </tex> определено).

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

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

===Вычислимость универсальной функции===
{{Теорема
|statement = Для класса вычислимых функций одного аргумента существует вычислимая универсальная функция.
|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>.
}}
{{Теорема
|statement = Для класса всюду определенных вычислимых функций одного аргумента не существует всюду определенной вычислимой универсальной функции.
|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> называется диагональной (отсюда и пошло название метода).

===Главная нумерация===
{{Определение
|definition='''Нумерация (numbering)''' множества <tex>X-</tex> это такое всюду определенное отображение <tex> f : \mathbb{N} \rightarrow X</tex>, область значений которого есть все множество <tex>X</tex>.
}}

{{Определение
|definition=Нумерация, заданная двуместной универсальной функцией <tex>U(n,x)</tex> называется '''главной (Гёделевой) (Godel numbering)''', если для любой двуместной вычислимой функции <tex>V(n,x)</tex> существует вычислимая, всюду определенная функция <tex>S:\mathbb{N}\rightarrow\mathbb{N}</tex> такая, что <tex>V(n,x)=U(S(n),x)</tex>.
}}
{{Теорема
|statement=Существует главная нумерация.
|proof=Рассмотрим универсальную функцию, построенную ранее, и нумерацию, соответствующую ей. Обозначим программу, вычисляющую функцию <tex>V(n,x)</tex> как <tex>v(n,x)</tex>. Построим программу (назовем ее <tex>s</tex>) с одним параметром - <tex>m</tex>, которая генерирует код программы <tex>v(n,x)</tex>, но с фиксированным <tex>n = m</tex>, и возвращает ее номер в заданной нумерации. Построенная программа вычисляет искомую функцию для универсальной двуместной функции <tex>U</tex> и двуместной функции <tex>V</tex>, то есть <tex>V(n,x)=U(S(n),x)</tex>, где <tex>S</tex> - функция, вычисляемая программой <tex>s</tex>. Из вычислимости <tex>v</tex> следует существование <tex>V</tex>, и за конечное время мы можем вернуть номер любой программы в выбранной нумерации. Таким образом <tex>S</tex> - вычислимая, всюду определенная.
}}

С помощью главной нумерации можно пронумеровать все программы. Также, используя главную нумерацию не сложно определить номер программы, являющуюся композицией двух программ (то есть состоящей из двух подпрограмм и основной функции, возвращающей результат композиции исходных программ). Пусть нам необходимо по номерам функций <tex>p</tex> и <tex>q</tex> определить номер функции-композиции <tex>p</tex> и <tex>q</tex>
{{Теорема
|statement=Существует такая функция <tex>c</tex>, которая всюду определена и которая по номерам функций <tex>p</tex> и <tex>q</tex> дает номер <tex>c(p, q)</tex> их композиций. То есть выполняется свойство <tex>U(c(p,q),x) = U(p, U(q,x))</tex>
|proof=Возьмем некоторую функцию <tex>V([p,q],x)=U(p, U(q,x))</tex>. Исходя из определения главной нумерации существует такая вычислимая, всюду определенная функция <tex>S: V(n,x)=U(s(n),x)</tex> для всех <tex>n</tex> и <tex>x</tex>. А тогда <tex>V([p,q],x)=U(S(p,q), x)</tex>, что значит функция с, определяемая как <tex>c(p,q)=S([p,q])</tex>, будет искомой.
}}
Отметим, что при доказательстве существования функции-композиции мы пользуемся основным свойством главной нумерации, а значит для неглавных нумерации мы не сможем построить такую функций и не сможем найти номер функции-композиции двух функций.

== Литература ==
[http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf ''Н. К. Верещагин, А. Шень.'' '''Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции.''' — М.: МЦНМО, 1999, с. 16]

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

[http://en.wikipedia.org/wiki/G%C3%B6del_numbering Godel numbering on Wiki]

[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]

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

2014-01-19T16:04:11Z

178.66.42.139:

===Определение универсальной функции===
В этом разделе равенство двух вычислимых функций при заданных аргументах понимается в том смысле, что при этих аргументах вычисляющие программы для этих функций зависают, либо равны значения, возвращаемые ими.
{{Определение
|definition = Функция <tex>U : N \times N \rightarrow N \cup \lbrace \bot \rbrace</tex> называется '''универсальной (universal function)''' для класса [[Вычислимые функции|вычислимых функций]] одного аргумента, если <tex>\forall n \in N</tex> <tex>U_n(x) = U(n, x)</tex> является вычислимой функцией и для любой вычислимой функции <tex>f</tex> <tex>\exists n \in N : f(x) = U(n, x)</tex>
}}
Менее формально, для универсальной функции должно выполняться следующее: "сечение" функции <tex> U_n </tex> является вычислимой функцией и все вычислимые функции одного аргумента встречаются среди <tex>U_n</tex> (отсюда универсальность). Универсальная функция нужна, например, для того, чтобы показать, что существует перечислимое неразрешимое множество (на самом деле это множество таких <tex> n </tex>, для которых <tex> U(n, n) </tex> определено).

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

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

===Вычислимость универсальной функции===
{{Теорема
|statement = Для класса вычислимых функций одного аргумента существует вычислимая универсальная функция.
|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>.
}}
{{Теорема
|statement = Для класса всюду определенных вычислимых функций одного аргумента не существует всюду определенной вычислимой универсальной функции.
|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> называется диагональной (отсюда и пошло название метода).

===Главная нумерация===
{{Определение
|definition='''Нумерация (numbering)''' множества <tex>X-</tex> это такое всюду определенное отображение <tex> f : \mathbb{N} \rightarrow X</tex>, область значений которого есть все множество <tex>X</tex>.
}}

{{Определение
|definition=Нумерация, заданная двуместной универсальной функцией <tex>U(n,x)</tex> называется '''главной (Гёделевой) (Godel numbering)''', если для любой двуместной вычислимой функции <tex>V(n,x)</tex> существует вычислимая, всюду определенная функция <tex>S:\mathbb{N}\rightarrow\mathbb{N}</tex> такая, что <tex>V(n,x)=U(S(n),x)</tex>.
}}
{{Теорема
|statement=Существует главная нумерация.
|proof=Рассмотрим универсальную функцию, построенную ранее, и нумерацию, соответствующую ей. Обозначим программу, вычисляющую функцию <tex>V(n,x)</tex> как <tex>v(n,x)</tex>. Построим программу (назовем ее <tex>s</tex>) с одним параметром - <tex>m</tex>, которая генерирует код программы <tex>v(n,x)</tex>, но с фиксированным <tex>n = m</tex>, и возвращает ее номер в заданной нумерации. Построенная программа вычисляет искомую функцию для универсальной двуместной функции <tex>U</tex> и двуместной функции <tex>V</tex>, то есть <tex>V(n,x)=U(S(n),x)</tex>, где <tex>S</tex> - функция, вычисляемая программой <tex>s</tex>. Из вычислимости <tex>v</tex> следует существование <tex>V</tex>, и за конечное время мы можем вернуть номер любой программы в выбранной нумерации. Таким образом <tex>S</tex> - вычислимая, всюду определенная.
}}

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

== Литература ==
[http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf ''Н. К. Верещагин, А. Шень.'' '''Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции.''' — М.: МЦНМО, 1999, с. 16]

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

[http://en.wikipedia.org/wiki/G%C3%B6del_numbering Godel numbering on Wiki]

[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]