5.2.3. Композиция машин Тьюринга

Для графического изображения основных операций алгоритма приняты обозначения блоков, показанные на рис. 5.15

Последовательное и/или параллельное соединение различных блоков позволяет организовать вычисление любых частично-рекурсивных функций. Общую схему соединения нескольких блоков от “начало” до “конец” называют блок-схемой алгоритма.

Оператор суперпозиции. Если даны m-местная функция h=(z₁, z₂,...z_m, у) и m n-местных функций g_i=(x₁, х₂,....х_n, z_i), где 1 i m, которые вычислимы по Тьюрингу, то функция f=(x₁, х₂,...х_n, у) также вычислима на машине Тьюринга.

Рассмотрим машину Тьюринга только для одного случая, когда n=1 и m=1. Тогда f=(x, y)=S₁¹ h((z, y), g(x, z)).

Для того, чтобы вычислить по заданным значениям x функцию у=f(х), необходимо и достаточно вычислить значение z=g(х), а по ее значениям вычислить y=h(z)=h(g(х))=f(x).

Таким образом, если h=(z, у) и g=(х, z) вычислимы по Тьюрингу, то их суперпозиция h(g(х))=f(х)=у также вычислима.

Весь процесс вычисления опирается на две машины Тьюринга:

шаг 1: вычислить для х значение z=g (х):

T_g: q_í|^x+1q_k|^{g (x+1) +1}.

шаг 2: вычислить для z=g(х) значение y=h(g(х)):

T_h : q_í|^{g (x+1) +1}q_k|^{h (g (x+1)) +1}.

Вычисленное значение функции h есть значение искомой функции, т.е. y=f(x)=h(g(x)).

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

Если п  1и m  1, то необходимо вычислять m функций g_i,, каждая из которых опирается на n независимых переменных x_i, а затем значения этих функций использовать в качестве независимых переменных z_i функции h.

Алгоритм вычисления оператора суперпозиции:

шаг 1: вычислить для заданных значений x₁, х₂,...х_n функции

g_i (x₁, х₂,...х_n) , где I  i  m:

T_g:q_о|^x1+1 #|^x2+1#...#|^xn+1 q_k|^{g1(x1+1, x2 +1,.. xn+1)+1}#..|^{gm (x1+1, x2+1,... xn+1) +1};

шаг 2: вычислить для полученных значений g_i (x₁, х₂,...х_n) функцию

h(g₁, g₂,...g_n):

T_h:q_о|^{g1(x1+1, x2+1,.. xn+1) +1} #...|^{gm(x1+1, x2+1,.. xn+1) +1}

 q_k|^{h(g1+1, g2 +1,.. gm+1)+1}.

Вычисленное значение функции h есть значение искомой функции у=f(x₁, х₂,...х_n)=h(g_i(x₁, х₂,...х_n), g₂(x₁, х₂,...х_n),...g_m(x₁, х₂,...х_n)).

Оператор рекурсии. Если даны n-местная функция g(x₁, х₂,...х_n) и (n+2)-местная функция h(x₁, х₂,...х_n, y, f(x₁, х₂,...х_n, y)), которые вычислимы на машине Тьюринга, то функция f(x₁, х₂,...х_n,, y+1)=h(x₁, х₂,...х_n, у, f(x₁, х₂,...х_n, y)) также вычислима на машине Тьюринга.

Для иллюстрации этой схемы рассмотрим случай для n=1, т.е.

g(x), h(x, y, f(x, y)) и f(x, y+1)= h(х, у, f(х, у)).

При реализации на машине Тьюринга оператора примитивной рекурсии последняя должна вычислять значения f(x, i+1) до тех пор, пока iу. При достижении i=у процесс вычисления прекращается, и результат вычисления имеет вид f(х, у+1)=h(х, у, f(х, у)).

Итак, машина Тьюринга имеет задание:

T_f: q_о|^x+1# |^y+1#  q_k|^{f (x+1; y+1) +1} # .

Алгоритм вычисления оператора рекурсии:

шаг 1: вычислить для заданного значения х функцию g(х);

T_g: q_о|^x+1 #|^y+1q_k|^x+1 #|^y+1#|^{g(x+1) +1} ,

если g является базовой функцией, то процесс ее вычисления приведен на машинах Т₁, Т₂, Т₃;

