Реферат: Нормальные Алгоритмы Маркова Построение алгоритмов из алгоритмов

Но в любом случае сложность НАМ для U₁ (n) больше сложности Машины Тьюринга для этой же функции, которая равнялась k+1.

Обратите внимание, что у НАМ порядок следования правил подстановки в схеме алгоритма существенно влияет на результат, в то время как для МТ он не существеннен.

Построим НАМ для примера 2 из лекции 2:

построить алгоритм для вычисления

U₂ ((n)₁ )=(n-1)₁

Итак, S={|}; W=S; V=Æ, т.е. пусто.

| a

Cложность этого алгоритма равна 1, в то время как сложность алгоритма для Машины Тьюринга равнялась n.

Теперь построим НАМ для примера 3 из лекции 2:

построить алгоритм для вычисления

U₃ ((n)₁ )=(n)₁₀

S={|}; W={0,1,2,3,4,5,6,7,8,9}; V=Æ

Схема этого алгоритма приведена на рисунке 3.2.

1|®2 2|®3 3|®4 4|®5 5|®6 6|®7 7|®8 8|®9 9|®|0 |0®10 0|®1 |®0|

Рис. 3.2. Схема НАМ для вычисления U₃ ((n)₁ )=(n)_10.

Сложность этого НАМ будет n+[log₁₀ n], что существенно меньше сложности для Машины Тьюринга, вычисляющей эту функцию, которая равнялась n² +[log₁₀ n(log₁₀ n+1)].

Реализацию функции U₄ сравнения двух целых чисел оставляем читателю в качестве упражнения.

Замечание: исходное слово надо задать в форме *