5.4. Некоторые операции над машинами Тьюринга

Рассмотрим суперпозицию двух функций f₁(x) и f₂(у): g(x)=f₂(f₁(x)).

Для того, чтобы g(x) была определена при данном х надо, чтобы f₁ была определена на х и f₂ была определена на f₁(x).

Теорема: Если f₁(x) и f₂(у) вычислимы по Тьюрингу, то их су­перпозиция f₂(f₁(x)) так же вычислима по Тьюрингу.

Е сли Т₁ – машина, вычисляющая f₂, то машина Тьюринга, вы­числяющая f₂(f₁(x)) называется композицией машин Т₁ и Т₂ и обо­значается Т₂ (Т₁) и изображается блок-схемой:

Эта блок-схема предполагает, что исходными данными ма­шины Т₂ являются результаты Т₁. При этом они уже готовы к упот­реблению, т.к. благодаря правильной вычислимости заключительная конфигурация Т₁ легко превращается в стандартную начальную кон­фигурацию для Т₂.

Пример: Машина Т₊(Т_коп) вычисляет функцию f(x)=2x для x0. При этом машина Т_коп строит двухкомпонентный вектор, а Т₊ вы­числяет функцию от двух переменных.

Имеет место важный факт. Оказывается, что для вычисления на машине Тьюринга достаточно, чтобы лента была бесконечна только в одну сторону, например, вправо. Такая лента называется правой полулентой. Это следует из теоремы:

Теорема: Для любой машины Тьюринга Т существует эквива­лентная ей машина Т_R­ с правой полулентой.

Может быть предложено две идеи построения такой машины:

1) всякий раз, когда головке прежней машины надо зайти за левый край ленты, новая машина предварительно сдви­нет все написанное (вместе с головкой) на клетку вправо;

2) лента ‘‘перегибается‘‘ пополам. При этом ячейки правой половины размещаются, например, в нечетных ячейках, а ячейки левой половины – в четных.

Рассмотрим теперь вычисление предикатов на машинах Тью­ринга. Машина Т вычисляет предикат Р() (-слово в А_исх), если Т()=, где =И, когда Р() истинно и =Л, когда Р() ложно. Если же Р() не определено, то машина Т, как и при вы­числении функций, не останавливается. При обычном вычислении пре­диката уничтожается , что может оказаться неудобным, если после Т должна работать другая машина. Поэтому вводится понятие вы­числения с восстановлением: машина Т' вычисляет Р() с восста­новлением, если Т()=. Если имеется машина Т, вычисляющая Р(), то имеется и Т', вычисляющая Р() с восстановлением.

Возникает вопрос, для всех, ли процедур, претендующих на алгоритмичность, т. е. эффективных процедур, могут быть построены реализующие их машины Тьюринга? Ответ на этот вопрос со­держится в тезисе Тьюринга: ‘‘Всякий алгоритм может быть реали­зован машиной Тьюринга”. Это не теорема и не постулат, а утвер­ждение, связывающее теорию с теми объектами, для описания кото­рых она построена. По характеру тезис напоминает гипотезу физики об адекватности математических моделей физическим явлениям, которые они описывают.

5.5. Рекурсивные функции

Всякий алгоритм исходным данным, в случае, если он опре­делен на них, ставит в соответствие результат. Поэтому с каждым алгоритмом однозначно связана функция, которую он вычисляет. Верно ли обратное: для всякой функции имеется алгоритм, вычис­ляющий её? Оказывается, что нет. Тогда возникает вопрос; для ка­ких функций алгоритмы существуют?

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

Займемся теперь конкретным выбором средств, с помощью которых будут строиться вычислимые функции. Очевидно, к вычисли­мым функциям следует отнести все числа: 0,1,2…. Однако в прямом включении бесконечного множеств констант нет необходимости. Достаточно одной константы 0 и функции следования f(x)=x+1, ко­торую обозначают х, чтобы получить весь натуральный ряд. Кроме того, в базис включим семейство { } функций тождества (или введения фиктивных переменных):

(x₁,…,x_n)=x­_m (mn)

Мощным средством получения новых функций из уже имею­щихся является суперпозиция. Оператором суперпозиции (h,g₁,…,g_m) назы­вается подстановка в функцию от m переменных функции от n переменных.

Например, для функций h(x₁,…,x_m),g₁(x₁,…,x_n),…, g_m(x₁,…,x_n),

(h,g₁,…,g_m)=h(g₁(x₁,…,x_n),…, g_m(x₁,…,x_n)).

Это определение порождает семейство операторов суперпози­ции { }. Благодаря функциям тождества стандартизация суперпо­зиции не уменьшает ее возможностей: любую подстановку функций в функции можно выразить через и .

Пример 5:

f(x₁,x₂)=h(g₁(x₁,x₂), g₂(x₁)) в стандартном виде запишется так:

f(x₁,x₂)= (h(x₁,x₂), g₁(x₁,x₂), ( (x₁,x₂), g₂(x₁), g₃(x₁))),

где g₃(x₁)- любая функция.

Используя подстановку и функции тождества, можно пред­ставлять и отождествлять аргументы в функции:

f(x₂,x₁, x₃,…, x_n)=f( (x₁,x₂), (x₁,x₂), x_3­,…, x_n),

f(x₁,x₁, x₃,…, x_n)=f( (x₁,x₂), (x₁,x₂), x_3­,…, x_n).

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

