5. Определение оператора примитивной рекурсии, примеры применения

Говорят, что функция h получена из функций f и g при помощи оператора примитивной рекурсии R и пишут hR(f,g), если:

h(x₁,…,x_n1,0)f(x₁,…,x_n1),

h(x₁,…,x_n1,y1)g(x₁,…,x_n1,y,h(x₁,…,x_n1,y))

для всех x₁,…,x_n1,yN (n1). При n1 f является константой.

Когда определено значение функции h(x₁,…,x_n1,y)?

h(x₁,…,x_n1,y) определено и равно z_y, если

f(x₁,…,x_n1) определено и равно z₀,

g(x₁,…,x_n1,0,z₀)) определено и равно z₁,

g(x₁,…,x_n1,1,z₁)) определено и равно z₂,

……………………………………………….,

g(x₁,…,x_n1,y1,z_y1)) определено и равно z_y;

иначе h(x₁,…,x_n) не определено.

Заметим, что оператору примитивной рекурсии в программировании соответствует цикл типа for ("для").

6. Определение оператора минимизации, примеры применения

Пусть функция f(x₁,…,x_n1,y) удовлетворяет условию "либо значение f(x₁,…,x_n1,y) не определено для всех y, либо найдется число y₀, такое, что значение f(x₁,…,x_n1,y) определено для всех yy₀ и равно x_n для yy₀".

Запись yf(x₁,…,x_n1,y)x_n означает "наименьшее y, такое, что f(x₁,…,x_n1,y) определено и равно x_n".

Говорят, что функция g получена из функции f при помощи оператора минимизации M и пишут gM(f), если g(x₁,…,x_n)yf(x₁,…,x_n1,y)x_n для всех x₁,…,x_n,yN (n1).

Когда определено значение функции g(x₁,…,x_n)?

g(x₁,…,x_n) определено и равно y, если

f(x₁,…,x_n1,0) определено и не равно x_n,

f(x₁,…,x_n1,1) определено и не равно x_n,

…………………………… ….……………,

f(x₁,…,x_n1,y1) определено и не равно x_n,

f(x₁,…,x_n1,y) определено и равно x_n;

иначе g(x₁,…,x_n) не определено.

Если n1, f – биекция, то gf^1 является функцией, обратной к f.

Заметим, что оператору минимизации в программировании соответствует цикл while ("пока").

7. Построение одноместных рекурсивных функций

Приведем схему примитивной рекурсии для одноместной функции:

h(0)f₀const,

h(x1)g(x,h(x)).

При помощи этой схемы доказываем, что функции – сигнум sg и антисигнум являются ПРФ. Например, сигнум sg – ПРФ:

sg(0)0,

sg(x1)1soI₁²(x,sg(x)).

8. Построение двухместных рекурсивных функций

Приведем схему примитивной рекурсии для двухместной функции:

h(x,0)f(x),

h(x,y1)g(x,y,h(x,y)).

При помощи этой схемы доказываем, что сложение xy, умножение xy и возведение в степень x^y – ПРФ. Например, функция f_(x,y)xy – ПРФ:

f_(x,0)xI₁¹(x),

f_(x,y1)sI₃³(x,y,f_(x,y)).

9. Машины Тьюринга. Команды в виде четверок и в виде пятерок

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

Устройство машины Тьюринга:

1) лента, разделенная на ячейки и бесконечная в обе стороны;

2) «вычислитель», который обозревает некоторую ячейку, считывает символ с ячейки, стирает этот символ и вписывает новый символ в ячейку, затем перемещается на одну ячейку влево или вправо;

3) конечный список внутренних состояний с начальным состоянием и заключительным состоянием ;

4) конечный список внешних символов – символов ячеек и символа , обозначающего пустую ячейку;

5) программа – список команд вида , или , причем, каждой паре соответствует не более одной пары , или (где , , , а – дополнительные символы, обозначающие перемещение вычислителя на одну ячейку влево или вправо).

В любой момент времени заполнено конечное число ячеек ленты.

Пусть s₁ – крайний левый и s₂ – крайний правый символ на ленте. Тогда последовательность символов ленты s₁...s₂ называется машинным.

Программа машины Тьюринга – это список команд, т.е. четверок вида q_ia_ja_kq_l, q_ia_jLq_l или q_ia_jRq_l, где i,j,k,lN, i0, причем, каждой паре q_ia_j соответствует не более одной пары a_kq_l, Lq_l или Rq_l.

Конфигурация машины Тьюринга – это слово машины Тьюринга, дополненное в любом месте одним из символов q_i, причем, слева и справа может быть дописано любое число символов пустой клетки a₀. Смысл конфигурации s₁...q_is_j...s₂ в том, что в данный момент времени машина находиться в состоянии q_i и обозревает клетку с символом s_j. При этом машина выполняет команду, начинающуюся с пары q_is_j, и переходит к следующей конфигурации, согласно следующим правилам:

конфигурация до выполнения команды	команда	конфигурация до выполнения команды
s1...qiaj...s2	qiajakql	s1...qlak...s2
s1...sxqiaj...s2	qiajLql	s1...qlsxaj...s2
qis1...s2, s1aj	qiajLql	qla0s1...s2
s1...qiajsx...s2	qiajRql	s1...ajqlsx...s2
s1...qis2, s2aj	qiajRql	s1...s2qla0