сергиевская

Простейшие примитивно-рекурсивные функции задаются следующим образом.

вектору сопоставляет его i -ю координату.

Из простейших примитивно-рекурсивных функций можно получить примитивно-рекурсивные функции с помощью следующих двух операторов.

•Оператор суперпозиции. Пусть f n (x1, x2 ,..., xn ) , g1m (t1,t2 ,...,tm ) , g2m (t1,t2 ,...,tm ) , …, gnm (t1,t2 ,...,tm ) – примитивно-рекурсивные функции. Тогда функция

Fnm (g1m , g2m ,..., gnm ) =

= f n (g1m (t1,t2 ,...,tm ), g2m (t1,t2 ,...,tm ),..., gnm (t1,t2 ,...,tm ))

получена с помощью оператора суперпозиции.

Оператор суперпозиции – это оператор построения сложной функции. Если

• Оператор примитивной рекурсии из известных примитивно-рекурсивных

f n+1 (x1, x2 ,..., xn ,0) = ϕn (x1, x2 ,..., xn ) , f n+1 (x1, x2 ,..., xn , y +1) =

=ψ n+2 (x1, x2 ,..., xn , y, f n+1 (x1, x2 ,..., xn , y)) .

46

Решение. Найдем значения функции f (x, y) . f (x,0) = ϕ(x) = x ,

f (x,1) =ψ(x,0, f (x,0)) =ψ(x,0, x) = x x = x2 ; f (x,2) =ψ(x,1, f (x,1)) =ψ(x,0, x2 ) = x x2 = x3 ;

f (x,3) =ψ(x,2, f (x,2)) =ψ(x,0, x3 ) = x x3 = x4 .

Можно предположить, что f (x, y) = x y+1 .

Докажем последнюю формулу методом математической индукции по переменной y .

1. Проверим формулу при y = 0 .

f (x,0) = x = x0+1 , то есть при y = 0 формула верна.

2.Допустим, что предположение индукции верно при y = n , то есть, верна формула f (x, n) = xn+1 .

47

Докажем, что предположение индукции верно при y = n +1, то есть, верна формула f (x, n +1) = xn+2 . Выразим f (x, n +1) с помощью схемы примитивной

рекурсии.

f (x, n +1) =ψ(x, n, f (x, n)) =ψ(x,n, xn+1 ) = x xn+1 = xn+2 .

Таким образом, на основании метода математической индукции формула доказана для всех y N0 .

Теперь строго определим примитивно-рекурсивные функции.

Определение. 1) Простейшие примитивно-рекурсивные функции примитивно-рекурсивны.

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

3)Функция является примитивно-рекурсивной тогда и только тогда, когда это следует из 1) и 2).

Пример. Покажем, что функция f+ (x, y) = x + y примитивно-рекурсивна. Доказательство. n +1 = 2 , n =1, следовательно, функция ϕ должна зависеть

от одной переменной, а функция ψ – от трех. Пользуясь заданием функции, найдем ее значения:

f+ (x,0) = x = I11 (x) =ϕ(x) .

f+ (x, y +1) = x + y +1 = f+ (x, y) +1 = s1 (f+ (x, y))= =ψ(x, y, f+ (x, y)),

то есть ψ(x, y, z)= s(z) = s(I33 (x, y, z)).

Таким образом, функция f+ (x, y) = x + y получена по схеме примитивной рекурсии ( f+ = R1 (ϕ,ψ )) из примитивно-рекурсивных функций, следовательно, сама является примитивно-рекурсивной.

48

Это уравнение решается подбором, вместо переменной y последовательно подставляются 0,1,2,… При этом возможны случаи.

•На некотором шаге левая часть соотношения (1) не определена. Следовательно, на наборе (x1, x2 ,..., xi ,..., xn ) операция минимизации не определена.

•На каждом шаге левая часть соотношения (1) определена, но равенство не

значением операции минимизации на наборе (x1, x2 ,..., xn ) .

Пример. [13]. Найти функции, получаемые из данной числовой функции

f (x1, x2 , x3 ) =1 − x1 с помощью оператора минимизации по каждой ее переменной. x2

не определена.

49

1. Определить функцию f (x, y) , полученную из функций ϕ(x) и ψ(x, y, z) по схеме примитивной рекурсии.

1)ϕ(x) = x , ψ(x, y, z) = z .

2)ϕ(x) = x , ψ(x, y, z) = x + z .

3)ϕ(x) = x , ψ(x, y, z) = x + y − z .

4)ϕ(x) = x , ψ(x, y, z) = z2 .

5)ϕ(x) =1, ψ(x, y, z) = xz .

6)ϕ(x) =1, ψ(x, y, z) = xy .

7)ϕ(x) = 0 , ψ(x, y, z) = x2 + z .

8)ϕ(x) =1, ψ(x, y, z) = xz .

9)ϕ(x) = 0 , ψ(x, y, z) = z − x .

10)ϕ(x) = 0 , ψ(x, y, z) = x + y .

2.Доказать, что следующие функции примитивно-рекурсивны.

1)f (x) = a .

2)f (x) = x + a .

0, если x = 0, 3) sgn(x) = 1, если x > 0.

