Доказательство. Область применимости — это a(H), а множество результатов — это z(H). Оба эти множества перечислимы по лемме 4. чтд

Следствие 2. Область определения и множество значений любой вычислимой функции перечислимы.

Доказательство. Частный случай Следствия 1. чтд

Следствие 3. График любой вычислимой функции перечислим.

Доказательство. По аксиоме протокола для функции существует множество протоколов H и вычислимые функции входа/выхода a(h) и z(h). Тогда следующий алгоритм перечисляет график функции: for hÎH do yield <a(h), z(h)> end for чтд

Следствие 4. Функция с перечислимым графиком вычислима.

Доказательство. По аксиоме протокола для функции существует множество протоколов H и вычислимые функции входа/выхода a(h) и z(h). Тогда следующий алгоритм перечисляет график функции: for hÎH do yield <a(h), z(h)> end for чтд

4.4 ¢ .5. Алгоритмы и программы

Алгоритмы могут быть записаны как слова в универсальном алфавите U, причем такая запись заведомо не является единственной. Возникает естественный вопрос: если даны две записи, причем обе синтаксически распознаются как записи алгоритмов, то что можно сказать о свойствах алгоритмов по их записям? Например, это две записи одного алгоритма или разных алгоритмов? Ясно, что ответить на эти вопросы не так просто. Необходимо внести уточнения в описание способа записи алгоритмов.

Введем обозначения. Напомним, что мы рассматриваем алгоритмы над словами в алфавите U, т.е. алгоритмы принимают в качестве аргументов слова (возможно, не принимают аргументов) и вырабатывают в качестве результата также слова (возможно много слов). Алгоритмы, в том числе вычислимые функции, не обязательно тотальны. Если аргументы принадлежат области определения алгоритма, то говорят, что алгоритм применим.

Говорят, что два алгоритма A и B условно равны для аргумента x, обозначение A (x)¡ B (x), если либо оба алгоритма применимы к аргументу x и тогда их результаты совпадают, либо оба алгоритма неприменимы к x.

Замечание. Алгоритмы в этом определении являются не только алгоритмами вычислимых функций, но любыми алгоритмами. Поэтому результатами работы может быть не только возвращаемое значение, но и перечислимое множество, или последовательность действий в случае итераторов, или изменение состояния объекта в случае трансформаций и т.д. Совпадение результатов для каждого типа алгоритмов определяется специфических образом. Для вычислимых функций это равенство слов, для перечислимых множеств — равенство множеств слов.

Два алгоритма A и B называются равносильными, если у них совпадают области применимости, и для любого слова из этой области, взятого в качестве аргумента, совпадают результаты работы алгоритмов, то есть " x (A (x) ¡ B (x)). Равносильность обычно обозначается следующим образом: A ~ B. Ясно, что равносильность алгоритмов является эквивалентностью.

Замечание. Все эти определения применимы к любым алгоритмам, в частности, к вычислимым функциям. Поэтому равносильность и функциональная эквивалентность — это равнообъемные понятия.

Говорят, что два алгоритма A и B всюду отличаются, если Ø$ x (A (x) ¡ B (x)). Другими словами, алгоритмы всюду отличаются, если дают разные результаты там, где применимы, и нет таких аргументов, при которых они оба неприменимы.

Пусть имеется алгоритм с двумя параметрами А: X ´ Y ® Z. Проекцией этого алгоритма на первый (второй) параметр, или остаточной программой по первому (второму) аргументу, называется алгоритм А _x: Y ® Z (А _y: X ® Z) такой, что " y Î Y (A _x (y) ¡ A (x, y)) (соответственно " x (A _y(x) ¡ A (x, y))).

Замечание. Термин остаточная программа заимствован из теории смешанных вычислений. Концепцию смешанных вычислений предложил А.П.Ершов[2].

Пусть есть некоторый класс алгоритмов A. Класс алгоритмов B называется представительным для класса A, если для любого алгоритма A ÎA существует равносильный алгоритм B ÎB, A ~ B.

Замечание. Отношение представительности между классами алгоритмов не является эквивалентностью, но является рефлексивным и транзитивным, то есть является отношением предпорядка.

Идея состоит в том, чтобы для любого класса алгоритмов A подобрать более четко очерченный (но, возможно, более широкий!) класс алгоритмов B, который будет представительным по отношению к исходному классу. Элементы класса B называются программами, которые представляют (или реализуют) элементы класса A.

Осталось определить, в каком смысле класс программ должен быть четко очерчен. Во-первых, класс программ должен быть разрешимым — требуется надежно отличать программы от не программ. Во-вторых, должен быть задан алгоритм интерпретации I, позволяющей по программе B и исходным данным x определить результаты представляемого алгоритма A (x) — программы необходимо уметь выполнять.

Замечание 1. Этой же схеме следуют все упоминавшиеся выше теоретические уточнения понятия алгоритма. Каждое такое уточнение описывает свой класс «программ» (более или менее формально), неформально описывает алгоритм I и в качестве недоказываемой догмы постулирует представительность выбранного класса программ.

