A08DPPMAT_UPS2006D00
.pdfУпражнения к лекции 5
В задачах 1–7 нужно составить программу машины Тьюринга для вычисления функции f x от одной переменной.
ЗАДАЧА 1. f x — нулевая функция o x .
ЗАДАЧА 2. f x — функция следования s x x 1.
ЗАДАЧА 3. f x |
2. |
|
ЗАДАЧА 4. f x |
x 2. |
|
ЗАДАЧА 5. f x |
x. |
|
ЗАДАЧА 6. f x |
x |
1. |
ЗАДАЧА 7. f x |
x |
1. |
В задачах 8–9 нужно составить программу машины Тьюринга для вычисления функции f x, y от двух переменных.
ЗАДАЧА 8. f x, y |
x 1. |
ЗАДАЧА 9. f x, y |
x y 1. |
ЗАДАЧА 10. Составить программу машины Тьюринга для вычисления функции f x, y, z x y z.
41
Лекция 6. Машины с неограниченными регистрами
Машина с неограниченными регистрами (МНР) — это абстрактная машина, более сходная с реальным компьютером по сравнению с машиной Тьюринга. Она имеет следующие составные части.
1) Регистры R1, R2, R3, . . ., в которых содержатся соответственно натуральные числа r1, r2, r3, . . .
r1 |
r2 |
r3 |
. . . |
rk |
0 |
. . . |
R1 R2 |
R3 |
. . . Rk Rk 1 . . . |
Число регистров бесконечно, но только конечное множество регистров R1, R2, . . . , Rk содержит числа, отличные от нуля. Все остальные регистры Rk 1, Rk 2, . . . заполнены нулями.
2) Программа машины — это конечная последовательность I1, I2, . . . , Is из следующих четырех типов команд:
Z n , S n , T m, n , J m, n, q ,
где m, n, q 1, 2, . . . . Эти команды выполняют следующие действия.
•Команда обнуления Z n делает содержимое регистра Rn равным нулю.
•Команда прибавления единицы S n к содержимому регистра Rn
прибавляет число 1.
•Команда переадресации T m, n заменяет содержимое регистра Rn на содержимое регистра Rm.
•Команда условного перехода J m, n, q сравнивает содержимое
регистров Rm и Rn. При rm rn в качестве следующей команды выполняется команда с номером q. Если rn rm, то выполняется следующая по порядку команда программы.
Команды обнуления, прибавления единицы и переадресации называются арифметическими командами. Отразим действие команд следующей таблицей (табл. 1).
42
Обозначение |
Действие, производимое МНР |
команды |
при выполнении команды |
|
|
Z n |
rn : 0 |
S n |
rn : rn 1 |
T m, n |
rn : rm |
|
Если rn rm, то перейти к выполнению команды с но- |
J(m, n, q) |
мером q, иначе выполнить следующую по порядку ко- |
|
манду. |
|
|
|
Таблица 1: Команды МНР |
Пусть, например, регистры МНР имеют вид
23 1 5 0 . . .
Выполним команду S 2 . Эта команда прибавит 1 к числу 3 в регистре R2 и не затронет остальные регистры. В результате получим следующее содержимое регистров
24 1 5 0 . . .
Выполним затем команду T 2, 1 . Содержимое 4 из регистра R2 заменит старое содержимое 2 в регистре R1. Получим регистры
44 1 5 0 . . .
Машина с неограниченными регистрами, как и произвольный алгоритм, работает по тактам: такт 1, такт 2, . . . Первый такт работы МНР с программой I1, I2, . . . , Is — выполнение первой команды I1. Затем выполняются команды I2, I3, . . . Этот последовательный порядок выполнения команд продолжается до тех пор, пока не встретится команда J(m, n, q), которая может изменить естественный порядок выполнения команд.
Условие остановки. Машина останавливается тогда и только тогда, когда невозможно выполнить очередную предписанную команду. Это означает, что МНР только что совершила i-вый такт работы и следующим i 1 тактом должна выполнить несуществующую команду. Эта ситуация при выполнении программы I1, I2, . . . , Is возникает ровно в одном из трех следующих случаев.
43
I) Если в i-вом такте выполнена Is — последняя команда программы и эта команда не является командой условного перехода, тогда следующим i 1 тактом должна выполняться несуществующая команда Is 1.
2) Если в i-вом такте выполнена команда условного перехода J m, n, q , где rm rn и q s, тогда следующим i 1 тактом должна выполняться несуществующая команда Iq .
3) Если в i-вом такте выполнена Is — последняя команда программы и эта команда является командой условного перехода J m, n, q при rm rn, тогда следующим i 1 тактом должна выполняться несуществующая команда Is 1.
Результат вычислений. Если выполнение программы завершилось, то число r1 из регистра R1 считается результатом применения алгоритма к исходному набору чисел r1, r2, . . . . Если выполнение программы никогда не заканчивается, то нет результата вычислений. В этом случае алгоритм неприменим к исходным данным. Тем самым при работе МНР возможно лишь два типа завершения работы: 1) выдача результата и 2) бесконечная работа. Третий случай (безрезультатная остановка) невозможен.
Вычисление функций на МНР. Как и в случае машин Тьюринга, мы должны указать, как машина с неограниченными регистрами вычисляет частичную функцию f x1, . . . , xn от n аргументов. Рассмотрим набор аргументов x1, . . . , xn , и разместим число x1 в регистре R1, число x2 — в регистре R2, . . . , число xn — в регистре Rn. Все остальные регистры заполнены нулями. Получаем начальную конфигурацию МНР. После окончания работы в регистре R1 должно быть значение функции f x1, . . . , xn . Если значение f x1, . . . , xn не определено, то МНР должна работать бесконечно.
ПРИМЕР 6.1. Составить программу для МНР, которая вычисляет функцию f x x 2.
Решение. Рассмотрим работу МНР со следующей программой:
I1 S 1
I2 S 1
В регистр R1 перед первым тактом работы машины занесено число x, остальные регистры заполнены нулями. Машина совершит два такта работы, два раза прибавит 1 к числу x в регистре R1 и остановится. Число x 2 — результат вычислений, что и нужно.
44
ПРИМЕР 6.2. Составить программу для МНР, которая вычисляет функцию f x, y x y.
Решение. Рассмотрим работу МНР со следующей программой:
I1 J 2, 3, 5
I2 S 1
I3 S 3
I4 J 1, 1, 1
В регистр R1 перед первым тактом работы машины занесено число x, в R2 — число y, остальные регистры заполнены нулями.
x y 0 0
R1 R2 R3 R4
Первый тактом работы МНР исполняется команда I1 J 2, 3, 5 , где R2 сравнивается с R3, т.е. y сравнивается с числом 0.
Допустим, например, что y |
2. Поскольку y 0, то вторым тактом |
||||
работы исполнится команда S 1 , а третьим — S 3 . В результате к чис- |
|||||
лам в регистрах R1 и R3 добавится число 1, и каждый из них увеличится |
|||||
на 1. |
|
|
|
|
|
|
x 1 |
y |
1 |
0 |
|
|
|
|
|
|
|
|
R1 |
R2 |
R3 |
R4 |
Далее команда J 1, 1, 1 сравнивает регистр R1 с самим собой. Получаем равенство и переход к первой команде I1. Цикл повторится второй раз, и к числам в регистрах R1 и R3 снова добавится число 1. Получим регистры
|
|
x 2 |
y |
2 |
0 |
|
|
|
|
|
|
|
|
|
|
R1 |
R2 R3 R4 |
|||
Далее I4 задает переход к первой команде I1. Итак, МНР готова выпол- |
||||||
нить команду I1 |
J 2, 3, 5 и совершить третий проход цикла. Однако |
теперь в регистрах R2 и R3 содержатся равные числа 2 и y. Тогда J 2, 3, 5 вызывает команду с номером 5. Такой команды нет. Поэтому МНР останавливается. В регистре R1 содержится результат x 2.
Вобщем случае произойдет y проходов цикла, добавляющих к числам
врегистре R1 и R3 число 1. В начале y 1 прохода цикла в момент испол-
нения команды I1 J 2, 3, 5 в регистре R1 имеем x y, в регистре R3 —
45
число y. По команде J 2, 3, 5 МНР останавливается, имея в регистре R1 результат вычислений x y.
Обозначим через F множество всех функций, которые можно вычислить на подходящей машине с неограниченными регистрами.
ТЕОРЕМА 6.1. Следующие функции вычислимы на МНР. 1 Функция следования s x .
2 Нулевая функция on x1, x2, . . . , xn .
3 Функция проектирования Imn x1, x2, . . . , xn .
Доказательство. Укажем программы для вычисления данных функций.
1)Функция следования s x имеет программу из одной команды S 1 .
Действительно, если в регистре R1 занесено число x, то МНР выполнит один такт работы, сменит число x в R1 на число x 1 и остановится.
2)Аналогично программа, состоящая из одной команды Z 1 , вычис-
ляет нулевую функцию on x1, x2, . . . , xn .
3) Для функции проектирования Imn x1, x2, . . . , xn применяем программу из одной команды T m, 1 . МНР выполнит один такт работы, перешлет в регистр R1 число xm и остановится.
Теорема доказана.
Итак, все простейшие функции из определения частично рекурсивной функции вычислимы на МНР. Далее установим, что все частично рекурсивные функции вычислимы на МНР.
Сложная программа часто содержит другие программы в качестве строительных блоков — подпрограмм. Для правильного взаимодействия этих подпрограмм нужно соблюдать некоторые правила.
ОПРЕДЕЛЕНИЕ 6.1 . Пусть дана программа для МНР, состоящая из 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 . Однако действие этих команд одинаково: при rm rn нужно перейти к следующей по порядку команде, а при rm rn остановиться.
46
ОПРЕДЕЛЕНИЕ 6.2 . Стандартизацией программы I1, I2, . . . , Is называется замена в данной программе всех команд J m, n, q , где q s 1, на команды J m, n, s 1 .
В результате стандартизации из программы P нестандартного вида получим стандартную программу P с тем же действием. Используя P вместо P , считаем, что все программы, которые мы рассматриваем, стандартны.
Пусть даны две программы P I1, I2, . . . , Is и Q I1, I2, . . . , It стандартного вида. Применим следующий прием — соединение программ.
ОПРЕДЕЛЕНИЕ 6.3 . Соединением программ P и Q называется программа из s t команд вида
I1, I2, . . . , Is,Is 1, Is 2, . . . , Is t, |
(6.1) |
||||
|
P |
|
Q |
|
|
где команды Is 1, Is 2, . . . , Is t получены из команд I1, I2, . . . , It программы Q приращением номеров на число s. При этом каждая ко-
манда условного перехода J m, n, q из Q заменена на команду вида
J m, n, q s .
Замена команды J m, n, q на команду J m, n, q s нужна по следующей причине. Номера команд из Q, когда эти команды перемещены на новые позиции в (6.1), подросли на s. Если в команде переадресации J m, n, q оставлен старый номер q , то вызываемой команды с таким номером q уже нет, т.к. у нее новый номер q s. Поэтому нужна команда J m, n, q s .
Соединение программ P и Q будем обозначать через P Q. Можно соединить программы P , Q, R и получить программу P QR P Q R и т.д.
Выделения регистров для подпрограммы. Пусть программа P используется как подпрограмма в основной программе Q. В некоторых регистрах хранятся данные основной программы. При выполнении подпрограммы P можно испортить данные основной программы Q.
Для предотвращения такой потери данных делаем так, что основная программа изменяет одну область регистров, а подпрограмма — другую. Произвольная МНР программа P имеет конечное число команд. Команда обнуления Z n и команда прибавления единицы S n действуют только на один регистр Rn. Команде переадресации T m, n и команде условного перехода J m, n, q для функционирования нужны два регистра Rm и Rn. Если общее число команд обнуления и прибавления единицы равно k,
47
а число команд переадресации и условного перехода равно l, то для работы всей программы P достаточно зарезервировать k 2l регистров. На остальные регистры программа P не действует, и их можно использовать в качестве рабочих регистров основной программы. Поэтому в дальнейшем применяем следующее правило выделения регистров подпрограммы P в программе Q.
ПРАВИЛО 6.1 . Пусть ρ ρ P число с условием, что действие программы P меняет лишь регистры R1, . . . , Rρ и не затрагивает регистры Rl для l ρ. Отводим регистры R1, . . . , Rρ для работы подпрограммы P , и выделяем регистры Rl при l ρ в качестве рабочих регистров для остальных команд основной программы Q.
Это правило изображено в следующем виде
R1, . . . , Rρ , |
Rρ 1, . . . |
(6.2) |
регистры для P |
регистры для Q |
|
Если соблюдено правило выделения регистров, то программа P в процессе выполнения меняет лишь регистры R1, . . . , Rρ, а данные программы Q находятся в регистрах Rρ 1, . . . и не могут быть затронуты и испорчены программой P .
Вставка подпрограммы. Пусть в программе Q имеется подпрограмма P для вычисления функции f x1, . . . , xn . В подпрограмме P имеются входные данные x1, . . . , xn и результат вычислений f x1, . . . , xn . По определению МНР должны соблюдаться следующие требования.
•При старте P аргументы x1, . . . , xn обязаны находиться в регистрах
R1, . . . , Rn.
•После окончания работы подпрограммы P результат f x1, . . . , xn должен содержаться в регистре R1.
Однако в ходе работы основной программы Q возможно следующее. Настал момент для старта подпрограммы P , которой нужны аргументы x1, . . . , xn. В данный момент аргументы хранятся в каких-то регистрах Ri1 , . . . , Rin, а не в регистрах R1, . . . , Rn, как нужно. Поэтому перед применением подпрограммы P мы должны извлечь аргументы из Ri1 , . . . , Rin и переслать их в регистры R1, . . . , Rn. Для осуществления такой пересылки аргументов выполняется следующее действие.
48
1) Перед командами из P размещается набор команд
T i1, 1 , . . . , T in, n .
Пусть основная программа Q вызвала подпрограмму P и в начало зарезервированных регистров R1, . . . , Rρ скопированы числа x1, . . . , xn, с которыми начнет работать подпрограмма P . Однако в регистрах Rn 1, . . . , Rρ может оставаться мусор — произвольные числа оставшиеся от предыдущей работы Q. По правилам работы МНР в последующих регистрах Rn 1, . . . , Rk должны быть только одни нули. Поэтому нужно выполнить обнуление этих регистров от мусора, которое осуществляется следующим способом.
2) Выполняется набор команд Z n 1 , . . . , Z ρ .
После выполнения подпрограммы P результат находится в регистре R1. Однако регистр R1 нужен для последующих вычислений программы Q. Поэтому из регистра R1 результат выполнения подпрограммы P нужно пересылать для его последующего использования на хранение в некоторый рабочий регистр Ri, где i ρ P . Это можно осуществить следующим способом.
3) Выполняется команда переадресации T 1, i .
Итак, для правильной работы подпрограммы P могут потребоваться следующие действия, которые назовем вставкой подпрограммы.
ОПРЕДЕЛЕНИЕ 6.4. Вставка подпрограммы P в основную программу МНР — это выполнение следующих действий 1 –5 .
1 Распределение памяти. Вычисляется число ρ ρ P и выделяется память R1, . . . , Rρ, достаточная для работы подпрограммы P . Задается регистр Ri, где i ρ, для хранения результата работы подпрограммы.
2 Извлечение аргументов. Для этого записываются следующие команды: T i1, 1 , . . . , T in, n для передачи аргументов из места их хранения в регистры R1, . . . , Rn.
3 Очистка регистров. Для этого записываются следующие команды:
Z n 1 , . . . , Z ρ .
4 Вставка команд подпрограммы P .
5 Пересылка результата на хранение. Добавляется команда T 1, i .
49
В итоге в основной программе получается следующий фрагмент
Ti1, 1
. . .
Tin, n
Z n 1
. . . |
(6.3) |
Z ρ
P
T 1, i
Вставку данного фрагмента в основную программу обозначаем через
P i1, . . . , in i . |
(6.4) |
50