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

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

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

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

Курсовая работа

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

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

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

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

Ургенч 2020 г



Содержание

Введение

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

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

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

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

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

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

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

4. Примеры

Заключение

Список литературы



Введение

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

Один из типов абстрактных вычислительных машин - машины с неограниченными регистрами, которые дают язык программирования более высокого уровня по сравнению с машинами Тьюринга. Машины с неограниченными регистрами пригодны только для вычисление арифметических функций, но в этой области они универсальны: всякая частично-рекурсивная функция вычислима на машине с неограниченными регистрами.

Для решения ряда однотипных задач можно использовать чисто механические вычислительные процессы. С их помощью искомые величины вычисляются последовательно из данных величин по определенным правилам. Описание таких процессов принято называть алгоритмами. Алгоритм - это строгое предписание, определяющее вычислительный процесс как последовательность шагов, которая приводит от изменяемых начальных данных к конечному результату. Это фундаментальное и неопределяемое понятие.

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



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

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

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

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

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

a) команда обнуления - Z(n) заменяет содержание Rn на 0;

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

b) команды прибавления единицы - S(n) увеличивает содержимое Rn на 1; обозначается также r_n + 1Rn или r_n:= r_n +1 (r_n присваивается r_n + 1);

c) команда переадресации - Т(m, n) заменяет содержимое Rn числом r_m, содержащимся в Rm; обозначается также r_nRn или r_n:= r_m (r_n присваивается r_m);

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

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

Машина с неограниченными регистрами (МНР) -- это абстрактная машина, более сходная с реальным компьютером по сравнению с машиной Тьюринга. Она имеет следующие составные части.

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

r1	r2	r3	…	rk	0	…

R₁ R₂ R₃ ... R_k R_k+1...

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

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

2) Программа машины -- это конечная последовательность

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

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).

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

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

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

2	3	1	5	0	…

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

2	4	1	5	0	…

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

4	4	1	5	0	…

Машина с неограниченными регистрами, как и произвольный алгоритм, работает по тактам: такт 1, такт 2,... Первый такт работы МНР с программой I₁, I₂,..., I_s -- выполнение первой команды I₁. Затем выполняются команды I₂, I₃,... Этот последовательный порядок выполнения команд продолжается до тех пор, пока не встретится команда J(m, n, q), которая может изменить естественный порядок выполнения команд.

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

1) Если в i-вом такте выполнена Is -- последняя команда программы и эта команда не является командой условного перехода, тогда следующим i+ 1 тактом должна выполняться несуществующая команда Is+1.

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

3) Если в i-вом такте выполнена Is -- последняя команда программы и эта команда является командой условного перехода J (m, n, q) при r_m ? r_n, тогда следующим i+1 тактом должна выполняться несуществующая команда I_s+1.

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

Вычисление функций на МНР. Как и в случае машин Тьюринга, мы должны указать, как машина с неограниченными регистрами вычисляет частичную функцию f (x₁,...,x_n) от n аргументов. Рассмотрим набор аргументов (x₁,...,x), и разместим число x₁ в регистре R₁, число x₂ -- в регистре R₂,..., число x_n -- в регистре R_n. Все остальные регистры заполнены нулями. Получаем начальную конфигурацию МНР. После окончания работы в регистре R₁ должно быть значение функции f (x1,...,xn). Если значение f (x1,...,xn) не определено, то МНР должна работать бесконечно.

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

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

I₁ S(1)

I₂ S(1)

В регистр R₁ перед первым тактом работы машины занесено число x, остальные регистры заполнены нулями. Машина совершит два такта работы, два раза прибавит 1 к числу x в регистре R₁ и остановится. Число x+2 -- результат вычислений, что и нужно.

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

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

I₁ J (2, 3, 5)

I₂ S (1)

I₃ S (3)

I₄ J (1, 1, 1)

x	y	0	0

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

в R₂ -- число y, остальные регистры заполнены нулями.

R₁ R₂ R₃ R₄

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

Допустим, например, что y=2. Поскольку y ? 0, то вторым тактом работы исполнится команда S(1), а третьим -- S(3). В результате к числам в регистрах R₁ и R₃ добавится число 1, и каждый из них увеличится на 1.

x+1	y	1	0

R₁ R₂ R₃ R₄

Далее 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).

