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

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

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

.
.

Рис. 3.1. Регистры МНР

При этом только конечное множество регистров содержит числа, отличные от нуля. Все остальные регистры заполнены нулями. Это допущение предполагает, что каждый алгоритм использует только конечный объем памяти.

В список предписаний МНР входит четыре команды: команда обнуления Z(n); команда прибавления единицы S(n); команда переадресации T(m, n) и команда условного переходам J(m, n, q). Команды обнуления, прибавления единицы и переадресации называются арифметическими.

Обозначение команды Действие, производимое МНР по данной команде
Z(n) Rn: = 0
S(n) Rn: = Rn + 1
T(m, n) Rn: = Rm
J(m, n, q) Если Rm = Rn, то перейти к вычислению команды алгоритма с номером q.

Рис. 3.2. Список предписаний МНР

Алгоритмом называется конечная непустая последовательность команд из списка предписаний МНР, начинающаяся с команды с номером 1.

Производя вычисления по данному алгоритму, МНР изменяет содержимое регистров памяти в точном соответствии с командами алгоритма. Исходное состояние памяти, то есть последовательность чисел в регистрах R1, R2, R3,…. перед началом вычислений, называется начальной конфигурацией.

Предположим, что некоторый алгоритм P состоит из последовательности команд I1, I2, . Is. МНР начинает вычисление с команды I1, затем выполняются команды I2, I3 и т. д. до тех пор, пока не встретится команда вида J(m, n, q). В этом случае МНР переходит к выполнению команды, предписанной J(m, n, q) и текущим содержанием регистров Rm и Rn.

МНР выполняет алгоритм P: I1, I2, . Is до тех пор, пока это возможно. Вычисление останавливается тогда и только тогда, когда нет следующей команды, то есть когда МНР только что выполнила команду Ik и следующая команда в вычислении есть Iv, где v > s. Это может произойти одним из способов:

I) если Ik = Is (выполнена последняя команда в P) и Ik — арифметическая команда;

В этом случае будем говорить, что вычисление остановилось после выполнения команды Ik, и заключительная конфигурации есть последовательность r1, r2, r3, . содержимого регистров на этом шаге.

Результатом применения алгоритма к некоторой начальной конфигурации будем считать число r1 из регистра R1 заключительной конфигурации.

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

Пример 3.1. Рассмотрим алгоритм P1

I1 J(1, 2, 6)
I2 S(2)
I3 S(3)
I4 J(1, 2, 6)
I5 J(1, 1, 2)
I6 T(3, 1)

Применим алгоритм к следующей начальной конфигурации:

R1 R2 R3 R4 R5 .
5 3 .

Рис. 3.3. Начальная конфигурация

Ход вычисления на МНР по алгоритму P1 с начальной конфигурацией, изображенной на рисунке 3.3, можно представить, записывая последовательно сверху вниз конфигурации машины вместе со следующей командой, к которой она переходит на данном шаге.

R1 R2 R3 R4 R5 . Следующая команда Комментарий
5 3 . I1
5 3 . I2 (так как )
5 4 . I3
5 4 1 . I4
5 4 1 . I5 (так как )
5 4 1 . I2 (так как )
5 5 1 . I3
5 5 2 . I4
5 5 2 . I6 (так как R1 = R2)
2 5 2 . I7

Рис. 3.4. Вычисление по алгоритму P1

Определение 3.1. Пусть f — функция от n неотрицательных целыхпеременных со значениями во множестве Z неотрицательных целых чисел(функция ). Функция f называется вычислимой на МНР (или МНР-вычислимой), если существует такой алгоритм P, что:

С этого момента под термином вычислимое будем подразумевать МНР-вычислимое.

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

Пример 3.2. Докажите МНР-вычислимость функции x + y.

Решение. Получим x + y, прибавляя y раз 1 к числу x. Начальной конфигурацией алгоритма служит x, y, 0, 0, 0, . . Типичной конфигурацией в процессе вычисления является

R1 R2 R3 R4 R5 .
x + k y k .

Определим алгоритм следующим образом:

I1 J(3, 2, 5)
I2 S(1)
I3 S(3)
I4 J(1, 1, 1)

Заданный алгоритм вычисляет функцию x + y.

Пример 3.3. Докажите МНР-вычислимость функции

Решение. Составим алгоритм для начальной конфигурации x, 0, 0, . . Типичной конфигурацией в процессе вычисления является:

R1 R2 R3 R4 R5 .
x k k + 1 .

Следующий алгоритм МНР — вычисляет функцию.

