Реферат: Алгоритми Маркова

0|®1

|®0|

Мал.1.2 Схема НАМ для обчислення U3((n) 1) =(n) 10.

Складність цього НАМ буде n+ [log10n], що істотно менше за складність для Машини Тюрінга, що обчислює цю функцію, яка дорівнювала n2+ [log10n(log10n+1)].

Реалізацію функції U4 порівняння двох цілих чисел залишаємо читачу як вправа.

Зауваження: початкове слово треба задати у формі *

Для нормальних алгоритмів Маркова справедлива теза, аналогічна тезі Тюрінга.

Теза Маркова: Для будь-якої інтуїтивно обчислюваної функції існує алгоритм, що її обчислює.

Список літератури

1. Джон Хопкрофт, Раджів Мотані, Джеффрі Ульман РОЗДІЛ 8. Введення в теорію машин Тюрінга // Введення в теорію автоматів, мов і обчислень. – М., 2002. – С528.