Замечание 2. Но этой же схеме следуют все практические системы программирования! Каждая такая система описывает свой класс программ (задает синтаксис языка программирования), полуформально описывает алгоритм I (операционная семантика языка программирования), а «выразительная сила» языка программирования рассматривается как предмет веры. В том, что класс программ шире класса алгоритмов (если программа синтаксически правильна, это еще не значит, что она сработает и даст результат) программисты очень быстро убеждаются на собственном печальном опыте.

Все сказанное приводит к следующей аксиоме.

Аксиома [ программы ]. Существует представительное разрешимое множество программ B такое, что для любого алгоритма A: T ₁® T ₂ существует равносильная программа BÎ B, и существует алгоритм интерпретации I: B´ T ₁® T ₂, причем A ~ I_B.

Замечание. Алгоритм I, как и все алгоритмы, может быть запрограммирован, то есть для него может быть предъявлена равносильная программа. Полученная программа является самоприменимой. В этом нет ничего парадоксального.

4.4 ¢ .6. Невычислимые функции и неразрешимые множества

Рассмотрим более подробно важное понятие универсальной функции, или универсального алгоритма. Рассмотрим произвольный класс F вычислимых функций f: X ® Y. Функция U: F ´ X ® Y называется универсальной для класса F, если " f " x U (f, x) ¡ f (x). Другими словами, там, где исходная функция определена, универсальная функция вычисляет значение по функции и по аргументу, а там где функция не определена, универсальная функция также не определена.

Примеры. 1. Алгоритм 3.4. в п. 3.6.3 является универсальным алгоритмом в классе булевых функций n переменных.

2. Алгоритм 3.1. в п. 3.2.1 является универсальным алгоритмом в классе функций, заданных формулами в базисе F.

3. Интерпретатор I является универсальным алгоритмом в классе программ.

Множество программ, представляющих вычислимые функции перечислимо и их можно перенумеровать. Но тогда интуитивно ясно, что возможно построить программу (например, в форме «очень длинного» оператора switch), которая по номеру функции и значению аргумента будет вычислять значение этой функции. Таким образом, из аксиомы программы имеем

Следствие 1. Каков бы ни был класс вычислимых функций T ₁® T ₂ существует вычислимая функция U: N´ T ₁® T ₂, универсальная в этом классе.

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

Следствие 2. Существует вычислимая функция U: N´N®N, универсальная в классе вычислимых функций N®N.

Доказательство. Положим T ₁:= N и ® T ₂:= N и по следствию 1. чтд

Следствие 3. Существует такая вычислимая функция N®N, что никакая вычислимая функция не может отличаться от нее всюду.

Доказательство. Рассмотрим «диагональную» функцию d (n):= U (n, n). Пусть f_n — функция, имеющая номер n. Если f_n (n) определено, то f_n (n) = d (n) и f_n (n) ¡ d (n), если же f_n (n) не определено, то и d (n) не определено, и все равно f_n (n) ¡ d (n). чтд

Предыдущее доказательство кажется парадоксом: действительно, если у нас есть функция, которая претендует на то, что, неформально говоря, её график «пересекается» с графиками всех других функций, то, казалось бы, возьмем функцию, график которой «параллелен» графику «претендента», и получится контрпример к следствию 3. Но никакого парадокса и контрпримера нет! Дело в том, что мы рассматриваем все вычислимые функции, в том числе и частичные, и «пересечение» получается там, где функции не определены.

Но если вычислимая функция определена частично, то можно доопределить ее произвольным образом, назначив какие-то значения функции для тех значений аргументов, где функция не определена. Такое «доопределение» называется всюду определенным продолжением.

Следствие 4. Существует вычислимая функция N®N, не имеющая всюду определённого вычислимого продолжения.

Доказательство. Рассмотрим «параллельную» функцию d ₁(n):= d (n)+1. Эта функция определена частично, потому что функция d (n) определена частично. Рассмотрим тогда D ₁(n) — всюду определенное продолжение d ₁(n). Эта функция всюду определена и всюду отличается от d (n). По следствию 3 заключаем, что функция D ₁(n) невычислима. чтд

Таким образом, построена всюду определенная, но невычислимая функция.

Следствие 5. Существует неразрешимое перечислимое подмножество натурального ряда.

Доказательство. Достаточно рассмотреть N:=Dom d ₁(n). N перечислимо по лемме 5. Допустим, что N разрешимо алгоритмом N. Тогда построим функцию d ₂(x):= if N (x) then d ₁(x) else 1 end if. Функция d ₂(x) оказывается всюду определенным вычислимым продолжением функции d ₁(n), что невозможно в силу следствия 4, а значит алгоритма N не существует. чтд

Таким образом, построено перечислимое, но неразрешимое множество.

Следствие 6. Существует перечислимое подмножество натурального ряда с неперечислимым дополнением.