Машины с неограниченными регистрами определение

Алгоритмы для исполнителя МНР

(машины с неограниченными регистрами)

Опишем исполнителя МНР. МНР состоит из памяти данных и программной памяти. Ячейки памяти данных называют регистрами и обозначают R0, R1, R2 и т.д. до бесконечности. В каждом регистре может содержаться любое целое неотрицательное число. Число, содержащееся в Rn, или значение регистра Rn будем обозначать r_n. В каждый момент времени только конечное число регистров содержит какие-то числа, т.е. память данных является не бесконечной, а потенциально бесконечной. МНР работает по программе. Программой называется пронумерованная конечная последовательность команд, хранящаяся в программной памяти. Программная память МНР также является потенциально бесконечной. Будем считать, что во всех ячейках, свободных от команд программы записана специфическая команда – Stop, результатом исполнения которой является остановка выполнения программы.

Система команд МНР содержит следующие команды:

1. Команда обнуления.

Команда обнуления записывается Z(n). Команда Z(n) выполняется так: содержимое регистра Rn обнуляется, т.е. r_n становится равным нулю (r_n:=0), содержимое других регистров не изменяется.

Пример 5. Пусть начальная конфигурация МНР имеет вид:

МНР выполнит команду обнуления – Z(3). Результатом будет следующая

2. Команда прибавления единицы.

Команда прибавления единицы имеет вид S(n). Команда S(n) выполняется так: содержимое регистра Rn увеличивается на единицу, т.е. r_n:=r_n+1, новое значение r_n равно старому значению, сложенному с 1, содержимое других регистров не изменяется.

Пример 6. Пусть начальная конфигурация МНР имеет вид (*). МНР выполнит команду S(4). Тогда новая конфигурация имеет вид:

3. Команда переадресации.

Команда переадресации имеет вид T(m,n). Команда T(m,n) выполняется так: содержимое регистра Rn заменяется числом r_m, содержащимся в регистре Rm, т.е. r_n:=r_m, содержимое других регистров (включая Rm) не изменяется.

Пример 7. Пусть начальная конфигурация МНР имеет вид (**). МНР выполнит команду T(4,2). Тогда новая конфигурация МНР имеет вид:

В МНР есть особый регистр, который назовем счетчиком адресов команд (САК). При запуске программы на выполнение в САК заносится 1. Выполнение каждой команды МНР состоит из четырех этапов:

1. Читается адрес из САК.

2. Запоминается команда из памяти по этому адресу.

3. САК увеличивается на единицу.

4. Выполняется запомненная команда.

МНР выполняет каждую команду программы в 4 этапа, пока не встретит команду Stop.

Команды обнуления, прибавления единицы и переадресации называются арифметическими. После каждой команды типа 1-3 выполняется команда со следующим номером.

4. Команда условного перехода.

В работе алгоритма могут быть моменты, когда предписываются альтернативные действия, зависящие от результата работы алгоритма к этому моменту. В других ситуациях может потребоваться повторить группу команд несколько раз. МНР может выполнять такие процедуры, используя команды условного перехода; они позволяют делать скачки вперед и назад в списке команд. Мы будем использовать команду условного перехода для совершения, например, следующего действия: «Если r₂=r₆, перейди к десятой команде программы, в противном случае, перейди к следующей команде программы». Команда, вызывающая это действие, записывается как J(2,6,10).

Команда условного перехода в общем виде записывается так J(m,n,q). Выполнение команды осуществляется следующим образом: сравнивается содержимое регистров Rm и Rn, если r_m=r_n, то МНР переходит к выполнению q-ой команды исполняемой программы, в САК заносится число q; если r_m¹r_n, то МНР переходит к выполнению команды, следующей в программе за J(m,n,q), САК увеличивается на единицу, содержимое регистров не изменяется. Если условный переход невозможен ввиду того, что в исполняемой программе команд меньше, чем q, то МНР прекращает работу.

С помощью данной команды можно осуществлять и безусловный переход. Для этого команду нужно записать следующим образом: J(m,m,q).

Работа на МНР состоит из следующих этапов:

1. Заполняем регистры памяти данных какими-то числами, т.е. задаем так называемую начальную конфигурацию.

2. Заполняем командами ячейки программной памяти.

3. Записываем в САК единицу, запускаем МНР и она работает так, как было описано выше до тех пор, пока не встретит команду Stop. При этом полученное по окончании работы машины содержимое регистров памяти данных называется конечной конфигурацией.

