Нормальные алгоритмы Маркова

а любые последовательности букв — словами. Пустое слово обозначается Λ.
Если

А и B — два алфавита, причем А  B, то алфавит В называется расширением алфавита А.
Определение. Марковской подстановкой называется операция над словами, задаваемая с помощью упорядоченной пары слов (Р, Q), состоящая в следующем: в заданном слове R находят первое вхождение слова Р (если таковое имеется) и, не изменяя остальных частей слова R, заменяют в нем это вхождение словом Q. Полученное слово называется результатом применения марковской подстановки (Р, Q) к слову R.

Q), (Р, Λ), (Λ,Λ).
Для обозначения марковской подстановки (Р, Q) используется

запись Р —> Q. Она называется формулой подстановки (Р, Q). Для обозначения заключительных подстановок будем использовать запись Р —>. Q

перерабатывает слово V в слово W.
Последовательность Vi, будем записывать следующим

образом:
V0 => V1 => V2 => ... => Vm-1 => Vm,
где V0 = V и Vm = W

Упорядоченный конечный список формул подстановок в алфавите А называется схемой нормального алгоритма в А.

тогда и только тогда существует какой-нибудь алгоритм, когда функция нормально

вычислима.

Следующие классы функций (заданных на натуральных числах и принимающих натуральные значения) совпадают:
а) класс всех функций, вычислимых по Тьюрингу,
б) класс всех частично рекурсивных функций;
в) класс всех нормально вычислимых функций.