Лекции - Теория алгоритмов
Подождите немного. Документ загружается.
Лекция 6. Машины с
неограниченными регистрами
► Машина с неограниченными регистрами (МНР) – это абстрактная машина, более
сходная с реальным компьютером по сравнению с машиной Тьюринга. Она имеет
следующие составные части.
► 1) Регистры R
1
, R
2
, ..., в которых содержатся соответственно натуральные
числа r
1
, r
2
, ... .
► Число регистров бесконечно, но только конечное множество регистров R
1
, R
2
, ... R
k
содержит числа, отличные от нуля. Все остальные регистры заполнены нулями.
(продолжение)
► 2) Программа машины – это конечная последовательность I
1
, I
2
, ... , I
s
. из
следующих четырех типов команд:
Z(n), S(n), T(m, n), J(m, n, q),
где m, n, q \{1,2, ... }. Эти команды выполняют следующие действия.
► Команда обнуления Z(n) делает содержимое регистра R
n
равным нулю.
► Команда прибавления единицы S(n) к содержимому регистра R
n
прибавляет число
1.
► Команда переадресации T(m, n) заменяет содержимое регистра R
n
на содержимое
регистра R
m
.
► Команда условного перехода J(m, n, q) сравнивает содержимое регистров R
m
и R
n
.
При r
m
= r
n
в качестве следующей команды выполняется команда с номером q,
в противном случае выполняется следующая по порядку команда программы.
► Команды обнуления, прибавления единицы и переадресации называются
арифметическими командами.
Примеры выполнения команд
► Пусть, например, регистры МНР имеют
вид.
►Выполним команду S(2). Эта команда
прибавит 1 к числу 3 в регистре R
2
и не
затронет остальные регистры. В
результате получим следующее
содержимое регистров
2 3 1 5 0 …
2 4 1 5 0 …
(продолжение)
► Выполним затем команду T(2,1). Содержимое 4
из регистра R
2
заменит старое содержимое 2 в
регистре R
1
. Получим регистры
► Машина с неограниченными регистрами, как и
произвольный алгоритм, работает по тактам:
такт 1, такт 2, … . Первый такт работы МНР с
программой I
1
, I
2
, … ,I
n
- выполнение первой
команды I
1
. Затем выполняются команды I
2
, I
3
,
... .
4 4 1 5 0 …
Условие остановки
► Машина останавливается тогда и только тогда, когда
невозможно выполнить очередную предписанную
команду. Это означает, что МНР только что совершила
i-вый такт работы и следующим i+1 тактом должна
выполнить несуществующую команду. Эта ситуация при
выполнении программы I
1
, I
2
, … ,I
n
возникает ровно в
одном из трех следующих случаев.
► I) Если в i-вом такте выполнена I
n
- последняя
команда программы и эта команда не является
командой условного перехода, тогда следующим i+1
тактом должна выполняться несуществующая команда
I
n+1
.
(продолжение)
► 2) Если в i-вом такте выполнена команда
условного перехода J(m, k, q), где r
m
= r
k
и q >
n, тогда следующим i+1 тактом должна
выполняться несуществующая команда I
q
.
► 3) Если в i-вом такте выполнена I
n
- последняя
команда программы и эта команда является
командой условного перехода J(m, k, q) при r
m
r
k
тогда следующим i+1 тактом должна
выполняться несуществующая команда I
n+1
.
Результат вычислений
► Если выполнение программы завершилось, то
число r
1
из регистра R
1
считается результатом
применения алгоритма к исходному набору
чисел r
1
, r
2
, ... . Если выполнение программы
никогда не заканчивается, то нет результата
вычислений. В этом случае алгоритм
неприменим к исходным данным. Тем самым
при работе МНР возможно лишь два типа
завершения работы: 1) выдача результата и 2)
бесконечная работа. Третий случай
(безрезультатная остановка) невозможен.
Вычисление функций на МНР
► Как и в случае машин Тьюринга, мы должны указать,
как машина с неограниченными регистрами вычисляет
частичную функцию f(x
1
,x
2
, ... , x
n
) от n аргументов.
Рассмотрим набор аргументов (x
1
,x
2
, ... , x
n
) и
разместим число x
1
в регистре R
1
, число x
2
- в
регистре R
2
, ..., число x
n
- в регистре R
n
. Все остальные
регистры заполнены нулями. Получаем начальную
конфигурацию МНР. После окончания работы в
регистре R
1
должно быть значение функции f(x
1
,x
2
, ... ,
x
n
) . Если значение f(x
1
,x
2
, ... , x
n
) не определено, то
МНР должна работать бесконечно.
Пример вычисления функции на
МНР
► Пример. Составить программу для МНР, которая
вычисляет функцию f(x,y)=x+y.
Решение. Рассмотрим работу МНР со следующей
программой:
I
1
J(2,3,5)
I
2
S(1)
I
3
S(3)
I
4
J(1,1,1)
В регистр R
1
перед первым тактом работы машины
занесено число x, в R
2
- число y, остальные регистры
заполнены нулями.
x y 0 0
Пример вычисления функции на
МНР(продолжение-1)
► Первым тактом работы МНР исполняется
команда I
1
=J(2,3,5), где R
2
сравнивается с
R
3
, т.е. y сравнивается с числом 0.
Допустим, например, что y=2. Поскольку y 0,
то вторым тактом работы исполнится команда
S(1), а третьим - S(3). В результате к числам в
регистрах R
1
и R
3
добавится число 1, и
каждый из них увеличится на 1.
X+1 y 1 0