Универсальная функция — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Главная нумерация)
м (rollbackEdits.php mass rollback)
 
(не показано 27 промежуточных версий 4 участников)
Строка 1: Строка 1:
===Определение универсальной функции===
+
==Определение универсальной функции==
В этом разделе равенство двух вычислимых функций при заданных аргументах понимается в том смысле, что при этих аргументах вычисляющие программы для этих функций зависают, либо равны значения, возвращаемые ими.
 
 
{{Определение
 
{{Определение
|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>
+
|definition =  
 +
Две '''вычислимые функции''' (англ. ''computable function'') <tex>f_1</tex> и <tex>f_2</tex> равны при заданных аргументах, если при этих аргументах вычисляющие программы для этих функций зависают, либо равны значения, возвращаемые ими:
 +
*<tex>f_1(x) = f_2(x)</tex>
 +
*<tex>f_1(x) = \bot</tex> и <tex> f_2(x) = \bot</tex>
 
}}
 
}}
Менее формально, для универсальной функции должно выполняться следующее: "сечение" функции <tex> U_n </tex> является вычислимой функцией и все вычислимые функции одного аргумента встречаются среди <tex>U_n</tex> (отсюда универсальность). Универсальная функция нужна, например, для того, чтобы показать, что существует перечислимое неразрешимое множество (на самом деле это множество таких <tex> n </tex>, для которых <tex> U(n, n) </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=Существует универсальная функция для класса вычислимых функций одного аргумента
+
|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) - универсальная функция.
+
|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> {{---}} универсальная функция.
 
}}
 
}}
  
===Вычислимость универсальной функции===
+
==Вычислимость универсальной функции==
 
{{Теорема
 
{{Теорема
 
|statement = Для класса вычислимых функций одного аргумента существует вычислимая универсальная функция.
 
|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>.
+
|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>.
 
}}
 
}}
 
{{Теорема
 
{{Теорема
 
|statement = Для класса всюду определенных вычислимых функций одного аргумента не существует всюду определенной вычислимой универсальной функции.
 
|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>. Противоречие.
+
|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>. Противоречие.
 
}}
 
}}
 
Отметим, что функция <tex>u(n) = U(n, n)</tex> называется диагональной (отсюда и пошло название метода).
 
Отметим, что функция <tex>u(n) = U(n, n)</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= '''Нумерация''' (англ. ''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>.
+
|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=Существует главная нумерация.
 
|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> - вычислимая, всюду определенная.
+
|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> {{---}} вычислимая, всюду определенная.
 
}}
 
}}
  
Строка 53: Строка 52:
 
Собственно, то, что с помощью главной нумерации мы можем легко получать номер композиции двух программ и является преимуществом главной нумерации относительно других.
 
Собственно, то, что с помощью главной нумерации мы можем легко получать номер композиции двух программ и является преимуществом главной нумерации относительно других.
  
Приведем пример вычислимой нумерации множества <tex>R</tex>. Для этого упорядочим все дроби, образующие все множество <tex>R</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]
+
не определённая функция имела единственный номер. Пусть <tex>U(n,x)</tex>- произвольная вычислимая универсальная функция.
 +
Теперь возьмем перечислимое множество <tex>D</tex> всех  <tex>U</tex>-номеров всех функций таких, что их область определения непуста. Пусть функция <tex>d</tex> есть всюду определенная функция перечисляющая множество <tex>D</tex>. Рассмотрим функцию <tex>V(i, x)</tex>, для которой <tex>V(0, x)</tex> не определено ни при каком <tex>x</tex>, а <tex>V(i+1, x) = U(d(i), x)</tex>. То есть, функция <tex>V_0</tex> нигде не определена, а функция <tex>V_{i+1}</tex> совпадает с <tex>U_{d(i)}</tex>. Очевидно, функция <tex>V</tex> вычислима и универсальна (по построению), а единственным <tex>V</tex>-номером нигде не определённой функции является число <tex>0</tex>. Тогда нумерация, соответствующая этой функции является неглавной.
 +
== См. также ==
 +
* [[Неотделимые множества]]
 +
