Суперпозиции, примитивной рекурсии и наименьшего корня.

Оператор суперпозиции: Позволяет из функции f (у₁, …, у_m) и функций

h₁(x₁,...,x_n), h₂(x₁,...,x_n),...,h_m(x₁,...,x_n) сконструировать функцию

f(h₁(x₁,...,x_n),..., h_m(x₁,...,x_n)).

Например, с помощью оператора суперпозиции можно получить любую константу

S(S(…(Z(x)) …)) = n, где число вложенных функций следования равно n.

Или сдвига числа на константу n, также равную числу вложенных функций следования.

S(S(…(S(x)) …)) = x + n,

Оператор примитивной рекурсии. Этот оператор позволяет получит

n + 1-местную функцию из n-местной и n + 2 - местной функций.

Оператор задается двумя равенствами:

f(x₁,...,x_n, 0) = g(x₁,...,x_n)

f(x₁,...,x_n, y) = h(x₁,...,x_n, y-1, f(x₁,...,x_n, y-1))

Позволяет по n+1-местной функции получить n-местную.

Частный случай - функция одного аргумента:

f(0) = const

f(y) = h(y - 1, f(y - 1))

Функции, которые могут быть построены из примитивных с помощью операторов суперпозиции и

примитивной рекурсии называются примитивно-рекурсивными.

Пример: функция суммирования.

f_S(x, 0) = g(x) = I(x) = x

f_S(x, 1) = h(x, 0, f_S(x, 0)) = h(x, 0, x) = h ^` (I₃⁽³⁾((x, 0, x)) = S(x) = x + 1

f_S(x, 2) = h(x, 1, f_S(x,1)) = h(x, 1, x+1) = S(x + 1) = x + 2

...

f_S(x, y) = h(x, 1, f_S(x, y - 1)) = S(f_S (x, y - 1)) = x + y

то есть в традиционной записи определение сложения, как примитивно-рекурсивной функции, будет:

x + y = x + (y - 1) + 1

Функция умножения.

f_p(x, 0) = y(x) = z(0) = 0

f_p(x, 1) = h(x, 0, f_p(x, 0)) = h(x, 0, 0) = h ^` (I_1,3⁽³⁾((x, 0, 0)) = f_S(x, 0) = x

f_p(x,2) = h ^` (x, f_p(x, 1)) = f_S(x, x) = 2x

f_p(x,y) = f_S(x, f_p(x, y - 1))

то есть в традиционной записи определение умножения, как примитивно-рекурсивной функции, будет

x*y = x*(y - 1) + x

M-оператор.

my[g(x₁,..., x_n, y) = 0]

где y - выделенная переменная.

Работу m-оператора можно описать следующим образом.

Выделяется переменная (здесь – у). Затем фиксируется значение остальных переменных (x₁,..., x_n).

Значение y последовательно увеличивается, начиная с нуля. Значением m-оператора будет значение y, при

котором функция впервые обратилась в ноль. Значение m-оператора считается неопределенным, если

функция вообще не принимает значения ноль, либо она принимает отрицательое значение до того как

примет значение ноль.

Пример.

Пусть функция g(х, y) = х – у + 3. Зафиксируем х = 1

my[g(1, y) = 0] = 4

так как 1 – 4 + 3 = 0.

Класс (множество, которое может быть получено из примитивных функций с помощью операторов

суперпозиции, примитивной. рекурсии и m-оператора, называется. множеством частично-рекурсивных

функций. Множество частично-рекурсивных функций совпадает с множеством вычислимых

функций - алгоритмически разрешимых задач.

 

Машины Тьюринга.

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

Но машина Тьюринга – это все-таки прежде всего метод математического моделирования.

Машина Тьюринга включает:

1. Потенциально бесконечную (вправо) ленту, разделенную на ячейки.

2. Считывающе-записывающую головку с устройством управления (УУ).

3. Алфавит внутренних состояний {q_0, q₁...q_n}.

4. Входной-выходной алфавит.

 

Определяется начальная конфигурация. Головка смотрит на какую-то ячейку и устройство управления

находится в начальном состоянии q₁.

Устройство управления на основании считанного из ячейки символа и внутреннего состояния пишет в

ячейку символ (возможно, тот же самый), совершает действие D и переходит в новое внутреннее

состояние(возможно прежнее). Это и есть команда Машины Тьюринга, которую можно записать так:

a_iq_i ® a_jD_jq_j.

D = {Л, П, С} - множество действий.

Л – влево, П – вправо, С - стоять.

Совокупность команд составляет программу машины Тьюринга, которая обычно оформляется в виде

таблицы. Машина заканчивает работу, когда переходит в состояние q_0.

l - пустой символ.

Пример: Построим машину Т, которая в сплошной последовательности 1 стирает первую и две последние.

(l - пустой символ).

 

	q1	q2	q3	q4
	lПq2	1Пq2	lЛq4	lСq0
l	-	lЛq3	-	-