Задача 37. Напишите для исполнителя МНР алгоритм вычисления суммы целых положительных чисел x и y, результат запишите в регистр R0.

Решение. Поместим x в регистр R0, y – в регистр R1, т.е. зададим начальную конфигурацию:

Блок-схема алгоритма: Алгоритм вычисления x+y:

Исполнение алгоритма при x=3, y=2

Исполнение алгоритма представим в виде последовательности состояний конфигурации МНР после исполнения очередной команды.

Задача 38. Напишите для исполнителя МНР алгоритм определения является ли треугольник с заданными сторонами a, b, c равнобедренным: . Результат запишите в регистр R0.

Решение. Зададим начальную конфигурацию:

Алгоритм вычисления t:

Исполнение алгоритма при a=5, b=4, c=4

Задача 39.Напишите для исполнителя МНР алгоритм нахождения большего из трех целых положительных чисел t = max(x,y,z). Результат запишите в регистр R0.

Решение. Зададим начальную конфигурацию:

В регистре R3 будем вначале хранить min(x,y), а затем min(max(x,y),z)).

Источник

Немного логики…

Задача #2 «Позитивные автоматы»

Для тех, кто не хочет читать:

Найти значение выражения: |x — |y||
X, Y — любые целые ( и отрицательные тоже )

Ограничение: нельзя пользоваться sub, dec… и любое другое вычитание, нельзя пользоваться регистрами флагов и бинарными операциями. (в частности сдвигами)
Все что у вас есть: je, cmp (нельзя смотреть флаги), jmp, inc, mov. (я же сказал, немного)

Для того, что бы лучше разобраться в задаче:

Есть такая замечательная штуковина, называется:
Машина с неограниченными регистрами (МНР)
Итак, зачем это? Лично для меня — расшевелить мозги.

Теперь попробуем в деле!

Как ей можно пользоваться? Пример: сложите два числа, в R0-первое число, в R1-второе число. Ответ записать в R0, при том r0, r1 >= 0

Замечание: я пишу имена регистров rn, а не Rn, и имена команд тоже маленькими, имхо удобнее.

Решение:
с1) s(r0); x = x+1
c2) s(r2); r2 = r2+1
c3) j(r2,r1,c1); если r2=r1, тогда прыгнуть на с1.
с4)

Как видно, если не произойдет прыжок на метке c3, то программа остановиться и в регистре r0 будет ответ.

Ограничения:
— прыгать можно только на метки (нельзя делать адрес переменным)
— класть в регистры отрицательные числа

Если на МНР писать большие программы (например ОС), удобно сделать эквивалентные команды для ассемблера (тестирование).

Заметка:
r0. rn — это зарезервированные в памяти слова. Пример: r0 dw 0
При том все «регистры» сначала в нуле.

МНР команды / АСМ. эквивалент

T(r1,r2) mov ax,r2
mov r1,ax

J(r1,r2,c1) mov ax,r2
cmp r1,ax
je c1

В общем идея: завязать себе правую руку на ноге, склеить 3 пальца на левой руке и пойти прогить на асме. Ну ничего, у нас целые 4 команды.

Хватит теории, пора задачи решать.

Задача 1. Найти ошибку в моем примере.
Задача 2. Вычесть одно число из другого, при том первое больше. r0 — первое, r1- второе. Результат в r0
Задача 3. Найти значение выражения: |x — |y||
X, Y — любые целые ( и отрицательные тоже )
r0 — x; r1-y. Результат записать в r0. В комментариях привести аналог на ассемблере или на МНР.

Источник

Машины с неограниченными регистрами

Использование механических вычислительных процессов для решения однотипных задач. Составляющие машины с неограниченными регистрами. Отражение команд обнуления, прибавления единицы и переадресации. Реализация подстановки, рекурсии и минимизации.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Министерство образование Узбекистана

Ургенчский Государственный Университет

по курсу: «Теория алгоритмов»

Тема: «Машины с неограниченными регистрами»

Выполнил: Режепов Нуршод

Проверил: Мадатов Х

1. Машина с неограниченными регистрами (МНР)

2. Соединение программ

3. МНР-вычислимость частично рекурсивных функций

3.1 Реализация подстановки на МНР

3.2 Реализация рекурсии на МНР

3.3 Реализация минимизации на МНР

3.4 Основной результат

машина неограниченный регистр вычислительный

