Главные нумерации — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 4: Строка 4:
 
|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) - универсальная функция.
 
|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) - универсальная функция.
 
}}
 
}}
Рассмотрим двуместную универсальную функцию <tex>U(n,x)</tex>. Будем говорить, что она задает нумерацию для класса одноместных функций следующим образом: <tex>f_n(x)=U(n,x)</tex>.
+
Рассмотрим двуместную универсальную функцию <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>.
 
|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>.

Версия 20:40, 9 декабря 2010

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

Теорема:
Существует универсальная функция
Доказательство:
[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]U(n,x)[/math]. Будем говорить, что она задает нумерацию для класса одноместных вычислимых функций следующим образом: [math]f_n(x)=U(n,x)[/math].

Определение:
Нумерация, заданная двуместной универсальной функцией [math]U(n,x)[/math] называется главной (Гёделевой), если для любой двуместной вычислимой функции [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]