Нормально вычислимые функции и принцип нормализации Маркова

Как и машины Тьюринга, нормальные алгоритмы не производят собственно вычислений: они лишь производят преобразования слов, заменяя в них одни буквы другими по предписанным им правилам. В свою очередь, мы предписываем им такие правила, результаты применения которых мы можем интерпретировать как вычисления.

Рассмотрим два примера. (с51)

(с 52)

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

Сформулируем теперь точное определение такой вычислимости функций. (с53)

Определение. Функция f, заданная на некотором множестве слов алфавита А, называется нормально вычислимой, если найдется такое расширение B данного алфавита (А В) и такой нормальный алгоритм в В, что каждое слово V (в алфавите А) из области определения функции f этот алгоритм перерабатывает в слово f (V).

В предыдущих двух примерах заданы нормально вычислимые функции, причем алгоритмы построены в том же самом алфавите т.е. В=А.

К пустому слову данный алгоритм не применим (получаем бесконечную последовательность) правило Λ→а

Λ=>a =>аа => ааа => аааа =>...

Если применить теперь алгоритм к слову 499, получим следующую последовательность слов:

499 => a499 (применена последняя формула) => 4a99 (формула из середины второго столбца) => 49а9 => 499b (дважды применена формула из конца второго столбца) => 499b (предпоследняя формула) => 49b0 => 4b00 (дважды применена предпоследняя формула первого столбца) => 500 (применена формула из середины первого столбца).

«Принцип нормализации Маркова».

Для нахождения значений функции, заданной в некотором алфавите, тогда и только тогда существует какой-нибудь алгоритм, когда функция нормально вычислима.

Сформулированный принцип, как и тезисы Тьюринга и Чёрча, не может быть строго доказан.

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

а) класс всех функций, вычислимых по Тьюрингу,

б) класс всех частично рекурсивных функций;

в) класс всех нормально вычислимых функций.