A08DPPMAT_UPS2006D00

Упражнения к лекции 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