Еще одно семейство операторов – это операторы примитив­ной рекурсии. Оператор примитивной рекурсии R_n определяет (n+1) – местную функцию f через n-местную функцию g и (n+2)-ме­стную функцию h следующим образом:

(5.2)

Пара уравнений (5.2) называется схемой примитивной рекур­сии. Тот факт, что f определена схемой (5.2), выражается равенством f(x₁,…,x_n)=R_n(g,h). В случае, когда h=0, т.е. определяемая функция f является одноместной, схема (5.2) принимает вид:

f(0)=с, 

 (5.3)

f(y+1)=h(y,f(y)), где с=const. 

Схемы (5.2) и (5.3) определяют f рекурсивно не только через другие функции g и h, но и через значения f в предшествующих точ­ках. Для вычисления f(x₁,…,x_n,k) понадобится (k+1) вычисление по схеме (5.2) для y=0,1,…,k.

Пример 6: Записать в стандартном виде n!.

Индуктивное определение примитивно-рекурсивной функции.

1. Функции 0, х и для всех натуральных m и n, где mn являются примитивно – рекурсивными.

2. Если g₁(x₁,…,x_n),…,g_m(x₁,…,x_n), h(x₁,…,x_m) – прими­тивно-рекурсивные, то (h,g₁,…,g_m) – примитивно-рекурсив­ная функция для всех m, n N.

3. Если g₁(x₁,…,x_n) и h(x₁,…,x_n,y,z) – примитивно-ре­курсивные, то R_n(g,h)- примитивно-рекурсивная функция.

4. Других примитивно-рекурсивных функций нет.

Пример 7:

1) Сложение f₊(x,y)=x+y примитивно-рекурсивно

f₊(x,0)=x=

f₊(x,y+1)= f₊(x,y)+1= (f₊(x,y)),

значит,

f₊(x,y)=R₁( ,h(x,y,z)), где h(x,y,z)=z=z+1.

2) Умножение f_(x,y)=xy примитивно-рекурсивно

f_(x,0)=0

f_(x,y+1)= f_(x,y)+х= (f_(x, f_(x,y))

3) Возведение в степень f_ехр(x,y)=x^у примитивно-рекурсивно

f_ехр(x,0)=1

f_ехр(x,y+1)= х x^у = (f_(x, f_ехр(x,y))

Пример 8: Вычитание.

Определим функцию х÷y (арифметическое или урезанное вычита­ние) так:

Примитивно-рекурсивными являются следующие функции:

1) f(x)= x÷1 Определяется схемой:

f(0)= 0÷1=1

f(y+1)= y.

2) f(x,y)=x÷y :

f(x,0)=x

f(x,y+1)= x÷(y+1)= (x÷y) ÷1=f(x,y) ÷1.

Для определения функции из пункта 2) используется функция из пункта 1).

3) f(x,y)=|x-y|=(x÷y)+(y÷x);

4)

sg(0)=0

sg(x+1)=1

5) min(x,y)=x(xy)

max(x,y)=y+(xy)

С помощью функции sg(x) и ее отрицания 1-sg(x) построим прими­тивно-рекурсивное описание функций, связанных с делением.

Пример 9: Деление

1. Функция r(x,y) – остаток от деления у на х:

r(x,0)=0

r(x,y+1)=(r(x,y,)+1)sg(|x-(r(x,y)+1)|)

Смысл: если у+1 не делится на х, то sg(|x-(r(x,y)+1)|)=1 и r(x,y+1)=r(x,y,)+1; если же у+1 делится на х, то r(x,y+1)=sg(|x-(r(x,y)+1)|)=0

2. Функция q(x,y)=[y/x] – целая часть дроби у/x:

q(x,0)=0

q(x,y+1)=q(x,y)+ (|x-(r(x,y)+1)|).

Если у+1 делится на х, то q(x,y+1) на единицу больше, чем q(x,y), если нет, то q(x,y+1)= q(x,y).

В рекурсивных описаниях функций из примера 9 отчетливо видны логические действия: проверка условия (делимость у+1 на х) и выбор дальнейшего хода вычислений в зависимости от истинности условия.

Из функций примеров 7 и 8 легко получается примитивная рекурсивность логических функций, т.е. числовых функций на мно­жестве {0;1}, которые ведут себя как логические.

Действительно:

(5.4)

Из полноты этого множества функций и того, что суперпози­ция является примитивно-рекурсивным оператором, следует прими­тивная рекурсивность всех логических функций.

Определение: Характеристической функцией предиката R(x₁, x₂,…, x_n) будем называть функцию:

Предикат называется примитивно-рекурсивным, если его ха­рактеристическая функция примитивно-рекурсивна. В силу соотно­шений (5.4), если предикаты Р₁,…,Р_к примитивно-рекурсивны, то и любой предикат, полученный из них с помощью логических опера­ций примитивно-рекурсивен.

Пример 10: Предикаты

1. Предикат ‘‘х делится на n” примитивно-ре­курсивен при любых n

2. Предикат ‘‘х делится на n и m” прими­тивно-рекурсивен:

3. Отношение x₁>x₂ – примитивно-рекурсивно:

.

Подведем некоторые итоги. Из простейших функций - кон­станты 0, функции х+1 и функций тождества с помощью опера­торов суперпозиции и примитивной рекурсии получено огромное разнообразие функций, включающих функции арифметики, алгебры, анализа, логики, и т.д. Тем самым выяснено, что эти функции имеют примитивно-рекурсивное описание, которое однозначно определяет процедуру их вычисления, а отсюда следует, что их естественно от­нести к классу вычислимых функций.