Приклад 1. #ab®b#a для всіх a, bÎТ

##a ® a#а## для всіх a Î Т

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

#а ® а для всіх a Î Т

## ®× e

e ® ##

НА A обчислює часткову функцiю f:N^k → N, якщо він кожне слово вигляду переводить у слово у випадку (x ₁ ,...,x_k)Î D_f та A() не визначене при (x ₁ ,...,x_k)Ï D_f.

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

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

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

# ® e

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

|#| ® #

#| ® #|

# ® e

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

#|| ® |#

#| ® #|

# ®× e

e ® #

Поиск по сайту: