Нормальный алгоритм Маркова
Нормальный алгоритм Маркова
- задается алфавитом и нормальной схемой подстановок, выполняемых по заранее определенной схеме;
- определяет преобразование строк.
Доказано, что класс нормальных алгоритмов Маркова и класс алгоритмов, представленных в форме машины Тьюринга, совпадают.
Тезис Маркова: любой вычислительный процесс можно преобразовать в нормальный алгоритм.
Алгоритмы Маркова
Основная операция при работе алгоритмов Маркова – это переработка слов в некотором алфавите. Эта переработка заключается в производстве некоторого количества замен определенных последовательностей символов. Эти замены совершаются в СТРОГО определенном порядке, а именно: после каждой замены алгоритм читается с самого начала, а слово анализируется с самого первого символа. В отличие от машин Тьюринга, алгоритмы Маркова выполняются без какого – либо устройства, осуществляющего движения и имеющего внутреннюю память. В данном случае мы можем оперировать только ленточными знаками. Сама лента в этом случае не разделяется на строгие ячейки, а имеет гибкую основу, что позволяет ей растягиваться и сжиматься исходя из того, увеличивается ли в слове число символов или уменьшается.