Машина с неограниченными регистрами является исполнителем, представляющим собой простой «идеализированный компьютер». Идеализация состоит в том, что каждый отдельный реальный компьютер ограничен как величиной чисел, которые поступают на вход, так и размером памяти (необходимой для запоминания промежуточных результатов), МНР лишена этих ограничений. Машина с неограниченными регистрами имеет неограниченно большую память, ячейки которой будем называть регистрами и обозначать R₁, R₂, R₃,…. Каждый регистр в любой момент времени содержит неотрицательное целое число.

1. Машина с неограниченными регистрами (МНР)

Машина с неограниченными регистрами (МНР) состоит из:

1) ленты, содержащей бесконечное число регистров, обозначаемых через R1, R2, R3, …, каждый из которых в любой момент времени содержит некоторое натуральное число. Число, содержащееся в Rn, мы будем обозначать через rn;

2) программы Р, состоящей из конечного списка команд.

Команды бывают следующих четырех видов:

обозначается также 0 Rn или r_n:= 0 (читается, как rn присваивается 0);

Команды обнуления, прибавления единицы и переадресации называются арифметическими.

1) Регистры R1, R2, R3. в которых содержатся соответственно натуральные числа r1, r2, r3.

Число регистров бесконечно, но только конечное множество регистров

R₁, R₂. R_k содержит числа, отличные от нуля. Все остальные регистры R_k+1, R_k+2. заполнены нулями.

I₁, I₂. I_s из следующих четырех типов команд:

* Команда обнуления Z(n) делает содержимое регистра Rn равным нулю.

* Команда прибавления единицы S(n) к содержимому регистра Rn прибавляет число 1.

* Команда переадресации T(m, n) заменяет содержимое регистра Rn на содержимое регистра Rm.

Команды обнуления, прибавления единицы и переадресации называются арифметическими командами. Отразим действие команд следующей таблицей (табл. 1).

Действие, производимое МНР

при выполнении команды

Если rn= rm, то перейти к выполнению команды с номером q, иначе выполнить следующую по порядку команду.

Таблица 1: Команды МНР

Пусть, например, регистры МНР имеют вид

Выполним команду S(2). Эта команда прибавит 1 к числу 3 в регистре R2 и не затронет остальные регистры. В результате получим следующее содержимое регистров

Выполним затем команду T(2,1). Содержимое 4 из регистра R₂ заменит старое содержимое 2 в регистре R₁. Получим регистры

Условие остановки. Машина останавливается тогда и только тогда, когда невозможно выполнить очередную предписанную команду. Это означает, что МНР только что совершила i-вый такт работы и следующим i+1 тактом должна выполнить несуществующую команду. Эта ситуация при выполнении программы I₁, I₂. I_s возникает ровно в одном из трех следующих случаев.

2) Если в i-вом такте выполнена команда условного перехода J (m, n, q), где r_m= r_n и q > s, тогда следующим i+ 1 тактом должна выполняться несуществующая команда Iq.

Результат вычислений. Если выполнение программы завершилось, то число r₁ из регистра R₁ считается результатом применения алгоритма к исходному набору чисел r₁, r₂. Если выполнение программы никогда не заканчивается, то нет результата вычислений. В этом случае алгоритм неприменим к исходным данным. Тем самым при работе МНР возможно лишь два типа завершения работы: 1) выдача результата и 2) бесконечная работа. Третий случай (безрезультатная остановка) невозможен.

ПРИМЕР 6.1. Составить программу для МНР, которая вычисляет функцию f(x) = x +2.

Решение. Рассмотрим работу МНР со следующей программой:

ПРИМЕР 6.2. Составить программу для МНР, которая вычисляет функцию f (x, y) = x+y.

Решение. Рассмотрим работу МНР со следующей программой:

В регистр R₁ перед первым тактом работы машины занесено число x,

Первый тактом работы МНР исполняется команда I₁ J (2, 3, 5), где R₂ сравнивается с R₃, т.е. y сравнивается с числом 0.

Далее I₄ задает переход к первой команде I₁. Итак, МНР готова выполнить команду I=J (2, 3, 5) и совершить третий проход цикла. Однако теперь в регистрах R₂ и R₃ содержатся равные числа 2 и y. Тогда J(2, 3, 5) вызывает команду с номером 5. Такой команды нет. Поэтому МНР останавливается. В регистре R₁ содержится результат x+ 2.

В общем случае произойдет y проходов цикла, добавляющих к числам в регистре R₁ и R₃ число 1. В начале y+ 1 прохода цикла в момент исполнения команды I₁ J(2, 3, 5) в регистре R1 имеем x+ y, в регистре R₃-число y. По команде J(2, 3, 5) МНР останавливается, имея в регистре R₁ результат вычислений x+ y.