2 Нулевая функция oⁿ (x₁, x₂,..., x_n).

3 Функция проектирования (x₁, x₂,..., x_n).

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

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

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

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

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

Теорема доказана.

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

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

ОПРЕДЕЛЕНИЕ 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 остановиться.

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

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

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

Пусть даны две программы P = I₁, I₂,..., I_s и Q = I?₁, I?₂,..., I?_t стандартного вида. Применим следующий прием -- соединение программ.

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

(6.1)

где команды 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.

Для предотвращения такой потери данных делаем так, что основная программа изменяет одну область регистров, а подпрограмма -- другую. Произвольная МНР программа P имеет конечное число команд. Команда обнуления Z(n) и команда прибавления единицы S(n) действуют только на один регистр Rn. Команде переадресации T(m, n) и команде условного перехода J(m, n, q) для функционирования нужны два регистра Rm и Rn. Если общее число команд обнуления и прибавления единицы равно k, а число команд переадресации и условного перехода равно l, то для работы всей программы P достаточно зарезервировать k+2l регистров. На остальные регистры программа P не действует, и их можно использовать в качестве рабочих регистров основной программы. Поэтому в дальнейшем применяем следующее правило выделения регистров подпрограммы P в программе Q.

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

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

(6.2)

Если соблюдено правило выделения регистров, то программа 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).

Пусть основная программа Q вызвала подпрограмму P и в начало зарезервированных регистров R₁,..., Rс скопированы числа x₁,..., x_n, с которыми начнет работать подпрограмма P. Однако в регистрах Rn+1,..., Rс может оставаться мусор -- произвольные числа оставшиеся от предыдущей работы Q. По правилам работы МНР в последующих регистрах Rn+1,..., R_k должны быть только одни нули. Поэтому нужно выполнить обнуление этих регистров от мусора, которое осуществляется следующим способом.

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).

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

T i1, 1

...

T (in, n)

Z (n+1)

...

Z(с)

P

T(1, i)

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

P[i1,..., in i] (6.4)



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

В дальнейшем нам придется рассматривать программы, которые содержат другие программы в качестве подпрограмм. Рассмотрим некоторые технические средства, позволяющие строить сложные программы из более простых. Для этого нам понадобится некоторая стандартизация программ. Пусть программа P состоит из команд I₁,..., I_s. Будем говорить, что программа P имеет стандартный вид, если во всякой команде условного перехода J(m,n, q) из P выполняется неравенство q ? s + 1. Очевидно, что каждая пр ограмма P может быть приведена к стандартному виду путем замены в ней всякой команды вида J(m, n, q), где q > s + 1 на J(m,n, s + 1), выполняющую точно такое ж действие, а именно, остановку выполнения программы P.

