Лекции - Теория алгоритмов
Подождите немного. Документ загружается.
Оператор суперпозиции
(Продолжение-4. Выполнение программы.)
► В программе вставлены несколько подпрограмм. Модифицируем
правило вставки для случая нескольких подпрограмм.
► 1) Вычисляем число =max(n, m, (G
1
), (G
2
), ... , (G
m
), (H)), и
производим следующее распределение памяти МНР.
► Регистры R
1
, ... , R
предназначены для работы всех подпрограмм
H , G
1
, G
2
, … , G
m.
► Последующие регистры R
+1
, ... , R
+n
выделены в качестве
постоянного хранилища аргументов x
1
, x
2
, ... , x
n
.
► Следующие по порядку регистры R
+n+1
, ... , R
+n+m
являются
рабочими регистрами основной программы, в которых сохраняются
результаты работы подпрограмм G
1
, G
2
, … , G
m
соответственно.
Оператор суперпозиции
(Продолжение-5. Выполнение программы.)
► 2) Командами T(1,+1), ... , T(n,+n)
пересылаем аргументы x
1
, x
2
, ... , x
n
на место
их постоянного хранения – регистры R
+1
, ... ,
R
+n
. Из этих регистров в процессе работы
подпрограмм несколько раз будут считываться
аргументы x
1
, x
2
, ... , x
n
и пересылаться в
регистры R
1
, ... , R
n
. Именно из этих регистров
подпрограммы G
1
, G
2
, … , G
m
будут извлекать
свои аргументы при старте.
Оператор суперпозиции
(Продолжение-6. Выполнение программы.)
► 3) Подпрограммы G
1
, G
2
, … , G
m
вставляются в
основную программу по правилу вставки подпрограмм.
Это правило в общем случае выражено в виде строки
P[i
1
, i
2
, ... i
n
i]. В нашем случае выполняются
следующие действия.
► В регистры R
1
, ... , R
n
считываются аргументы x
1
, x
2
, ...
, x
n
из их постоянного хранилища – регистров R
+1
, ... ,
R
+n
.
► Очищаются от мусора остальные регистры R
n+1
, ... , R
.
► Исполняются команды из G
i
.
► Результат работы, т.е. число y
i
= g
i
(x
1
, x
2
, ... , x
n
)
переносится в регистр R
+n+i
- место хранения
результата работы подпрограммы G
i
.
Оператор суперпозиции
(Окончание. Выполнение программы.)
► Далее вставляется подпрограмма H для
вычисления функции h. Аргументы функции h
равны y
1
= g
1
(x
1
, x
2
, ... , x
n
), y
2
= g
2
(x
1
, x
2
, ... ,
x
n
), ... , y
m
= g
m
(x
1
,x
2
, ... , x
n
) и хранятся в
регистрах R
+n+1
, ... , R
+n+m.
► Подпрограмма H считывает эти аргументы,
затем по правилу вычисляет f(x
1
, x
2
, ... , x
n
) и
пересылает результат в регистр R
1
.
► Затем МНР останавливается.
► Теорема доказана.
Оператор примитивной рекурсии
► Теорема 2. Пусть функция f получена с помощью оператора
примитивной рекурсии из функций g и h. Если функции g и h
МНР вычислимы, то и функция f также МНР вычислима.
► Доказательство. По условию функции g и h МНР вычислимы.
Пусть G и H программы, вычисляющие эти функции. Выразим
кратко процесс вычисления функции f = f(x
1
, x
2
, ... , x
n
, y).
► Сравниваем y с числом 0. Если равенство верно, то вычисляем
f(x
1
, x
2
, ... , x
n
, 0) = g(x
1
, x
2
, ... , x
n
)
и останавливаемся. В противном случае несколько раз применяем
программу H для последовательного вычисления чисел
f(x
1
, x
2
, ... , x
n
, k)
при k=0, 1, ... , y.
Оператор примитивной рекурсии
(Продолжение-1. Программа вычисления)
► T(1, +1)
► ......................
► T(n+1, t+1)
► G[1, 2, ... , n t+3]
► I
q
J(t+2, t+1, p)
► H[+1, ... , +n, t+2, t+3 t+3]
► S(t+2)
► J(1, 1, q)
► I
p
T(t+3, 1)
► При этом I
q
и I
p
- просто особо отмеченные команды с
некоторыми номерами q и p.
Оператор примитивной рекурсии
(Продолжение-2. Блок-схема.)
Оператор примитивной рекурсии
(Продолжение-3. Выполнение программы.)
► 1) Вычисляем число = max(n+2, (G), (H)). Обозначим + n = t.
Регистры для работы программы распределим следующим
способом.
► R
1
, … , R
- регистры для подпрограмм G и H;
► R
+1
, … , R
t+1
- регистры, для постоянного хранилища аргументов
x
1
, x
2
, ... , x
n
, y;
► R
t+2
, R
t+3
- два регистра для запоминания промежуточных значений
k и f(x
1
, x
2
, ... , x
n
, k) в цикле, где k=0, 1, ... , y. Перед первым
исполнением цикла в регистрах R
t+2
и R
t+3
разместим 0 и f(x
1
, x
2
,
... , x
n
, 0).
Оператор примитивной рекурсии
(Продолжение-4. Выполнение программы.)
► 2) Командами T(1, +1), ... , T(n+1, t+1) пересылаем
n+1 аргументов x
1
, x
2
, ... , x
n
, y на место их
постоянного хранения – регистры R
+1
, … , R
t+1
.
► Затем в регистр R
t+3
помещаем число g(x
1
, x
2
, ... , x
n
),
равное f(x
1
, x
2
, ... , x
n
, 0). Это выражено вставкой в
программу строки G[1, 2, ... , n t+3]. Итак, перед
первым выполнением команды I
q
имеем следующее
содержание регистров.
► В регистре R
t+1
число y. Оно не будет изменяется в
процессе выполнения цикла.
► В регистре R
t+2
число k = 0. Оно будет наращиваться
на 1 при каждом проходе цикла.
► В регистре R
t+3
число f(x
1
, x
2
, ... , x
n
, k) при k = 0. Число
k будет наращиваться на 1 при каждом проходе цикла.
Оператор примитивной рекурсии
(Продолжение-5. Выполнение программы.)
► Выполнение команды I
q
начинает цикл. Возвращение
на повторение этой команды производит команда
J(1,1,q). Сравниваются число r
t+2
= k и число r
t+1
,
всегда равное y. Число r
t+2
= k принимает значения 0,
1, ... , y. Для его приращения на 1 предназначена
команда S(t+2). Поэтому в цикле последовательно
проверяются равенства
► 0 = y, 1 = y, ... , y = y.
► Пусть равенство еще не выполнено. Тогда выполняется
вставка H[+1, ... , +n, t+2, t+3 t+3]. Она
вычисляет функцию
► h(x
1
, x
2
, ... , x
n
, k, f(x
1
, x
2
, ... , x
n
, k)),
► то есть число f(x
1
, x
2
, ... , x
n
, k+1).