63
правки
Изменения
Новая страница: «В этом разделе равенство двух вычислимых функций при заданных аргументах понимается в то…»
В этом разделе равенство двух вычислимых функций при заданных аргументах понимается в том смысле, что при этих аргументах вычисляющие программы для этих функций зависают, либо равны значения, возвращаемые ими.
{{Теорема
|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> - является вычислимой функцией. Вычисляющая программа содержит интерпретатор для зафиксированного языка программирования, по номеру программы (первый аргумент) восстанавливает ее код, и передает ей второй аргумент, возвращая результат ее работы. Значит U(n,x) - универсальная функция.
}}
Рассмотрим двуместную универсальную функцию <tex>U(n,x)</tex>. Будем говорить, что она задает нумерацию для класса одноместных функций следующим образом: <tex>f_n(x)=U(n,x)</tex>.
{{Определение
|definition=Нумерация, заданная двуместной универсальной функцией <tex>U(n,x)</tex> называется главной (Гёделевой), если для любой двуместной вычислимой функции <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> - вычислимая, всюду определенная.
}}
{{Теорема
|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> - является вычислимой функцией. Вычисляющая программа содержит интерпретатор для зафиксированного языка программирования, по номеру программы (первый аргумент) восстанавливает ее код, и передает ей второй аргумент, возвращая результат ее работы. Значит U(n,x) - универсальная функция.
}}
Рассмотрим двуместную универсальную функцию <tex>U(n,x)</tex>. Будем говорить, что она задает нумерацию для класса одноместных функций следующим образом: <tex>f_n(x)=U(n,x)</tex>.
{{Определение
|definition=Нумерация, заданная двуместной универсальной функцией <tex>U(n,x)</tex> называется главной (Гёделевой), если для любой двуместной вычислимой функции <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> - вычислимая, всюду определенная.
}}