Обозначим через F множество всех функций, которые можно вычислить на подходящей машине с неограниченными регистрами.

ТЕОРЕМА 6.1. Следующие функции вычислимы на МНР.

1 Функция следования s(x).

Доказательство. Укажем программы для вычисления данных функций.

1) Функция следования s(x) имеет программу из одной команды S(1).

Действительно, если в регистре R₁ занесено число x, то МНР выполнит один такт работы, сменит число x в R₁ на число x+1 и остановится.

2) Аналогично программа, состоящая из одной команды Z(1), вычисляет нулевую функцию o n (x₁, x₂. x_n).

3) Для функции проектирования (x₁, x₂. x_n) применяем программу из одной команды T (m, 1). МНР выполнит один такт работы, перешлет в регистр R₁ число x_m и остановится.

Итак, все простейшие функции из определения частично рекурсивной функции вычислимы на МНР. Далее установим, что все частично рекурсивные функции вычислимы на МНР.

ОПРЕДЕЛЕНИЕ 6.2. Стандартизацией программы I₁, I₂. I_s называется замена в данной программе всех команд J (m, n, q), где

q s+1, на команды J (m, n, s+1).

В результате стандартизации из программы P нестандартного вида получим стандартную программу P? с тем же действием. Используя P? вместо P, считаем, что все программы, которые мы рассматриваем, стандартны.

ОПРЕДЕЛЕНИЕ 6.3. Соединением программ P и Q называется программа из s+ t команд вида

где команды I_s+1, I_s+2. I_s+t получены из команд I?₁, I?₂. I?_t программы 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 будем обозначать через PQ. Можно соединить программы P, Q, R и получить программу PQR=(PQ)R и т.д.

Выделения регистров для подпрограммы. Пусть программа P используется как подпрограмма в основной программе Q. В некоторых регистрах хранятся данные основной программы. При выполнении подпрограммы P можно испортить данные основной программы Q.

ПРАВИЛО 6.1. Пусть с=с(P) число с условием, что действие программы P меняет лишь регистры R1. Rс и не затрагивает регистры Rl для l? с. Отводим регистры R₁. Rс для работы подпрограммы P, и выделяем регистры R_l при l?с в качестве рабочих регистров для остальных команд основной программы Q.

Это правило изображено в следующем виде

Если соблюдено правило выделения регистров, то программа P в процессе выполнения меняет лишь регистры R₁. Rс, а данные программы Q находятся в регистрах Rс1. и не могут быть затронуты и испорчены программой P.

Вставка подпрограммы. Пусть в программе Q имеется подпрограмма P для вычисления функции f (x₁. x_n). В подпрограмме P имеются входные данные (x₁. x_n) и результат вычислений f (x₁. x_n). По определению МНР должны соблюдаться следующие требования.

* При старте P аргументы x₁. x_n обязаны находиться в регистрах R₁. R₁.

* После окончания работы подпрограммы P результат f (x₁. x_n) должен содержаться в регистре R₁.

Однако в ходе работы основной программы Q возможно следующее.

Настал момент для старта подпрограммы P, которой нужны аргументы x₁. x_n. В данный момент аргументы хранятся в каких-то регистрах Ri1. Rin, а не в регистрах R₁. R_n, как нужно. Поэтому перед применением подпрограммы P мы должны извлечь аргументы из Ri1. Rin и переслать их в регистры R₁. R_n. Для осуществления такой пересылки аргументов выполняется следующее действие.

1) Перед командами из P размещается набор команд T (i1,1). T (in, n).

2) Выполняется набор команд Z (n+1). Z(с).

После выполнения подпрограммы P результат находится в регистре R1. Однако регистр R1 нужен для последующих вычислений программы Q. Поэтому из регистра R1 результат выполнения подпрограммы P нужно пересылать для его последующего использования на хранение в некоторый рабочий регистр Ri, где i? с(P). Это можно осуществить следующим способом.

3) Выполняется команда переадресации T (1, i).

Итак, для правильной работы подпрограммы P могут потребоваться следующие действия, которые назовем вставкой подпрограммы.

1) Распределение памяти. Вычисляется число с=с(P) и выделяется память R1. Rс, достаточная для работы подпрограммы P. Задается регистр Ri, где i?с, для хранения результата работы подпрограммы.

