Информатика -продвинутый курс
НОРМАЛЬНЫЕ АЛГОРИТМЫ МАРКОВА - часть 5
II. Объединение алгоритмов.
Объединением алгоритмов А и В в одном и том же алфавите называется алгоритм С в том же алфавите, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В, в записанные рядом слова А(р) и
В(р).
III. Разветвление алгоритмов. Разветвление алгоритмов представляет собой композицию D трех алгоритмов А, В и
С, причем область определения алгоритма D является пересечением областей определения всех трех алгоритмов А, В и С, а для любого слова р из этого пересечения D(p) = А(р),
если С(р) = е, D(p)
= B(p), если С(р) = е, где е - пустая строка.
IV. Итерация алгоритмов. Итерация (повторение) представляет собой такую композицию С двух алгоритмов А и В, что для любого входного слова р соответствующее слово С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.
Нормальные алгоритмы Маркова являются не только средством теоретических построений, но и основой специализированного языка программирования, применяемого как язык символьных преобразований при разработке систем искусственного интеллекта. Это один из немногих языков, разработанных в России и получивших известность во всем мире.
Существует строгое доказательство того, что по возможностям преобразования нормальные алгоритмы Маркова эквивалентны машинам Тьюринга.
