МНР - это машина с натуральнозначными регистрами.
Регистры имеют свои номера R0,R1,R2...
Если мы имеем Rn, то содержимое этого регистра обозначаем 'Rn
Если, мы имеем содержание, то 'R0,'R1,'R2...называется конфигурацией МНР.
МНР может изменить содержимое регистров согласно выполняемой ею командой, конечный список команд образует программу МНР. Команды программы нумеруются начиная с 1 (единицы), номер команды в программе называется адресом команды.
Z(n) 'Rn:=0
2) Увеличивает содержимое n-ого регистра на 1.
3) Копирование содержимого регистра
T(m,n) 'Rn: = 'Rm
Содержание регистра m, остается неизменным.
4) Команда условного перехода
J(m,n.p) 'Rm: = 'Rn до p
Результат выполнения МНР программы считывается с регистра R0 !!!
Функция называется МНР вычисляемой, если существует программа МНР, которая вычисляет эту функцию. Каждая МНР программа вычисляет одну функцию заданной арности.
Команды типов 1-3 называют арифметическими. После выполнения арифметической команды МНР должна выполнять следующую по списку команду программы. Выполнение одной команды МНР назовем шагом МНР.
Заметим, что формальными моделями алгоритмов являются именно МНР-программы, понятие МНР используется для описания функционирования МНР-программ. Выполнение программы МНР начинает, находясь в некоторой начальной конфигурации, из выполнения 1-и по списку команды. Следующая для выполнения команда программы определяется так, как описано выше. Выполнение программы завершается (программа останавливается), если следующая для выполнения команда отсутствует (то есть номер следующей команды превышает номер последней команды программы).
Конфигурация МНР в момент завершения выполнения программы называется финальной, она определяет результат работы МНР-программы над данной начальной конфигурацией.
Если МНР-программа P при работе над начальной конфигурацией (a0, a1 ...) никогда не останавливается, этот факт помечаем P(a0, a1 ...)↑, если же когда-либо остановится, этот факт помечаем P(a0, a1...)↓. Если МНР-программа P при работе над начальной конфигурацией (a0, a1 ...) останавливается с финальной конфигурацией (b0, b1 ...), этот факт будем помечать так: P(a0, a1, ...)↓(b0, b1, ...).
МНР-программы как модели алгоритмов являются финитными объектами, потому ограничимся рассмотрением конечных конфигураций. Конфигурацию вида (a0, a1, ..., aп , 0, 0, ...), в которой ’Rm= 0 для всех m>n, назовем конечной. Такую конфигурацию помечаем (a0, a1 ..., an ). Понятно, что если МНР-программа P начинает работу над конечной начальной конфигурацией, то в процессе выполнения P МНР будет находиться только в конечных конфигурациях.
МНР-программы P и Q назовем эквивалентными, если при работе над одинаковыми начальными конфигурациями они или обе останавливаются с одинаковыми финальными конфигурациями, или обе не останавливаются.
МНР-программа P вычисляет частичную n-арну функцию f:Nп>N, если f(a1, a2, ..., aп)=b ⇔ P(a1, a2, ..., aп)↓(b,...).
Вместо P(a1, a2 ,...)↓(b,...) дальше будем писать P(a1 , a2 ,...)↓b.
Заметим, что каждую функцию, заданную на N, можно трактовать как предикат, интерпретируя значение 1 и 0 как истинностные значения "Т” и "F” соответственно. В этом случае в роли предиката выступает его характеристическая функция.
