МНР-вычислимые функции

Пусть имеется неограниченное количество регистров . В каждом регистре содержится целое число :

			…	…
			…	…

Количество регистров бесконечно, .

В качестве аксиом принимается набор допустимых операций:

– – обнуление ();

– – прибавление единицы (), содержимое увеличивается на единицу и записывается обратно.

– – операция переадресации, содержимое регистра заносится в регистр ;

– – условный переход: если , то перейти на команду , если иначе, то выполнить следующую команду.

Программа – это последовательность команд, а именно, , , , .

Пример:

X

;

;

;

;

.

Проверим потактно результаты применения команд:

x	x
x	x
x	x+1			…
x	x+1			…
x	x+2			…
x	x+2			…
x	x+3			…
x	x+3			…

:

:

:

:

:

:

:

:

После окончания работы программы результат находится во втором регистре.

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

Пример:

x

y

x

y

…

;

;

;

;

;

;

.

Пусть имеется множество , NxN – прямое (или декартово) произведение.

Если и , то , , .

Функцией называется однозначное отображение , или

,

где .

Область определения – это подмножество , для которого определено отображение : если , то функция называется частично определенной; если , то функция называется тотальной.

Функция называется частично вычислимой, если существует МНР-программа для её вычисления в области определения.

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

Функция называется вычислимой если:

– существует предикат, принимающий значение «истинно» в области определения и «ложно» вне её;

– функция является частично вычислимой.

Характеристическая функция предиката

Рассмотрим предикат . Его характеристическая функция – это такая функция , которая принимает значение 1, если , и 0, если .

Предикат называется разрешимым, если его характеристическая функция вычислима.

Дата добавления: 2015-06-04