I1 J(1, 2, 6)
I2 S(2)
I3 J(1, 2, 6)
I4 S(3)
I5 J(1, 1, 2)
I6 T(3, 1)

Вопросы для контроля:

Дата публикования: 2015-03-26 ; Прочитано: 1522 | Нарушение авторского права страницы

studopedia.org — Студопедия.Орг — 2014-2020 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.004 с) .

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

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

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

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

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

Читайте также:  Что такое офлайн режим в айфоне

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

R0 R1 R2 R3 R4 R5
R0 R1 R2 R3 R4 R5 (*)

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

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

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

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

R0 R1 R2 R3 R4 R5 (**)

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

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

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

R0 R1 R2 R3 R4 R5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

R0 R1
x y
R0
x+y

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

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

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

Шаги САК Исполняемая команда Конфигурация МНР после исполнения команды Проверяемое условие
R0 R1 R2 R3
Z(2)
J(1,2,6) 2=0 (нет)
S(0)
S(2)
J(0,0,2) 4=4 (да) САК=2
J(1,2,6) 2=1 (нет)
S(0)
S(2)
J(0,0,2) 5=5 (да) САК=2
J(1,2,6) 2=2 (да) САК=6
Stop

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

R0 R1 R2
a b c

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

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

R0
t

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

Шаги САК Исполняемая команда Конфигурация МНР после исполнения команды Проверяемое условие
R0 R1 R2 R3
Z(3)
J(0,1,6) 5=4 (нет)
J(0,2,6) 5=4 (нет)
J(1,2,6) 4=4 (да) САК=6
S(3)
T(3,0)
Stop
R0 R1 R2
x y z

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

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

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

Как и в случае машин Тьюринга, мы должны указать, как машина с неограниченными регистрами вычисляет частичную функцию f(x1,x2, . , xn) от n аргументов. Рассмотрим набор аргументов (x1,x2, . , xn) и разместим число x1 в регистре R1 , число x2 – в регистре R2, . число xn — в регистре Rn. Все остальные регистры заполнены нулями. Получаем начальную конфигурацию МНР. После окончания работы в регистре R1 должно быть значение функции f(x1,x2, . ,xn) . Если значение f(x1,x2, . , xn) не определено, то МНР должна работать бесконечно.

Читайте также:  Как узнать свою учетную запись на компьютере

72)Вычислимость простейших функций на машинах с неограниченными ресурсами.Теорема. Простейшие функции s(x)=x+1, on(x1,x2. xn)=0, In

m(x1,x2. xn)=xm вычислимы на МНР. Доказательство. Укажем программы для вычисления данных функций. 1) Функция следования s(x) имеет программу из одной команды S(1). Действительно, если в регистре R1

занесено число x, то МНР выполнит один такт работы, сменит число x в R1 на число x+1 и остановится. 2) Аналогично программа, состоящая из одной команды Z(1), вычисляет нулевую функцию on(x1,x2. xn)=0.3) Для функции проектирования In m(x1,x2. xn)=xm применяем программу из одной команды T(m,1). МНР выполнит один такт работы, перешлет в регистр R1 число xm и остановится. Теорема доказана. Итак, все простейшие функции из определения частично рекурсивной функции вычислимы на МНР. Далее установим, что все частично рекурсивные функции вычислимы на МНР.

73)Стандартный вид программы. Сложная программа часто содержит другие программы в качестве строительных блоков — подпрограмм. Для правильного взаимодействия этих подпрограмм нужно соблюдать некоторые

правила. Определение. Пусть дана программа для МНР, состоящая из 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 остановиться. Определение .Стандартизацией программы I1 , I2 , … ,Is называется замена в данной программе всех команд J(m, n, q) где q > s+1, на команды J(m, n, s + 1). В результате стандартизации из программы P нестандартного вида получим стандартную программу P’ с тем же действием. Используя P’ вместо P, считаем, что все программы, которые мы рассматриваем, стандартны.

74) Соединение программ.Определение. Соединением программ P: I1, I2. Is и Q: I’1, I’2, . I’t называется программа из s+t команд вида I1, I2, . Is, Is+1, Is+2 , . Is+t, где команды Is+1, Is+2 , . Is+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 и т.д.

75) Вставка подпрограммы. Пусть в программе Q имеется подпрограмма P для вычисления функции f (x1,x2. xn). В подпрограмме P имеются входные данные (x1,x2. xn) и результат вычислений f (x1,x2. xn). По определению МНР должны соблюдаться следующие требования. 1. При старте P аргументы (x1,x2. xn) обязаны находиться в регистрах R1, . ,Rn..

