Лемма (о декартовом произведении)., Замечания и упражнения - Рекурсивные функции

Если А - эффективное множество, то

Для любого эффективного множества B AB эффективно (и, следовательно, любое декартово произведение A1A2...Аn эффективных множествэффективно);

Множество A*, A*=N N AN, всех конечных последовательностей элементов А эффективно счетно.

Если B - эффективно счетно, то утверждение тривиально следует из показанного в лекции 1 факта эффективной счетности NN. Если же B - конечно, то пусть f1:NA - эффективное кодирование, а f2 - 1-1 конечное отображение N в B, B={f(1),...,f(k)}. Тогда

F(n)= < f1(n div k), f2(n mod k) >

Где n div k, n mod k - соответственно, целая часть и остаток от деления n на k, -1-1 отображение N на AB.

По основной теореме арифметики, для любого числа n, n N, существует единственное разложение на произведение степеней простых чисел :

N=p(1)n(1)* p(2)n(2)*... *p(k)n(k)=i=1,k p(i)n(i)

(где p(i) - i-ое простое число), что и дает требуемое 1-1 отображение N на N*:n<n(1),n(2),...,n(k)> и, следовательно, на A*.

Замечания и упражнения

Закончите доказательство, построив FD-программы вычисления функций n div k, n mod k и разложения числа на простые множители и показав, тем самым, эффективность выбранных кодировок.

Взятое нами из процедурного программирования понятие (конструктивного) типа данных (в терминологии объектного программирования - классов, в терминологии универсальной алгебры - алгебраических систем) подразумевает рассмотрениенекоторого множества А значений данных Совместно со средствами их обработки, т. е. наличия некоторых Вычислимых функций на А. Если f: AN эффективное кодирование и g:AA, то g естественно считать вычислимой тогда и только тогда, когда вычислима соответствующая функция на кодах - образ g при отображении f, т. е.функция f(x)fg(x).

Покажите, что для любого эффективного счетного множества A

Операция конкатенации ( соединения, приписывания ) последовательностей вычислима;

Операции

Элемент_n-ки(<a(1),a(2),...,a(n)>,i)=a(i), i N,

Элемент_последовательности(<a(1),a(2),...,a(n)>,i)=a(i), i N,

Взятия проекции AN, для любого n N, и A* на заданную координату вычислима.

С) Заметим, что операции взятия проекции можно трактовать как операции "выборки компоненты по индексу", что открывает нам путь к неявному употреблению Статических и Динамических массивов в языке FD-программ. Действительно, можно завести обычную (числовую) переменную - скажем, с именем ArrayCode, полагая, что она содержит код некоторой конечной числовой последовательности Array и моделируя нужные операции над элементами массива функциями над их кодами. Скажем, присваивание ArrayCode:= ArrayCode*pI ,будет моделировать присваивание Array[i]:=S(Array[i]). Таким образом, мы можем без опасения расширить синтаксис FD-программ введением индексных переменных, полагая операторы работы с массивами просто иной формой записи операторов работы с их кодами.

Приступим теперь к построению нумерации программ. FD-программы, по определению, есть конечные последовательности пар вида <k: op> k, k N - числовая метка, а op - оператор. Мы уже научились строить кодирования конечных последовательностей и пар, для этого достаточно построить эффективное кодирование всех возможных операторов.

Каждый оператор однозначно характеризуется следующей парой - Тип (название) оператора (stop, if-then-else, приваивания) и Список параметров оператора <y1, y2,..., yM>, среди которых - метки операторов, переменные, функциональные и логические выражения. Оператор start стоит всегда в начале FD-программы и может быть задан только списком своих параметров. Типам других операторов нетрудно сопоставить числовые коды - скажем, перенумеровать в приведенном выше порядке. Остается закодировать числами каждое из возможных значений параметров оператора.

Метки операторов не нуждаются в особом кодировании - это уже натуральные числа. Без ограничения общности, можно полагать, что каждая из переменных имеет вид xI, iN-поставим каждой из переменных xI в соответствие ее номерi. Наконец, перенумеруем все функциональные и предикатные символы (скажем, ноль-функцию 0 - нулем, функцию следования S - единицей и предикат равенства - двойкой) и закодируем функциональные и логические выражения, имеющие вид f(x1, x2,..., xN) кодом пары <i, j>, где i - номер функционального или предикатного символа f, j - код n-ки < j1, j2,..., jN >, j1, j2,..., jN - коды имен переменных x1, x2,..., xN.

(конец доказательства)

Замечание. Внимательный к деталям читатель, вероятно, заметил, что для того, чтобы не перегружать изложение деталями, мы немного упростили синтаксис FD - программ, разрешая переход на несуществующие метки - что, с точки зрения семантики, естественно трактовать как "ошибку программы", т. е. неопределенность значения вычисляемой функции.

Подчеркнем снова, что для построенного кодирования существует не только алгоритм нахождения номера программы по ее тексту, но и обратный алгоритм, восстанавливающий полный синтаксис каждой программы по ее номеру. В теории алгоритмов такие нумерации программ называют геделевыми (в честь знаменитого немецкого логика Курта Геделя, впервые, с целью вложения логики в арифметику, применившим такие нумерации для кодирования логических формул). В качественной теории алгоритмов нас интересует лишь наличие либо отсутствие, но не конкретный вид алгоритмов, поэтому мы далее мы можем допускать вольность, отождествляя программы и их геделевы номера и говоря, например, о программе i вместо - программа с геделевым номером i. Особо отметим, что, в любом случае, наши результаты не будут зависеть от выбора конкретной геделевой нумерации.

Поскольку каждая программа вычисляет некоторую функцию, введенная нумерация программ порождает некоторую нумерацию функций. Через Pk обозначим программу с кодом k, а через K - (одноместную) функцию, вычисляемую программойPk (для n-местных функций будем употреблять обозначение K(n) ). Очевидно,

1, 2, 3,....

Некоторая нумерация (перечисление) Всех вычислимых функций, которую мы также назовем Геделевой.

Правда, в отличие от нумерации программ, у нас нет никаких оснований считать эту нумерацию эффективным кодированием. Заметим пока, что, как минимум, это нумерацияне взаимно-однозначна. Действительно, мы кодировали синтаксис программ, и любые синтаксически различные программы имеют разные коды. С другой стороны, каждая вычислимая функция вычисляется бесконечным классом программ. Скажем, если P - одна такая программа, то программа, полученная дописыванием к ней "фиктивного" оператора x:=x, вычисляет ту же функцию.

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

Пусть А - счетный класс одноместных (не обязательно - всюду определенных) функций,

A={f1, f2,..., fI,...}

Даже если Каждая из функций fI вычислима (некоторым алгоритмом PI), это не гарантирует существование Единого алгоритма вычисления Всех функций. Назовем класс A Равномерно перечислимым, Если это действительно так, т. е. существует двуместная вычислимая функция F, что класс А состоит в точности из функций вида F(n, x), для некоторых n из N; функцию F назовем универсальной Функцией класса A. Ясно (пусть пока, быть может, лишь на интуитивном уровне), что nF(n, x) - эффективная нумерация класса А, которую мы также назовем равномерной.

Наша ближайшая цель - показать, что

Определенная нами геделева нумерация вычислимых функций равномерна (теорема об универсальной функции),

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

Более точные (и программистские по духу) формулировки и пояснения следует далее. По сложившейся традиции, начнем с обсуждения второго результата.

Похожие статьи




Лемма (о декартовом произведении)., Замечания и упражнения - Рекурсивные функции

Предыдущая | Следующая