Словарь информационных технологий

математическое построение, предназначенное для уточнения понятия алгоритм. Нормальный алгоритм Маркова: - задается алфавитом и нормальной схемой подстановок, выполняемых по заранее определенной схеме; - определяет преобразование строк. Доказано, что класс нормальных алгоритмов Маркова и класс алгоритмов, представленных в форме машины Тьюринга, совпадают.