2. После окончания работы подпрограммы P результат f (x1,x2. xn) должен содержаться в регистре R. Однако в ходе работы основной программы Q возможно следующее. Настал момент для старта подпрограммы P, которой нужны аргументы x1, x2, . xn. В данный момент аргументы хранятся в каких-то регистрах Ri1, . , Rin , а не в регистрах R1, . , Rn , как нужно.

Поэтому перед применением подпрограммы P мы должны извлечь аргументы из Ri1, . , Rin и переслать их в регистры R1, . , Rn такой пересылки аргументов выполняется следующее действие. 1) Перед командами из P размещается набор команд T(i1 ,1), . ,T(in ,n). Пусть основная программа Q вызвала подпрограмму P и в начало зарезервированных регистров R1, . , Rn скопированы числа x1, x2, . xn, с которыми начнет работать подпрограмма P. Однако в регистрах Rn+1, . ,

R может оставаться «мусор» — произвольные числа, оставшиеся от предыдущей работы Q. По правилам работы МНР в последующих регистрах Rn+1, . , Rk должны быть только одни нули. Поэтому нужно выполнить обнуление этих регистров от мусора, которое осуществляется следующим способом. 2) Выполняется набор команд Z(n+1), . , Z().В итоге в основной программе получается следующий фрагмент T(i1 ,1) . T(in ,n) Z(n+1) . Z() PT(1,i) Вставку данного фрагмента в основную программу обозначаем

через P[i1, . , in i].

76) Вычислимость частично рекурсивных функций на МНР.Если функция f вычислима на некотороймашине с неограниченными регистрами, тоговорим кратко «Функция f МНР вычислима».В предыдущей лекции установлена МНРвычислимость простейших функций. Теперьпроверим, что применение операторовсуперпозиции, примитивной рекурсии иминимизации к МНР вычислимым функциямвырабатывает МНР вычислимые функции. Врезультате получим основной результат -все частично рекурсивные функции вычислимы

77) Оператор суперпозиции. Теорема 1. Пусть функция f получена из

функций h, g1, g2, … , gm с помощью оператора суперпозиции. Если функции h, g1, g2, … , gm МНР вычислимы, то и функция f также МНР вычислима. Доказательство. По условию функции h, g1, g2, … , gm МНР вычислимы. Пусть H , G1, G2, … , Gm- программы, вычисляющие эти функции.

Читайте также:  Как вытащить фото из ватсапа

78) Оператор примитивной рекурсии. Теорема 2. Пусть функция f получена с помощью операторапримитивной рекурсии из функций g и h. Если функции g и hМНР вычислимы, то и функция f также МНР вычислима.

Доказательство. По условию функции g и h МНР вычислимы. Пусть G и H программы, вычисляющие эти функции. Выразим кратко процесс вычисления функции f = f(x1, x2, . , xn, y). Сравниваем y с числом 0. Если равенство верно, то вычисляем f(x1, x2, . , xn, 0) = g(x1, x2, . , xn)

и останавливаемся. В противном случае несколько раз применяем программу H для последовательного вычисления чисел f(x1, x2, . , xn, k) при k=0, 1, . y.

79)Оператор минимизации. Алгоритм вычислений.► Теорема 3. Пусть функция f получена из функции g с помощью оператора минимизации. Если функция g является МНР вычислимой, то и функция f также МНР

вычислима. Доказательство. Построим программу, вычисляющую функцию f. Пусть G – программа, вычисляющая функцию g. Будем считать, что программа G приведена к стандартному виду. Искомая программа для функции f будет проверять одно за другим следующие равенства: g(x1,x2. xn,0)=0,

g(x1,x2. xn,y)=0, стремясь найти наименьшее k с условием

80) Программа вычисления.T(1,p+1)

Ip G[p+1, p+2, . , p+n+11]

IqT(p+n+1, 1) При этом команда Ip является первой командой

подпрограммы G[p+1, p+2, . , p+n+11].

Работа программы Пусть p=max(n+1, p(G)). Распределимпамять: Регистры R1, . , Rp предназначены дляработы подпрограммы G.В регистрах Rp+1 , . , Rp+n постояннохранятся аргументы x1, . , xn.В регистр Rp+n+1 будет записыватьсячисло k.В итоге получим искомое число k или машина будет работать бесконечно, что означает, что функция f(x1, x2, . xn) не существует. Теорема доказана.

