Универсальная функция
Содержание
Определение универсальной функции
В этом разделе равенство двух вычислимых функций при заданных аргументах понимается в том смысле, что при этих аргументах вычисляющие программы для этих функций зависают, либо равны значения, возвращаемые ими.
| Определение: |
| Функция называется универсальной (universal function) для класса вычислимых функций одного аргумента, если является вычислимой функцией и для любой вычислимой функции |
Менее формально, для универсальной функции должно выполняться следующее: "сечение" функции является вычислимой функцией и все вычислимые функции одного аргумента встречаются среди (отсюда универсальность). Универсальная функция нужна, например, для того, чтобы показать, что существует перечислимое неразрешимое множество (на самом деле это множество таких , для которых определено).
Аналогично определяется универсальная функция для класса всюду определенных вычислимых функций одного аргумента.
Существование универсальной функции
| Теорема: |
Существует универсальная функция для класса вычислимых функций одного аргумента |
| Доказательство: |
| Зафиксируем какой-либо язык программирования. Пусть программами на этом языке являются слова над алфавитом . Программа будет иметь номер , если ее код - -е слово среди всех слов над алфавитом , отсортированных сначала по возрастанию длины, а при равной длине - в лексикографическом порядке. При этом если -я программа не компилируется, будем считать, что она всегда зависает. Рассмотрим функцию такую, что , где - -я программа. Заметим, что по определению вычислимой функции существует программа, вычисляющая ее. Но в заданной нумерации у любой программы есть номер. Таким образом для любой вычислимой функции существует номер . И наоборот - - является вычислимой функцией. Вычисляющая программа для содержит интерпретатор для зафиксированного языка программирования, по номеру программы (первый аргумент) восстанавливает ее код, и передает ей второй аргумент, возвращая результат ее работы. Таким образом - вычислима для любого , и , - вычислима, значит U(n,x) - универсальная функция. |
Вычислимость универсальной функции
| Теорема: |
Для класса вычислимых функций одного аргумента существует вычислимая универсальная функция. |
| Доказательство: |
| Занумеруем программы нашего языка натуральными числами. Рассмотрим функцию , где — -ая программа в указанной нумерации. Для любой вычислимой функции . , очевидно, является вычислимой функцией. Значит — универсальная функция для класса вычислимых функций одного аргумента. Очевидно, что вычислима. Действительно, для того, чтобы вычислить , достаточно вернуть вывод программы на входе . |
| Теорема: |
Для класса всюду определенных вычислимых функций одного аргумента не существует всюду определенной вычислимой универсальной функции. |
| Доказательство: |
| От противного. Пусть — всюду определенная вычислимая универсальная функция для класса всюду определенных вычислимых функций одного аргумента. Воспользуемся теперь диагональным методом. Рассмотрим всюду определенную вычислимую функцию одного аргумента . в силу того, что — универсальная для соответствующего класса функций. Так как всюду определена, то она не зависает на аргументе . Значит , но в то же время . Противоречие. |
Отметим, что функция называется диагональной (отсюда и пошло название метода).
Перечислимое неразрешимое множество
| Теорема: |
Существует перечислимое неразрешимое множество |
| Доказательство: |
| Возьмем вычислимую функцию не имеющую всюду определенного вычислимого продолжения. Тогда область определения этой функции будет искомым множеством. Действительно, перечислимо. Предположим, что разрешимо. Но тогда функция равная при и равная если является вычислимым всюду определенным продолжением функции . Пришли к противоречию, значит неразрешимо. |
Главная нумерация
| Определение: |
| Нумерация (numbering) множества это такое всюду определенное отображение , область значений которого есть все множество . |
| Определение: |
| Нумерация, заданная двуместной универсальной функцией называется главной (Гёделевой) (Godel numbering), если для любой двуместной вычислимой функции существует вычислимая, всюду определенная функция такая, что . |
| Теорема: |
Существует главная нумерация. |
| Доказательство: |
| Рассмотрим универсальную функцию, построенную ранее, и нумерацию, соответствующую ей. Обозначим программу, вычисляющую функцию как . Построим программу (назовем ее ) с одним параметром - , которая генерирует код программы , но с фиксированным , и возвращает ее номер в заданной нумерации. Построенная программа вычисляет искомую функцию для универсальной двуместной функции и двуместной функции , то есть , где - функция, вычисляемая программой . Из вычислимости следует существование , и за конечное время мы можем вернуть номер любой программы в выбранной нумерации. Таким образом - вычислимая, всюду определенная. |
С помощью главной нумерации можно пронумеровать все программы. Также, используя главную нумерацию не сложно определить номер программы, являющуюся композицией двух программ (то есть состоящей из двух подпрограмм и основной функции, возвращающей результат композиции исходных программ). Пусть нам необходимо по номерам функций и определить номер функции-композиции и
| Теорема: |
Существует такая функция , которая всюду определена и которая по номерам функций и дает номер их композиций. То есть выполняется свойство |
| Доказательство: |
| Для начала зафиксируем вычислимую нумерацию пар (взаимно однозначное соответствие между и ; число назовем номером этой пары. Возьмем некоторую функцию . Исходя из определения главной нумерации существует такая вычислимая, всюду определенная функция для всех и . А тогда , что значит функция с, определяемая как , будет искомой. |
Собственно, то, что с помощью главной нумерации мы можем легко получать номер композиции двух программ и является преимуществом главной нумерации относительно других.
Литература
В. А. Успенский Лекции о вычислимых функциях — М.: ГИФМЛ, 1960, с. 203