* [[Свойства перечислимых языков. Теорема Успенского-Райса]]
 +
* [[Теорема о рекурсии]]
 +
== Источники информации ==
 +
* [http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf ''Н. К. Верещагин,  А. Шень.'' '''Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции.''' — М.: МЦНМО, 1999, с. 16. ISBN 5-900916-36-7 ]
  
''В. А. Успенский'' '''Лекции о вычислимых функциях''' — М.: ГИФМЛ, 1960, с. 203
+
* ''В. А. Успенский'' '''Лекции о вычислимых функциях''' — М.: ГИФМЛ, 1960, с. 203
  
[http://en.wikipedia.org/wiki/G%C3%B6del_numbering Godel numbering on Wiki]
+
* [http://en.wikipedia.org/wiki/G%C3%B6del_numbering Wikipedia {{---}} Godel numbering ]
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория вычислимости]]
 
[[Категория: Теория вычислимости]]
 +
[[Категория: Разрешимые и перечислимые языки]]

Текущая версия на 19:38, 4 сентября 2022

Определение универсальной функции

Определение:
Две вычислимые функции (англ. computable function) [math]f_1[/math] и [math]f_2[/math] равны при заданных аргументах, если при этих аргументах вычисляющие программы для этих функций зависают, либо равны значения, возвращаемые ими:
  • [math]f_1(x) = f_2(x)[/math]
  • [math]f_1(x) = \bot[/math] и [math] f_2(x) = \bot[/math]


Определение:
Функция [math]U : \mathbb{N}\ \times \mathbb{N}\ \rightarrow \mathbb{N}\ \cup \lbrace \bot \rbrace[/math] называется универсальной (англ. universal function) для класса вычислимых функций одного аргумента, если [math]\forall n \in \mathbb{N}\[/math] [math]U_n(x) = U(n, x)[/math] («сечение» функции [math]U[/math] при фиксированном [math]n[/math]) является вычислимой функцией и для любой вычислимой функции [math]f[/math] [math]\exists n \in \mathbb{N}\ : f(x) = U(n, x)[/math].

Менее формально, для универсальной функции должно выполняться следующее: «сечение» функции [math] U_n [/math] является вычислимой функцией и все вычислимые функции одного аргумента встречаются среди [math]U_n[/math] (отсюда универсальность). Универсальная функция нужна, например, для того, чтобы показать, что существует перечислимое неразрешимое множество (на самом деле это множество таких [math] n [/math], для которых [math] U(n, n) [/math] определено).

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

Универсальную функцию удобно представлять как интерпретатор, которому на вход подают функцию и её аргумент, а он исполняет функцию на данном аргументе и возвращает результат.

Существование универсальной функции

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

Вычислимость универсальной функции

