Суперпозиции, примитивной рекурсии и наименьшего корня.
Оператор суперпозиции: Позволяет из функции f (у1, …, уm) и функций
h1(x1,...,xn), h2(x1,...,xn), ... ,hm(x1,...,xn) сконструировать функцию
f(h1(x1,...,xn), ... , hm(x1,...,xn)).
Например, с помощью оператора суперпозиции можно получить любую константу
S(S( …(Z(x)) …)) = n, где число вложенных функций следования равно n.
Или сдвига числа на константу n, также равную числу вложенных функций следования.
S(S( …(S(x)) …)) = x + n,
Оператор примитивной рекурсии. Этот оператор позволяет получит
n + 1-местную функцию из n-местной и n + 2 - местной функций.
Оператор задается двумя равенствами:
f(x1,...,xn, 0) = g(x1,...,xn)
f(x1,...,xn, y) = h(x1,...,xn, y-1, f(x1,...,xn, y-1))
Позволяет по n+1-местной функции получить n-местную.
Частный случай - функция одного аргумента:
f(0) = const
f(y) = h(y - 1, f(y - 1))
Функции, которые могут быть построены из примитивных с помощью операторов суперпозиции и
примитивной рекурсии называются примитивно-рекурсивными.
Пример: функция суммирования.
fS(x, 0) = g(x) = I(x) = x
fS(x, 1) = h(x, 0, fS(x, 0)) = h(x, 0, x) = h`(I3(3)((x, 0, x)) = S(x) = x + 1
fS(x, 2) = h(x, 1, fS(x,1)) = h(x, 1, x+1) = S(x + 1) = x + 2
. . .
fS(x, y) = h(x, 1, fS(x, y - 1)) = S(fS (x, y - 1)) = x + y
то есть в традиционной записи определение сложения, как примитивно-рекурсивной функции, будет:
x + y = x + (y - 1) + 1
Функция умножения.
fp(x, 0) = y(x) = z(0) = 0
fp(x, 1) = h(x, 0, fp(x, 0)) = h(x, 0, 0) = h`(I1,3(3)((x, 0, 0)) = fS(x, 0) = x
fp(x,2) = h`(x, fp(x, 1)) = fS(x, x) = 2x
fp(x,y) = fS(x, fp(x, y - 1))
то есть в традиционной записи определение умножения, как примитивно-рекурсивной функции, будет
x*y = x*(y - 1) + x
M-оператор.
my[g(x1, ... , xn, y) = 0]
где y - выделенная переменная.
Работу m-оператора можно описать следующим образом.
Выделяется переменная (здесь – у). Затем фиксируется значение остальных переменных (x1, ... , xn).
Значение y последовательно увеличивается, начиная с нуля. Значением m-оператора будет значение y, при
котором функция впервые обратилась в ноль. Значение m-оператора считается неопределенным, если
функция вообще не принимает значения ноль, либо она принимает отрицательое значение до того как
примет значение ноль.
Пример.
Пусть функция g(х, y) = х – у + 3. Зафиксируем х = 1
my[g(1, y) = 0] = 4
так как 1 – 4 + 3 = 0.
Класс (множество, которое может быть получено из примитивных функций с помощью операторов
суперпозиции, примитивной. рекурсии и m-оператора, называется. множеством частично-рекурсивных
функций.Множество частично-рекурсивных функций совпадает с множеством вычислимых
функций - алгоритмически разрешимых задач.
Машины Тьюринга.
Известны случаи построения школьниками железных машин Тьюринга с колесами.
Но машина Тьюринга – это все-таки прежде всего метод математического моделирования.
Машина Тьюринга включает:
1. Потенциально бесконечную (вправо) ленту, разделенную на ячейки.
2. Считывающе-записывающую головку с устройством управления (УУ).
3. Алфавит внутренних состояний {q0, q1...qn}.
4. Входной-выходной алфавит.
Определяется начальная конфигурация. Головка смотрит на какую-то ячейку и устройство управления
находится в начальном состоянии q1.
Устройство управления на основании считанного из ячейки символа и внутреннего состояния пишет в
ячейку символ (возможно, тот же самый), совершает действие D и переходит в новое внутреннее
состояние(возможно прежнее). Это и есть команда Машины Тьюринга, которую можно записать так:
aiqi ® ajDjqj.
D = {Л, П, С} - множество действий.
Л – влево, П – вправо, С - стоять.
Совокупность команд составляет программу машины Тьюринга, которая обычно оформляется в виде
таблицы. Машина заканчивает работу, когда переходит в состояние q0.
l - пустой символ.
Пример: Построим машину Т, которая в сплошной последовательности 1 стирает первую и две последние.
(l - пустой символ).
| q1 | q2 | q3 | q4 | |
| lПq2 | 1Пq2 | lЛq4 | lСq0 | |
| l | - | lЛq3 | - | - |