Пусть теперь P = I₁,..., I_s и Q = I₁,..., I_s ( -- программы стандартного вида. Соединен нем программ P и Q называется программа

PQ = I₁, …, I_s, I_s+1, …, I_s+t,

где I_s+1,..., I_s+t -- команды полученные из команд программы Q заменой каждой команды условного перехода J(m,n, q) на J(m,n, s + q). Очевидно, что результат выполнения программы PQ такой же, как и результат последовательного выполнения программ P и Q. Можно говорить также о соединении трех и более программ, понимая, например, программу PQR как (PQ)R.

В том случае, когда одна программа используется как подпрограмма в другой программе, важно позаботиться о том, чтобы в ходе выполнения подпрограммы не изменилось содержимое регистров, используемых основной программой. Этого нетрудно добиться следующим образом. Пусть мы собираемся использовать программу P как подпрограмму при составлении новой программы Q. Поскольку программа P конечна, в ней используется конечное число регистров, так что найдется такое наименьшее число u (обозначим его с(P)), что регистры R_? при ? > u не используются в этой программе. Тогда при составлении программы Q, использующей P в качестве своей части, т. е. подпрограммы, нужно использовать в качестве рабочих только регистры R_? при ? > u.

Если программа P предназначена для вычисления некоторой функции ?(x₁,..., x„), то, в соответствии с общими соглашениями, исходные данные записываются в регистры R₁,..., R_n, а результат -- в регистр R₁. В тоже время, при использовании программы P в качестве подпрограммы в другой программе, исходные данные для P могут быть задисаны в каких-то других регистрах R_l1,..., R_ln, а результат требуется поместить в регистр R_l. Чтобы обеспечить возможность такого использования программы P, мы можем преобразовать ее в следующую программу, являющуюся соединением трех программ:

T(l₁, 1);

……….

T(l_n, n)

Z(n +1);

………..

z(с (p));

p{T (1,z).

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

P[l₁,...,l_n l].



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

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

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

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

Теорема 5.1. Пусть n-местная частичная числовая функция h получена подстановкой n-местных функций ?, g₁,...,g_k в k-местную функцию ?, причем функции ?, g₁,...,g_k МНР-вычислимы. Тогда и функция h МНР-вычислима.

Доказательство. Пусть программы стандартного вида F, G₁,..., G_k вычисляют соответственно функции ?, g₁,...,g_k. Напишем программу Н для вычисления функции h. Пусть т=max{n,k,с(F),с(G₁),...,с(G_k)}. Тогда программа Н будет выглядеть как следующее соединение нескольких программ:

Т(1,m + 1);

……..

Т(n,m + n);

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) вычисляет значение

? (g₁(x₁, …, x_n),...,g_k(x₁...,х_п)

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

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



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

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

Теорема: Пусть (n + 1)-местная функция h получена рекурсией из n-местной функции ? и (п + 2)-местной функции g, причем функции ? и g МНР-вычислимы. Тогда и функция h МНР-вычислима.

Доказательство. Пусть программы F и G, имеющие стандартный вид, вычисляют соответственно функции ? и g. Напишем программу Н для вычисления функции h, заданной рекурсивными уравнениями h(x₁,..., x,0) ? f(x₁,..., x_n), h(x₁,..., х_п,..., x _n+1 + 1) ? g(х₁,...,x_n,x_n+1),h(x₁,..., x_n)). Пусть т = max{n + 2, с(F), с(G)}, t = m + n. Тогда программа h будет выглядеть как следующее соединение нескольких программ:

Т(1,m + 1);

……..

Т(n+1,m+n+1);

F[ l, 2,...,n t + 3]

q: J(t + 2, t + l, с);

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

S(t+1);

J(1,1,q);

с: T(t+3, 1).

Действительно, если в начальный момент в регистры R₁,..., R_n, R_n+1 помещены числа x₁,..., x_n, у, то при выполнении первых n + 1 команд программы Н эти числа записываются в регистры Rm+1, …, Rm+n, Rt+1, не используемые программами F и G. Затем выполняется программа F, модифицированная таким образом, что ее результат, если он существует, записывается в регистр R_t+3. Таким образом, в случае завершения выполнения модифицированной программы F в регистре R_t+1 оказывается записанным число f(x₁,..., x_n). При этом в регистре R_t+1 содержится число y, а в регистре R_t+2 -- число 0, так что при выполнении команды условного перехода с номером q происходит следующее.

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

При у ? 0 после команды с номером q выполняется программа G, модифицированная таким образом, что исходные данные для нее берутся из регистров R_m+1, R_m+2, …, R_m+n, R_t+2, R_t+3, а результат записывается в регистр R_t+3 Таким образом, модифицированная программа G вычисляет значение g(х₁,..., x_n, 0, h(x₁,..., x_n, 0), которое есть h(x₁,..., x_n, 1). Затем содержимое регистра R_t+2 увеличивается на единицу, и снова выполняется команда с номером q. Очевидно, что если у = 1, то программа Н завершит работу с результатом h(x₁,...,x_n, 1), в противном случае будет вычисляться значение

g{х₁,..., х_n, 1, h(x₁,..., x_n, 1) ? h(x₁,..., x_n, 2),

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

При п = 1 в роли 0-местной функции ? выступает некоторое фиксированное число а, поэтому в доказательстве теоремы в качестве F нужно взять программу, которая записывает число а в регистр R₁.



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

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

Теорема: Пусть п(х₁,...,х_п) ? мy[?(x₁...,х_п,у) = 0], причем функция ? МНР-вычислима. Тогда n-местная функция g также МНР-вычислима.

Доказательство. Пусть программа F, имеющая стандартный вид, вычисляет функцию ?. Напишем программу G для вычисления функции g. Пусть

т = max{n + 1, с (F)}.

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

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

(т. е. с -- номер первой команды в этой подпрограмме)

J(1, m+n+2, q);

S(m+n+1);

J(1, 1, с).

q: T(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].

При f(x₁,...,х_n,0) ? 0 содержимое регистра увеличивается на единицу, так что теперь оно равно 1, и с помощью модифицированной программы F вычисляется значение f(x₁,..., x_n, 1). Если это значение равно нулю, то программа G завершает работу с результатом 1; в противном случае вычисляется значение f(x₁,..., х_n, 2), и так далее, пока не будет найдено значение у такое, что для каждого z < у значение f(x 1,..., x_n, z) определено и не равно нулю, a f(x₁,...,х_n,у)= 0. Это значение у будет записано в регистр R₁, и выполнение программы завершится. Очевидно, что найденное таким образом значение у (если оно вообще существует) как раз и есть значение мy[?(x_1,...,х_п,у) = 0], т.е. значение g(х₁,...,х_п).

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

Теорема: Всякая частично-рекурсивная функция МНР- вычислима.

Доказательство. По определению, любая ЧРФ может быть получена из базисных функций о, s, (п = 1,2,...;1 ? т ? п) с помощью операций подстановки, рекурсии и минимизации. Базисные функции s, о, МНР-вычислимы. Отсюда и из теорем немедленно следует, что всякая частично-рекурсивная функция МНР- вычислима.

Справедливо и обратное утверждение.

Теорема: Всякая МНР-вычислимая функция частично-рекурсивна.

Эта теорема доказывается технически более сложно с помощью следующего рассуждения. Пусть n-местная функция ? вычисляется программой Р. Обозначим через с(х₁,..., x_n, t) содержимое регистра R₁ после t шагов работы программы Р на исходных данных x₁,..., х_т, если она не завершилась раньше, и заключительное содержимое регистра R₁, если работа программы завершилась за меньшее число шагов. Через j(x₁,..., x_n, t) обозначим номер следующей команды, после того как сделано ровно t шагов работы программы Р на исходных данных x₁,..., х_т, если она не завершилась раньше, и 0 при завершении работы программы за меньшее число шагов. Тогда очевидно

f(x₁,...,x_n) ?c(x₁,...,x_n, мt[j(x₁,...,x_n,t) = 0]).

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

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



4. Примеры

МНР-программа для функции f(x, y)=x+y:

Рассмотрим первый пример детально.

Запишем необходимые команды, для обсчета функции f(x, y)=x+y. Имеем:

1. J(1,2,5)

2. S(0)

3. S(2)

4. J(0,0,1)

Теперь покажем, как работает программа на конкретном примере. Следовательно, имеем:

f(x, y)=x+y:

f(2,3)=2+3

Начальные условия записываем в регистры R₀ и R_1. Шаг за шагом выполняем необходимые команды, пока машина не остановится.

R0	R1	R2	R3
2	3	0	0
3	3	0	0
3	3	1	0
4	3	1	0
4	3	2	0
5	3	2	0
5	3	3	0

Результат считываем из регистра R0. Следовательно, имеем, что 2+3=5 МНР-программа для функции f(x, y)=x-y:

1. J(0,1,5)

2. S(1)

3. S(2)

4. J(0,0,1)

5. Т(2,0)

Аналогично, к предыдущему примеру имеем: f(x, y)=x-y:

f(5,2)=5-2

R0	R1	R2	R3
5	2	0	0
5	3	0	0
5	3	1	0
5	4	1	0
5	4	2	0
5	5	2	0
5	5	3	0
3	5	3	0

Результат считываем из регистра R_0. Следовательно, имеем, что 5-2=3.



Заключение

Рассмотрим теперь точное определение алгоритма через машину с неограниченной количество регистров (МНР). При этом, как в качестве изучаемых объектов берем элементы из множества натуральных чисел, т.е. N = {0,1,2,...}.

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

Выше была решено несколько примеров по МНР. Показано результаты этих примеров.

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



Список литературы

1. studfile.net

2. primat.org

3. http://math.hashcode.ru/

4. Теория алгоритмов. Крупский В.Н. Москва 2009г.

5. Теория алгоритмов. Ильиных А.П. Екатеринбург 2006г.

6. Теория алгоритмов. Плиско В.Е. Москва 2009г.

7. Лекции по теории алгоритмов. Белов.Ю.А, Соколов В.А. Ярославль 2013г.

Размещено на Allbest.ru

...