2) Извлечение аргументов. Для этого записываются следующие команды: T (i1, 1). T (in, n) для передачи аргументов из места их хранения в регистры R1. Rn.

3) Очистка регистров. Для этого записываются следующие команды:

4) Вставка команд подпрограммы P.

5) Пересылка результата на хранение. Добавляется команда T (1, i).

В итоге в основной программе получается следующий фрагмент.

Вставку данного фрагмента в основную программу обозначаем через

2. Соединение программ

Модифицированную таким образом программу P будем обозначать

3. МНР-вычислимость частично-рекурсивных функций

3.1 Реализация подстановки на МНР

Докажем, что класс всех МНР-вычислимых функций замкнут относительно операции подстановки.

G₁ [m + 1, m + 2. m + n т + п + 1]

G_k[m + 1,m + 2. m + n т + п + k]

F[m + п + 1. m + п + k 1].

Действительно, вспомнив только что введенные обозначения для модифицированных программ, видим, что если в начальный момент в регистры R₁. Rn помещены числа x₁. х_n, а в остальных регистрах содержится число 0, то в результате выполнения первых п команд программы Н числа x₁. х_п оказываются переписанными в регистры Rm+1,…, Rm+ n не используемые ни одной из программ F, G₁. G_k.

Затем выполняется подпрограмма G₁, модифицированная таким образом, что исходные данные для нее берутся из регистров Rm+1. Rm+n, а результат, если он существует, записывается в регистр Rm+n+1. В случае завершения выполнения этой программы в регистре Rm+n+1 содержится число g₁(х₁. х_п). Затем выполняется подобным же образом модифицированная программа G₂ с той лишь разницей, что результат ее выполнения записывается в регистр Rm+n+2. Вообще, если выполнение модифицированной программы G_i-1(i=2, …, k) завершилось результативно, то выполняется модифицированная программа G_i, и, в случае ее завершения, в регистр Rm+n+i помещается число g_i(x₁, …, x_n).

Таким образом, если все значения g₁(x₁, …, x_n). g_k(x₁. х_п) определены, то они оказываются помещенными в регистры Rm+n+1. Rm+n+k. Затем выполняется программа F, модифицированная таким образом, что исходные данные для нее берутся из регистров Rm+n+1. Rm+n+k. Значит, эта модифицированная программа (F) вычисляет значение

т. е. значение h(x₁. x_n ), и, если оно определено, помещает его в регистр R₁.

Таким образом, программа Н вычисляет функцию h. Следовательно, функция h является МНР-вычислимой.

3.2 Реализация рекурсии на МНР

Докажем, что класс всех МНР-вычислимых функций замкнут относительно операции рекурсии.

G[m + 1,m + 2. m + n,t + 2,t + 3 t + 3]

При у = 0 выполняется команда с номером р, которая переписывает содержимое регистра R_t+3 в регистр R₁, а затем программа завершается. Таким образом, после выполнения программы в регистре R₁ оказывается число f 1. x_n), которое совпадает со значением h(x₁. x_n, 0). Это означает, что программа Н правильно вычисляет значение h(x₁. х_n, 0).

и так далее, пока не будет получено значение h(x₁. x_n, у).

3.3 Реализация минимизации на МНР

Докажем, что класс всех МНР-вычислимых функций замкнут относительно операции минимизации.

Тогда программа G будет выглядеть как следующее соединение нескольких программ:

с: F[m + 1,m + 2. m + n + 1 1]

Действительно, если в начальный момент в регистры R₁. R_n помещены числа x₁. х_n, то в результате выполнения первых п команд программы G эти числа окажутся записанными в регистрах Rm+1. Rm+n. Затем выполняется программа F, модифицированная таким образом, что исходные данные для нее берутся из регистров Rm+1. Rm+n, Rm+n+1. Заметим, что в регистре Rm+n+1 в этот момент содержится число 0. Таким образом, модифицированная программа F вычисляет значение f(x₁. x_n, 0) и, если оно определено, помещает его в регистр R₁.

Затем содержимое регистра R₁ сравнивается с содержимым регистра R_m+n+2, которое в процессе исполнения программы G остается равным нулю. Так проверяется выполнение условия f(x₁. х_n, 0) = 0. Если это условие выполнено, то содержимое регистра R_m+n+1, т. е. число 0, записывается в регистр R₁, и программа завершается. В этом случае в регистре R₁ действительно содержится значение g(х₁. х_п) = му[?(х₁. х_n, у) = 0].

© 2000 — 2021, ООО «Олбест» Все права защищены

Источник