шаг 2: ввести переменную i для счета символов слова (у+1):

T_i: q_о|^x+1#|^y+1#|^{g (x+1) +1}q_k|ⁱ⁺¹#|^x+1#|^y+1 #|^{g (x+1) +1};

установить i = 0;

шаг 3: вычислить значение функции h(х, i, f (х, i)):

T_h: q_o|ⁱ⁺¹#|^x+1#|^y+1 #|^{g(x+1) +1}  q_k|ⁱ⁺¹#|^x+1#|^y+1 #|^{h((x+1), i, f (x +1, i)) +1};

шаг 4: проверить i = у;

a) если i  у, то принять i = i+1 и перейти к шагу 3,

b) если i = у перейти к шагу 5;

для проверки условия i = у использовать Т₁₂;

шаг 5: удалить с ленты слова |^y+1, |^x+1 , | ^y+1:

T_k : q_í|^y+1#|^x+1#|^y+1#|^{h (x+1, y, f (x+1, y))+1}#  q_k|^{h (x+1), y, f (x +1, y))+1}#;

шаг 6: выдать результаты расчетов:

q_k|^{h (x+1), y, f (x +1, y))+1}#  |^{f (x +1, y+1)+1}#.

Если каждый шаг вычислительного процесса представить отдельной машиной Тьюринга, то их последовательное соединение (кроме машины, реализующей шаг 4), обеспечивает поиск значения функции f (х; у). Выход на шаге 4 должен поступить на входы машины Т_h или T_k, т.е. машина, реализующая шаг 4, имеет два выхода и реализует предикат. На рис. 5.19 приведена схема соединения машин Тьюринга для оператора примитивной рекурсии.

Если функции g(х) и h(х, у, f(х, у)) не базовые, но вычислимые по схеме примитивной рекурсии, то функция f(х, у) также вычислима на машине Тьюринга.

Оператор минимизации. Для определения наименьшего корня (x₁, х₂,...хn)=_y(f(x₁, х₂,...х_n, y)=0) необходимо организовать последовательное приращение вспомогательного аргумента у = 0. 1. 2.... и сравнивать значение функции f(x₁, х₂,...х_n, y) с базовой функцией Сn=0.

Алгоритм вычисления оператора минимизации:

шаг 1: ввести переменную i в функцию f(x₁, x₂, .. x_n, y):

T_i: q_о| ^{f(x1+1# x2+1#... Xn+1, y+1)}q_k| ^{f(x+11# x2+1#... Xn+1# i+1)}#;

установить i = 0;

шаг 2: вычислить значение функции f(х₁, x₂,...x_n, i):

T_f: q_o| ^{f(x+11# x2+1#... Xn+1# i+1)}#  q_k| ^{f(x+11# x2+1#... Xn+1# i+1)}#;

• если f(x₁, x₂, .. x_n, i)=0, то конец. Принять |ⁱ⁺¹=|^{ (x+11# x2+1#... Xn+1)}#;

• если f(x₁, x₂, .. x_n, i) 0, то принять i=i+1 и перейти к шагу 2:

T_f: q_o| ^{f(x+11# x2+1#... Xn+1# (i+1))+1}#  q_k| ^{f(x+11# x2+1#... Xn+1# (i+1))+!}#.

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

В 70-е годы прошлого века была предложена алгоритмическая модель, представляющая собой идеализированную ЭВМ. Эта модель состоит из бесконечного числа регистров R₁, R₂, R₃,..., в каждом из которых может быть записано натуральное число из N₀.. Часть этих регистров используют для хранения команд (аналог левой полуленты), остальные - для хранения исходных данных, промежуточных и окончательных результатов вычислений (аналог правой полуленты). Такая модель позволяет организовать произвольный доступ к ячейкам памяти (МПД).

Набор команд МПД включает:

• команду обнуления: действие команды Z(n) заключается в замене содержимого регистра R_n на 0;

• команду прибавления единицы: действие команды S(n) заключается в увеличении содержимого регистра R_n на 1;

• команду переадресации: действие команды T(m, n) заключается в замене содержимого регистра R_n числом r_m, хранящимся в регистре R_m;

• команду условного перехода: действие команды заключается в сравнении содержимого регистров R_n и R_m:

- если r_n=r_m, то перейти к исполнению команды q_i;

- если r_nr_m, то перейти к исполнению команды q_j.

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