Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій

МНР-програма P обчислює часткову n-арну функцiю f:Nп→N, якщо f(a1, a2, ..., aп)=b P(a1, a2, ..., aп)(b,...).

Замiсть P(a1, a2 ,...)(b,...) надалі будемо писати P(a1 , a2 ,...)b.

Функцiю f:Nп→N називають МНР-обчислюваною, якщо iснує МНР-програма, яка обчислює цю функцiю.

Кожна МНР-програма обчислює безліч функцій, заданих на N, але, зафіксовуючи наперед арність функцій (тобто кількість компонент початкових конфігурацій), отримуємо, що кожна МНР-програма обчислює єдину функцію заданої арності.

Зауважимо, що кожну функцiю, задану на N, можна трактувати як предикат, інтерпретуючи значення 1 та 0 як істиннісні значення “Т” та “F” відповідно. В цьому випадку в ролі предикату виступає його характеристична функція.

Розглянемо приклади МНР-програм для функцій та предикатів.

Приклад 1. МНР-програма для всюди невизначеної функції:

1)J(0,0,1)

Приклад 2. МНР-програма для предикату "x=y":

1)J(0,1,3)

2)J(0,0,4)

3)S(2)

4)T(2,0)

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

1)J(1,2,5)

2)S(0)

3)S(2)

4)J(0,0,1)

Приклад 4. МНР-програма для функцiї f(x)=2x:

1)T(0,1)

2)J(1,2,6)

3)S(0)

4)S(2)

5)J(0,0,2)