Теорема:
Для класса вычислимых функций одного аргумента существует вычислимая универсальная функция.
Доказательство:
[math]\triangleright[/math]
Занумеруем программы нашего языка натуральными числами. Рассмотрим функцию [math]U(n, x) = p_n(x)[/math], где [math]p_n[/math][math]n[/math]-ая программа в указанной нумерации. Для любой вычислимой функции [math]f[/math] [math]\exists n \in \mathbb{N}\ : f(x) = p_n(x) = U(n, x)[/math]. [math]\forall n \in \mathbb{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 \mathbb{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] называется диагональной (отсюда и пошло название метода).

Главная нумерация

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


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

С помощью главной нумерации можно пронумеровать все программы. Также, используя главную нумерацию не сложно определить номер программы, являющуюся композицией двух программ (то есть состоящей из двух подпрограмм и основной функции, возвращающей результат композиции исходных программ). Пусть нам необходимо по номерам функций [math]p[/math] и [math]q[/math] определить номер функции-композиции [math]p[/math] и [math]q[/math]

Теорема:
Существует такая функция [math]c[/math], которая всюду определена и которая по номерам функций [math]p[/math] и [math]q[/math] дает номер [math]c(p, q)[/math] их композиций. То есть выполняется свойство [math]U(c(p,q),x) = U(p, U(q,x))[/math]
Доказательство:
[math]\triangleright[/math]
Для начала зафиксируем вычислимую нумерацию пар (взаимно однозначное соответствие [math]\langle u, v \rangle \leftrightarrow [u, v][/math] между [math] N \times N [/math] и [math]N[/math]; число [math][u, v][/math] назовем номером этой пары. Возьмем некоторую функцию [math]V([p,q],x)=U(p, U(q,x))[/math]. Исходя из определения главной нумерации существует такая вычислимая, всюду определенная функция [math]S: V(n,x)=U(s(n),x)[/math] для всех [math]n[/math] и [math]x[/math]. А тогда [math]V([p,q],x)=U(S[p,q], x)[/math], что значит функция с, определяемая как [math]c(p,q)=S([p,q])[/math], будет искомой.
[math]\triangleleft[/math]

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

Пример неглавной вычислимой нумерации

Теорема:
Пусть [math]U-[/math] универсальная функция, соответствующая главной нумерации. Множество тех [math]n[/math], при которых функция [math]U_n[/math] является нигде не определённой, неразрешимо.
Доказательство:
[math]\triangleright[/math]

Покажем, что если бы это множество было разрешимо, то любое перечислимое множество было бы разрешимо (что не так). Пусть [math]W-[/math] произвольное перечислимое неразрешимое множество. Введем функцию [math]V[/math] от двух аргументов такую, что [math]V(n,x) = 0[/math] если [math] n \in W [/math], и неопределенную в противном случае. Эта функция имеет сечения двух типов: сечение есть нулевая функция, либо нигде не определенная функция. Поскольку [math] U [/math] соответствует главной нумерации, то существует вычислимая всюду определённая функция [math]s[/math] такая, что [math]V (n, x) = U(s(n), x)[/math] для любых [math]n[/math] и [math]x[/math], то есть [math]V_n = U_{s(n)}[/math].

Тогда при [math] n \in W [/math] значение [math]S_n[/math] есть [math]U[/math]-номер нулевой функции, иначе [math]U[/math]-номер нигде не определенной функции. Поэтому если бы множество [math]U[/math]-номеров нигде не определённой функции разрешалось бы некоторым алгоритмом, то применяя этот алгоритм к [math]s(n)[/math] мы могли бы узнать принадлежность [math]n[/math] к множеству [math]W[/math]. То есть множество [math]W[/math] было бы разрешимым в противоречии с нашим предположением.
[math]\triangleleft[/math]

Также мы можем заключить, что нигде не определённая функция имеет бесконечно много номеров в любой главной нумерации (множество номеров нигде не определённой функции неразрешимо, а любое конечное множество разрешимо). А также отметим, что множество номеров нигде не определённой функции не только не разрешимо, но и не перечислимо. Его дополнение [math]-[/math] множество всех номеров всех функций с непустой областью определения — перечислимо (При вычислении [math]U(n,x)[/math] для всех [math]n, x[/math] мы можем печатать те [math]n[/math], для которых нашло [math]x[/math] такое, что [math]U(n,x)[/math] определено). А если дополнение неразрешимого множества перечислимо, то само множество неперечислимо.

Теперь приведем пример вычислимой нумерации, не являющейся главной. Для этого достаточно сделать так, чтобы нигде не определённая функция имела единственный номер. Пусть [math]U(n,x)[/math]- произвольная вычислимая универсальная функция. Теперь возьмем перечислимое множество [math]D[/math] всех [math]U[/math]-номеров всех функций таких, что их область определения непуста. Пусть функция [math]d[/math] есть всюду определенная функция перечисляющая множество [math]D[/math]. Рассмотрим функцию [math]V(i, x)[/math], для которой [math]V(0, x)[/math] не определено ни при каком [math]x[/math], а [math]V(i+1, x) = U(d(i), x)[/math]. То есть, функция [math]V_0[/math] нигде не определена, а функция [math]V_{i+1}[/math] совпадает с [math]U_{d(i)}[/math]. Очевидно, функция [math]V[/math] вычислима и универсальна (по построению), а единственным [math]V[/math]-номером нигде не определённой функции является число [math]0[/math]. Тогда нумерация, соответствующая этой функции является неглавной.

См. также

Источники информации

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