- •ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ АЛГОРИТМОВ
- •ПРИМИТИВНО-РЕКУРСИВНЫЕ ФУНКЦИИ
- •Оператор примитивной рекурсии
- •Оператор минимизации
- •МАШИНА ТЬЮРИНГА
- •Композиция МТ
- •Геделева нумерация МТ
- •НОРМАЛЬНЫЕ АЛГОРИТМЫ МАРКОВА
- •ПРИМЕР ВЫПОЛНЕНИЯ ИНДИВИДУАЛЬНОГО ЗАДАНИЯ
- •ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ ПО ТЕОРИИ АЛГОРИТМОВ
- •СПИСОК ЛИТЕРАТУРЫ
Рекурсивные (рекуррентные) функции – это такие функции, значения которых можно вычислить для n + 1, если умеешь вычислить для n, т. е. каждое последующее значение вычисляется, если известны предыдущие.
Пример – числа Фибоначчи – последовательность чисел f(n), удовлетворяющая условиям:
f(0) = 1; f(1) = 1; f(n + 2) = f(n) + f(n + 1), т. е. 1, 1, 2, 3, 5, 8, 13, 21, . . .
ПРИМИТИВНО-РЕКУРСИВНЫЕ ФУНКЦИИ
Сначала введем три простейшие рекурсивные функции, которые по определению считаются примитивно-рекурсивными (ПРФ).
1.O(x) = 0 – нуль – функция, оператор аннулирования.
2.S(x) = x + 1 – функция Пеано, оператор сдвига.
3.Im(x1, . . . xn) = xm; xi N; m = 1, . . ., n – функция-проектор, оператор проектирования. В частности, I1(x) = x – функция-проектор.
Очевидно, что эти три функции всюду определены (на N) и вычислимы. Теперь введем два оператора, которые позволят нам получать более
сложные вычислимые функции.
Оператор суперпозиции (получение сложной функции, или «функции от функции»).
Пусть даны функции h1(x1, . . . xn); h2(x1, . . . xn), . . . hm(x1, . . . xn) и
функция g(x1, . . . xm). Тогда применение оператора суперпозиции дает новую функцию:
f(x1, . . . xn) = g(h1(x1 . . . xn); h2(x1 . . . xn); . . . hm(x1 . . . xn) ), т. е. мы в функцию g вместо xi подставили hi( x1 . . . xn ). Смысл оператора: если
можно у вычислимой функции g вычислить аргументы по формулам (hi), то и саму функцию g также можно вычислить.
Например, с помощью этого оператора можно получить из простейших рекурсивных функций следующие функции:
f(x) = 1 = S(O(x)) = S(0)
f(x) = 2 = S(S(O(x))) = S(S(0)) = S(1)
f(x) = x + 3 = S(S(S(x))) = S(S(x + 1)) = S(x + 2)
f(x1, x2 … xn) = xi + a = S(S(S…S(Ii(x1, … xn)))…) f(x1, x2 … xn) = a = S(S(… S(O(x1, x2 … xn)) …)
Оператор примитивной рекурсии
Говорят, что (n + 1)-местная функция f(x1, … xn, y) (т. е. функция (n + 1) аргументов) получена из n-местной функции g(x1, … xn) и (n + 2)-местной
5
функции h(x1 … xn, y, z) с помощью оператора примитивной рекурсии, если значения f(x1 … xn, y) можно вычислить по так называемой схеме примитивной рекурсии:
f(x1 … xn, 0) = g(x1 … xn)
f(x1, … xn, y+1 ) = h(x1 …xn, y, f(x1 …xn, y))
Вэтом случае говорят: «рекурсия проводится по y». Заметим, что
всписке аргументов функции f рекурсия обычно проводится по последнему аргументу.
При n = 0 функция одной переменной f(x) получается примитивной рекурсией из g = const = a и функции двух переменных h(x, y) следующим образом:
f(0) = a
f(x + 1) = h(x, f(x))
Например, найти f(x) по схеме примитивной рекурсии
g(x) = 1
h(x,y) = (x + 1)2y
Тогда f(0) = 1
f(x + 1) = (x + 1)2f(x)
f(1) = f(0 + 1) = (0 + 1)2f(0) = 1 f(2) = f(1 + 1) = (1 + 1)2f(1) = 4
f(3) = f(2 + 1) = (2 + 1)2f(2) = 36
. . . . . . . . . . . . . . . . .
f(x) = h(x – 1,f(x – 1)) = x2f(x – 1) = x2(x – 1)2f(x – 2) = = x2(x – 1)2(x – 2)2 … 1 = (x!)2
При n = 1 функция f(x,y) получается примитивной рекурсией из g(x) и h(x, y, z) следующим образом:
f(x, 0) = g(x)
f(x, y + 1) = h(x, y, f(x, y)
Например, найти f(x, y) по схеме примитивной рекурсии, если g(x) = x; h(x, y, z) = x(y + 1)z:
f(x, 0) = x
f(x, y + 1) = h(x, y, f(x, y)) = x(y + 1)f(x, y) f(x, 1) = x(0 + 1)x = x2
f(x, 2) = x(1 + 1)x2 = 2!x3 f(x, 3) = x(2 + 1)2x3 = 3! x4
. . . . . . . . . . . .
Очевидно, что искомая функция f(x, y) = y!xy+1.
6
Определение. Функция f(x1 … xn) называется примитивно-рекурсивной (ПРФ), если она может быть получена с помощью конечного числа операторов суперпозиции и примитивной рекурсии, примененных к простейшим функциям O(x), S(x), Im (x1 … xn).
Замечание 1. Очевидно, что для получения ПРФ функции, участвующие в схеме ПРФ g и h, должны быть тоже ПРФ.
Замечание 2. Очевидно, что ПРФ от n переменных определена на пространстве Nn.
Замечание 3. Если операторы суперпозиции и примитивной рекурсии применены к ПРФ, то в результате тоже получается ПРФ, т. е. не обязательно при доказательстве того, что функция – ПРФ, доходить до простейших функций.
Замечание 4. Если f(x1, x2) – ПРФ, то f(x2, x1) – тоже ПРФ, так как получена из f(x1, x2) оператором суперпозиции.
Докажем, например, что следующие функции – ПРФ. 1. f(x, y) = x + y. Введем g(x) = x – ПРФ, так как x = I(x)
f(x, y + 1) = x + y + 1 = (x + y) + 1 = f(x, y) + 1
Введем h(x, y, z) = z + 1 – ПРФ, так как z + 1 = S(z).
Тогда f(x, y) = x + y получается по схеме примитивной рекурсии по y:
f(x, 0) = g(x) = x
f(x, y + 1) = h(x, y, f(x, y)) = f(x, y) + 1
Следовательно, f(x, y) = x + y – ПРФ.
Отсюда можно сделать вывод: сумма двух ПРФ есть также ПРФ.
2. f(x, y) = xy Введем g(x) = 0 – ПРФ
f(x, y + 1) = x(y + 1) = xy + x = f(x, y) + x
Введем h(x, y, z) = z + x – ПРФ
Тогда f(x, y) = xy получается по схеме примитивной рекурсии:
f(x, 0) = g(x) = 0
f(x, y + 1) = h(x, y, f(x, y)) = f(x, y) + x
Следовательно, f(x,y) = xy – ПРФ.
Отсюда можно сделать вывод: произведение ПРФ есть также ПРФ. 3. f(x) = 5x – ПРФ, так как она есть произведение 5 и x – двух ПРФ.
4. f x x о 1 = x 1, если x 1, |
x N : 0, 1, 2, ... |
|
0, |
если x 0 |
7
Эта функция получается по схеме примитивной рекурсии:
f(0) = g = 0 – ПРФ
f(x + 1) = (x + 1) o 1 = (x o 1) + 1 = f(x) + 1 = h(x, f(x)), где h(x, y) = y + 1 = S(y) – ПРФ.
5. f(x, y) = x o y = x y, если x y,
0, если x y.
Схема примитивной рекурсии для этой функции:
f(x, 0) = g(x) = x = I(x) – ПРФ
f(x, y + 1) = x o (y + 1) = (x o y) o 1 = f(x ,y) o 1 = h(x, y, f(x, y)), где h(x, y, z) = z o 1 – ПРФ.
Итак, f(x, y) = x o y – ПРФ, так как она получена оператором примитивной рекурсии из функций g(x) = x и h(x, y, z) = z o 1.
Примитивно-рекурсивные функции определены для всех значений аргументов из Nn.
Иногда это является недостатком в том смысле, что вычислимая функция не есть ПРФ из-за того, что определена не для всех значений аргументов. Напомним, что и аргументы вычислимой функции, и сама функция могут принимать только положительные целочисленные значения. Например, естественно считать вычислимой (т. е. существует алгоритм для ее вычисления) функцию f(x, y) = x – y, при x ≥ y и неопределенную при x < y.
Однако, эта функция не ПРФ, поэтому требуется ввести еще один оператор.
Оператор минимизации
Пусть имеется функция g(x1 … xn, y ) и пусть x1, x2 … xn – фиксированы, тогда возможны 4 случая.
1.При любых y g(x1 … xn, y) ≠ 0. В этом случае будем считать, что оператор минимизации µy(g) = f(x1 … xn) не определен в точке (x1, x2 … xn).
2.g(x1, … xn, 0) = 0. Тогда µy(g) = f(x1 … xn) = 0.
3.Пусть y – наименьший корень уравнения g(x1, x2, … xn, y) = 0, при-
чем все значения g(x1 … xn, y – 1), g(x1 … xn, y* – 2), . . . g(x1 … xn, 0) ≠ 0 и
определены.
Тогда µy(g) = f(x1 … xn) = y.
4. Среди g(x1 … xn,. y* – 1), . . g(x1 … xn, 0) есть хотя бы одно неопределенное значение.
Тогда µy(g) = f(x1 … xn) не определен.
8
Итак, можно сформулировать следующее.
Определение. Оператор минимизации µy(g) – функция n переменных f(x1, … xn), значение которой равно наименьшему корню y уравнения g(x1, … xn, y) = 0 при условии, что определены значения g(x1 … xn, y* – 1), g(x1 … xn, y* – 2), . . . g(x1 … xn, 0).
Для вычисления функции µy(g(x1 … xn, y) = 0) = f(x1 … xn) можно предложить следующий алгоритм:
1) вычисляем g(x1 … xn, 1); если равно 0, то f(x1 … xn) = µy(g)= 0; если же ≠ 0, переходим к следующему шагу;
2) вычисляем g(x1 … xn, 1), если равно 0, то µy(g) = 1, если же ≠ 0, переходим к следующему шагу и так далее.
Если для всех y g(x1 … xn, y) ≠ 0 или на каком-то шаге значение g(x1 … xn, y) не определено, то µy(g) считаем неопределенным.
Определение. Функция называется частично-рекурсивной, если она может быть получена с помощью применения конечного числа раз трех операторов (суперпозиции, примитивной рекурсии и минимизации)
кпростейшим примитивно-рекурсивным функциям (O(x), S(x), Im(x1 … xm)).
Вкачестве примера докажем, что функция f(x, y) = x – y, при x ≥ y и
неопределенная при x < y есть частично-рекурсивная функция. Напомним, что функция x o y = x – y при x ≥ y и равная 0 при x < y
является ПРФ, а также сумма двух ПРФ есть также ПРФ.
Рассмотрим функцию h(x, y) = |x – y| = (x o y) + (y o x). Эта функция есть ПРФ как сумма двух ПРФ. Введем теперь функцию g(x, y, z) = |x – (z + y)|. Очевидно, что она ПРФ. Тогда
f(x, y) = x – y = µz(g) = x – y при x ≥ y и не определена при x < y. Действительно, уравнение g(x, y, z) = 0 это уравнение |x – y – z| = 0.
Если x ≥ y, то корень z = x – y – наименьший корень этого уравнения, так как
g(x, y, z* – 1) = |x – y – (x – y – 1)| = 1 ≠ 0 g(x, y, z* – 2) = |x – y – (x – y – 2)| = 2 ≠ 0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
g(x, y, 0) = |x – y – 0| = |x – y| ≠ 0, если z ≠ 0
Если x = |
y , то корень z = 0, если же x < y, то ни при каком |
||||
z N 0, 1, 2, ... |
|
x y z |
|
0, т. е. оператор |
µz(g) не определен. |
|
|
Таким образом мы доказали, что f(x, y) получена оператором минимизации из ПРФ, и поэтому является частично-рекурсивной функцией.
9