81) Нормальные алгорифмы. • Третий вариант формализации понятия алгоритма предложен российским мaтематикомА.А.Марковым.• В этом определении считается, что алгоритмический процесс – это процесс переработки слов некоторого алфавита. Алфавит нормальногоалгорифма A — это некоторая конечная совокупность символов A = . Элементы из A мы будем называть буквами. Из букв алфавита A составляются слова —

конструктивные объекты, которые поступают на вход и перерабатываются в

алгорифме A. При этом говорят, что A — алгорифм в алфавите A.Схема нормального алгорифмаРассмотрим две буквы и , которые не входят в алфавит A. Формулой подстановки назовем выражение u  v или выражение u  v, где u и v — произвольные слова в алфавите A. Формула без точки называется простой формулой, а формула с точкой называется заключительной формулой. В обоих случаях формула имеет левую часть u и правую часть v, которые должны быть словами в алфавите A. Знаки  и  могут быть любыми буквами вне алфавита A. Мы могли вместо них

использовать, например, греческие буквы  и .

82) Алгоритм сложения натуральных чисел. Построим нормальныйалгорифм, вычисляющий сумму двух натуральных чисел x и y. Для этого рассмотрим алфавит из трех символов A=<0,|,+ >. Число n N изображаем словом 0||. | в алфавите A. В этом слове n палочек, перед которыми

поставлен символ 0. Искомый нормальный алгорифм A имеет схему из одной

заключительной формулы подстановки u1  v1, где u1 = +0 — слово из

двух букв, а v1 =  — пустое слово. Тем самым схема алгорифма имеет вид

+0 Если нужно вычислить сумму x+y, то подаем на вход алгорифма A ее

изображение, т.е. словоP=0||. |+0||. | Алгоритм A удалит из P подслово +0 и в один шаг переработает входное слово P в выходное слово Q. При этом

83) Принцип нормализации Маркова.Сделаем несколько предварительных замечаний. Не все вербальные алгорифмы являются нормальными алгорифмами,такткак вербальные алгорифмы реализуют произвольные преобразования слов, а нормальные алгорифмы ограничены

преобразованиями слов по заданной схеме. Поэтому определение алгоритма по Маркову не будет утверждать о совпадении класса нормальныхалгорифмов и класса вербальных алгорифмов, а будет иметь другую формулировку. Рассмотрим эту формулировку. Пусть задан алфавит A. Добавим к алфавиту A новые буквы. Получим алфавит A1 с условием AA1. Алфавит A1 называется расширением алфавита A. Нормальныйалгорифм в каком-либо расширении A1 алфавита A называется нормальным алгорифмом над алфавитом A. А.А.Марков предложил следующий тезис. Принцип нормализации. Пусть задан произвольный вербальный алгорифм A в алфавите A. Тогда существует расширение A1 алфавита A и нормальныйалгорифм A1 в алфавите A1 с условием: произвольное слово P в алфавите A

перерабатывается нормальнымалгорифмом A1 в тот же самый результат, в который слово P перерабатывается исходным вербальным алгорифмом A.Поэтому принцип нормализации можно рассматривать как способ обозрения всевозможных действий в вербальных алгоритмах. Поскольку эти действия строго заданы, то мы имеем третий вариант определения алгоритма. В результате принятия принципа нормализации мы получили инструмент для доказательства неосуществимости задачи нахождения определенного алгоритма. Доказано, что данная формулировка понятия алгоритма (принцип

нормализации) эквивалентна другим формулировкам понятия алгоритма: тезису Черча, использующему частично рекурсивные функции, и тезису Тьюринга, использующему понятие вычислительной машины. Поэтому еще раз подкрепляется уверенность в том, что мы нашли и выразили в трех формах фундаментальное понятие математики, логики и информатики — понятие алгоритма. При этом частичная рекурсивность, машина Тьюринга, МНР и нормальныйалгорифм — лишь различные формы выражения этого самостоятельного понятия.

Ссылка на основную публикацию
Куосера пишет неоригинальный картридж
Современные принтеры японской компании Kyocera, которые были разработаны после 2013 года оснащены специальным механизмом. Он определяет количество тонера в картридже...
Колода из 36 карт состав
«В» = «J» — walet, Jopek [ва́лет, йо́пэк] «Д» = «Q» — dama [да́ма] «К» = «K» — król [круль]...
Компьютер не видит микрофон wo mic
Программа wo mic разработана для использования на самых популярных операционных системах для настольных компьютеров. Авторская идея состоит в том, чтобы...
Листы для морского боя распечатать
Игра “морской бой” остаётся популярной во все времени. Для того, чтобы играть в Морской бой необходимы две карточки, на которых...
Adblock detector