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

НА A i B еквiвалентнi вiдносно алфавiту T, якщо для всiх x(T* A(x) та B(x) одночасно визначенi або невизначенi, та у випадку визначеностi A(x)=B(x).

Відомо [7], що для кожного НА над алфавітом Т існує еквiвалентний йому вiдносно T НА в алфавіті Т ({s} з єдиним допоміжним символом s(Т. Відомо також [7], що вербальне відображення, яке кожне слово x(T* переводить в слово хх, не може бути заданим жодним НА в алфавіті Т. В той же час маємо

Приклад 1. НА, який кожне x(T* переводить в слово xх (тут #(Т):

##a(a#а## для всіх a(Т

#ab(b#a для всіх a, b(Т

#а(а для всіх a(Т

##(((

((##

) невизначене при (x1 ,...,xk)(Df .

Функцiя називається обчислюваною за Марковим, або НА-обчислюваною, якщо iснує НА, який її обчислює.

Зауважимо, що кожний НА обчислює безліч функцій натуральних аргументів та значень, але зафіксовуючи наперед арність функцій, дістаємо, що кожний НА обчислює єдину функцію заданої арності.

Приклад 2. НА для функцiї f(x, y)=x+y:

#((

Приклад 3. НА для функцiї f(x, y)=x-y:

|#|(#

#|(#|

#((

Приклад 4. НА для функцiї f(x)=x/2:

#||(|#

#|(#|

#(((

((#

:

da(add

ad(d

d(d

((d

Приклад 6. НА для функцiї f(x)=2х:

(|(|((

|(((