Лекции - Теория алгоритмов
Подождите немного. Документ загружается.
Пример вычисления функции на
МНР(продолжение-2)
► Далее команда J(1, 1, 1) сравнивает
регистр R
1
с самим собой. Получаем
равенство и переход к первой команде I
1
.
Цикл повторится второй раз, и к числам в
регистрах R
1
и R
2
снова добавится число
1. Получим регистры
►Далее I
4
задает переход к первой
команде I
1
.
X+2 y 2 0
Пример вычисления функции на
МНР(продолжение-2)
► Итак, МНР готова выполнить команду I
1
=J(2,3,5) и
совершить третий проход цикла. Однако теперь в
регистрах R
2
и R
3
содержатся равные числа 2 и y. Тогда
J(2,3,5) вызывает команду с номером 5. Такой команды
нет. Поэтому МНР останавливается. В регистре R
1
содержится результат x+2.
► В общем случае произойдет y проходов цикла,
добавляющих к числам в регистре R
1
и R
3
число 1. В
начале y+1 прохода цикла в момент исполнения
команды I
1
=J(2,3,5) в регистре R
1
имеем x+y, в
регистре R
3
- число y. По команде J(2,3,5) МНР
останавливается, имея в регистре R
1
результат
вычислений x+y.
Вычислимость простейших
функций на МНР
► Теорема. Простейшие функции
s(x)=x+1, o
n
(x
1
,x
2
,...,x
n
)=0, I
n
m
(x
1
,x
2
,...,x
n
)=x
m
вычислимы на МНР.
► Доказательство. Укажем программы для вычисления
данных функций.
► 1) Функция следования s(x) имеет программу из одной
команды S(1). Действительно, если в регистре R
1
занесено число x, то МНР выполнит один такт работы,
сменит число x в R
1
на число x+1 и остановится.
► 2) Аналогично программа, состоящая из одной команды
Z(1), вычисляет нулевую функцию o
n
(x
1
,x
2
,...,x
n
)=0.
Вычислимость простейших
функций на МНР (продолжение)
► 3) Для функции проектирования
I
n
m
(x
1
,x
2
,...,x
n
)=x
m
применяем программу из
одной команды T(m,1). МНР выполнит один
такт работы, перешлет в регистр R
1
число x
m
и
остановится. Теорема доказана.
► Итак, все простейшие функции из определения
частично рекурсивной функции вычислимы на
МНР. Далее установим, что все частично
рекурсивные функции вычислимы на МНР.
Стандартный вид программы
► Сложная программа часто содержит другие программы в
качестве строительных блоков - подпрограмм. Для правильного
взаимодействия этих подпрограмм нужно соблюдать некоторые
правила.
► Определение. Пусть дана программа для МНР, состоящая из s
команд. Будем говорить, что программа имеет стандартный вид,
если во всякой команде условного перехода J(m,n,q) данной
программы выполняется неравенство q s + 1.
► Если программа P не имеет стандартного вида, то в ней найдется
команда вида J(m, n, q), где q > s+1. Заменим в программе P эту
команду на команду J(m,n, s + 1). Получим программу P
’
’,
выполняющую точно такое же действие, как и программа P.
Действительно, P и P’ отличаются лишь командами J(m, n, q) и
J(m,n, s + 1). Однако действие этих команд одинаково: при r
m
r
n
нужно перейти к следующей по порядку команде, а при r
m
= r
n
остановиться.
Стандартный вид программы
(продолжение)
► Определение .Стандартизацией программы I
1
,
I
2
, … ,I
s
называется замена в данной
программе всех команд J(m, n, q) где q > s+1,
на команды J(m, n, s + 1).
► В результате стандартизации из программы P
нестандартного вида получим стандартную
программу P’ с тем же действием. Используя
P’ вместо P, считаем, что все программы,
которые мы рассматриваем, стандартны.
Соединение программ
► Определение. Соединением программ P: I
1
, I
2
,
..., I
s
и Q: I’
1
, I’
2
, ..., I’
t
называется программа
из s+t команд вида
I
1
, I
2
, ..., I
s
, I
s+1
, I
s+2
, ..., I
s+t
,
где команды I
s+1
, I
s+2
, ..., I
s+t
получены из
команд I’
1
, I’
2
, ..., I’
t
программы Q приращением
номеров на число s. При этом каждая команда
условного перехода J(m, n, q) из Q заменена
на команду вида J(m, n, q+s ).
► Соединение программ P и Q будем обозначать
через PQ. Можно соединить программы P, Q, R
и получить программу PQR=(PQ)R и т.д.
Выделения регистров для
подпрограммы
► Пусть программа P используется как подпрограмма в основной
программе Q. В некоторых регистрах хранятся данные основной
программы. При выполнении подпрограммы P можно испортить
данные основной программы Q. Для предотвращения такой
потери данных делаем так, что основная программа изменяет
одну область регистров, а подпрограмма - другую.
► Произвольная МНР программа P имеет конечное число команд.
Команда обнуления Z(n) и команда прибавления единицы S(n)
действуют только на один регистр R
n
. Команде переадресации
T(m, n) и команде условного перехода J(m, n, q) для
функционирования нужны два регистра R
m
и R
n
. Если общее
число команд обнуления и прибавления единицы равно k, а
число команд переадресации и условного перехода равно l, то
для работы всей программы P достаточно зарезервировать k+2l
регистров.
Правило выделения регистров для
подпрограммы
► Пусть = (P) - число с условием, что действие
программы P меняет лишь регистры R
1
, … R
и не
затрагивает регистры R
l
для l> .
► Отводим регистры R
1
, … R
для работы подпрограммы
P, и выделяем регистры R
l
при l> в качестве
рабочих регистров для остальных команд основной
программы Q.
► Если соблюдено правило выделения регистров, то
программа P в процессе выполнения меняет лишь
регистры R
1
, … R
, а данные программы Q находятся в
регистрах R
l
при l> и не могут быть затронуты и
испорчены программой P.
Вставка подпрограммы
► Пусть в программе Q имеется подпрограмма P
для вычисления функции f (x
1
,x
2
,...,x
n
). В
подпрограмме P имеются входные данные
(x
1
,x
2
,...,x
n
) и результат вычислений f
(x
1
,x
2
,...,x
n
). По определению МНР должны
соблюдаться следующие требования.
1. При старте P аргументы (x
1
,x
2
,...,x
n
) обязаны
находиться в регистрах R
1
, ... ,R
n.
.
2. После окончания работы подпрограммы P
результат f (x
1
,x
2
,...,x
n
) должен содержаться в
регистре R.