4)f (x, y) = xy .

5)f (x, y) = x!.

1, если x = 0, 6) sgn(x) = 0, если x > 0.

7)f (x, y) = x y .

3.Записать схему примитивной рекурсии для произвольных примитивнорекурсивных функций при

1)n =1;

2)n = 2 ;

3)n = 3.

4.Найти функции, получаемые из данной числовой функции f (x1, x2 , x3 ) с

помощью оператора минимизации по каждой ее переменной.

1)f (x1, x2 , x3 ) = x12 − x2 .

2)f (x1, x2 , x3 ) = 2x1 (x2 +1).

3)f (x1, x2 , x3 ) = x1 − x2 .

4)f (x1, x2 , x3 ) = x1x22 +1.

5)f (x1, x2 , x3 ) = x13 + x2 .

51

6)f (x1, x2 , x3 ) = x13 +3x2 .

7)f (x1, x2 , x3 ) = 2x1 + x2 .

8)f (x1, x2 , x3 ) = 2(x2 − x1 ) .

9)f (x1, x2 , x3 ) = x1x2 .

10)f (x1, x2 , x3 ) = x1 (x2 −1)2 .

ВОтветы и указания.

ВСодержание.

Глава 9. Машины Тьюринга.

Машина Тьюринга – это модель алгоритма, которая иллюстрирует процессы, происходящие при реализации алгоритма. Машина Тьюринга является гипотетической машиной. Ее составляют следующие компоненты.

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

Состояния обозначаются буквами так называемого внутреннего алфавита

Q={q0 , q1,K, qm }. Состояние q1 , как правило, считают начальным состоянием,

асостояние q0 – конечным (заключительным). Во внутренний алфавит включают также символы сдвига : R – вправо, L – влево, E – на месте.

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

каждой ячейке может быть записан один и только один символ некоторого

внешнего алфавита A ={a0 , a1,K,an }. Символ a0 принято считать пустым символом. Он обозначает пустую ячейку. По умолчанию, во всех ячейках, в

которых не записаны символы a1 , a2 ,…, an , записан символ a0 . В данной главе в качестве внешнего алфавита мы будем рассматривать алфавит E ={0,1}, 0 соответствует пустому символу.

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

52

… a0 a1 a2 … an …

↑

q1

Рис. 1

Так, на рис. 1 считывающая головка обозревает ячейку ленты, в которой записан символ an . Управляющее устройство находится в состоянии q1

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

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

qi a j qij aij Dij .

Здесь:

•qi – состояние, в котором управляющее устройство находится в данный момент,

•a j - символ, обозреваемый головкой,

•qij – состояние, в которое управляющее устройство переходит в зависимости от

состояния qi и обозреваемого символа a j ,

• aij – новый символ, который записывается в ячейку, и зависящий от qi и a j ,

• Dij – символ сдвига, указывающий направление движения головки (он также зависит от qi и a j ).

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

Вид ленты в каждый момент времени может быть определен конфигурацией

вида:

a j1 Ka jl−1 qi a jl Ka js .

Головкой в данный момент обозревается символ a jl , записанный в

конфигурации первым справа от символа qi . Первый и последний символы в данной

конфигурации – непустые. Считается, что остальные символы на ленте, не записанные в конфигурацию – пустые. Имеется в виду, что в данный момент времени на ленте записано слово a j1 Ka jl−1 a jl Ka js .

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

53

прекратить работу и в случае, когда в программе отсутствует команда для некоторого состояния и некоторого символа.

Если машина Тьюринга T , начав работу на некотором слове P , останавливается через некоторое число шагов, то считается, что она применима к слову P . Результатом применения машины к слову является слово T (P) , которое

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

Пример. Пусть машина Тьюринга задана программой:

T: q1 0q01E .

q11q11R

Рассмотрим записанные в последовательных n ячейках n единиц. Пусть, например, начальная конфигурация имеет вид: q1111K11.

Сокращенно эту конфигурацию можно записать так: q11n .

Вообще, записанные подряд n единиц обозначаются 1n , а записанные подряд m нулей – 0m .

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

Предполагается, что в начальный момент времени головка машины обозревает

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

54

Поскольку команда вида q2 0qiαD в программе отсутствует, то последняя

конфигурация является заключительной. Следовательно, машина T к слову P применима, и T (P) =1. (Нули слева и справа от слова не записываются).

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

Машины Тьюринга T1 и T2 называются эквивалентными, если:

• T1 и T2 либо обе применимы, либо обе неприменимы к каждому исходному слову

P;

•если обе машины применимы к слову P , то T1 (P) = T2 (P) .

Программу для машины Тьюринга можно задать не только с помощью последовательности команд, но и в виде таблицы. Так, в последнем примере программа может быть задана в виде:

При табличной записи командой иногда называют выражение qij aij Dij . Имеет место следующий тезис.

Тезис Тьюринга. Всякий алгоритм может быть реализован соответствующей машиной Тьюринга.

Тезис является недоказуемым, так как он связывает нестрогое понятие алгоритма и строгое понятие машины Тьюринга.

Тезис может быть опровергнут построением примера алгоритма, который не может быть реализован машиной Тьюринга.

В Содержание.

55