Изменения

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

|definition = Функция Две '''вычислимые функции''' (англ. ''computable function'') <tex>U : N \times N \rightarrow N \cup \lbrace \bot \rbracef_1</tex> называется '''универсальной (universal function)''' для класса [[Вычислимые функции|вычислимых функций]] одного аргумента, если и <tex>\forall n \in Nf_2</tex> равны при заданных аргументах, если при этих аргументах вычисляющие программы для этих функций зависают, либо равны значения, возвращаемые ими:*<tex>U_nf_1(x) = Uf_2(n, x)</tex> является вычислимой функцией и для любой вычислимой функции *<tex>ff_1(x) = \bot</tex> и <tex>\exists n \in N : ff_2(x) = U(n, x)\bot</tex>

{{Определение|definition = Функция <tex>U : \mathbb{N}\ \times \mathbb{N}\ \rightarrow \mathbb{N}\ \cup \lbrace \bot \rbrace</tex> называется '''универсальной '''(англ. ''universal function'') для класса [[Вычислимые функции|вычислимых функций]] одного аргумента, если <tex>\forall n \in \mathbb{N}\</tex> <tex>U_n(x) = U(n, x)</tex> («сечение» функции <tex>U</tex> при фиксированном <tex>n</tex>) является вычислимой функцией и для любой вычислимой функции <tex>f</tex> <tex>\exists n \in \mathbb{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> {{--- }} вычислима, значит <tex>U(n,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 \mathbb{N }\ : f(x) = p_n(x) = U(n, x)</tex>. <tex>\forall n \in \mathbb{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)</tex> — всюду определенная вычислимая универсальная функция для класса всюду определенных вычислимых функций одного аргумента. Воспользуемся теперь диагональным методом. Рассмотрим всюду определенную вычислимую функцию одного аргумента <tex>d(x) = U(x, x) + 1</tex>. <tex>\exists n \in \mathbb{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>. Противоречие.

===Перечислимое неразрешимое множество==={{Теорема|statement=Существует перечислимое неразрешимое множество|proof=Возьмем вычислимую функцию <tex>f(x)</tex> не имеющую всюду определенного вычислимого продолжения. Тогда область определения <tex>F</tex> этой функции будет искомым множеством. Действительно, <tex>F</tex> [[Перечислимые языки|перечислимо]]. Предположим, что <tex>F</tex> разрешимо. Но тогда функция <tex>g(x)</tex> равная <tex>f(x)</tex> при <tex> x \in F </tex> и равная <tex>0</tex> если <tex> x \notin F </tex> является вычислимым всюду определенным продолжением функции <tex>f</tex>. Пришли к противоречию, значит <tex>F</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>.

|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=Пусть <tex>U-</tex> универсальная функция, соответствующая главной нумерации. Множество тех <tex>n</tex>, при которых функция <tex>U_n</tex> является нигде не определённой, неразрешимо.|proof=Покажем, что если бы это множество было разрешимо, то любое перечислимое множество было бы разрешимо (что не так).Пусть <tex>W-</tex> произвольное перечислимое неразрешимое множество. Введем функцию <tex>V</tex> от двух аргументов такую, что <tex>V(n,x) = 0</tex> если <tex> n \in W </tex>, и неопределенную в противном случае.Эта функция имеет сечения двух типов: сечение есть нулевая функция, либо нигде не определенная функция.Поскольку <tex> U </tex> соответствует главной нумерации, то существует вычислимая всюду определённая функция <tex>s</tex> такая, что<tex>V (n, x) = U(s(n), x)</tex> для любых <tex>n</tex> и <tex>x</tex>, то есть <tex>V_n = U_{s(n)}</tex>. Тогда при <tex> n \in W </tex> значение <tex>S_n</tex> есть <tex>U</tex>-номер нулевой функции, иначе <tex>U</tex>-номер нигде не определенной функции. Поэтому если бы множество <tex>U</tex>-номеров нигде не определённой функции разрешалось бы некоторым алгоритмом, то применяя этот алгоритм к <tex>s(n)</tex> мы могли бы узнать принадлежность <tex>n</tex> к множеству <tex>W</tex>. То есть множество <tex>W</tex> было бы разрешимым в противоречии с нашим предположением.}}Также мы можем заключить, что нигде не определённая функция имеет бесконечно много номеров в любой главной нумерации (множество номеров нигде не определённой функции неразрешимо, а любое конечное множество разрешимо). А также отметим, что множество номеров нигде неопределённой функции не только не разрешимо, но и не перечислимо. Его дополнение <tex>-</tex> множество всех номеров всехфункций с непустой областью определения — перечислимо (При вычислении <tex>U(n,x)</tex> для всех <tex>n, x</tex> мы можем печатать те <tex>n</tex>, для которых нашло <tex>x</tex> такое, что <tex>U(n,x)</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 Wikipedia {{---}} Godel numbering on Wiki]