Cтраница 4
Будем говорить, что машина Тьюринга и нормальный алгоритм Маркова моделируют друг друга, если у них пошаговые преобразования любого слова совпадают. [46]
В качестве примера алфавитных алгоритмов можно привести нормальный алгоритм Маркова, машину Тьюринга, МНР. [47]
Тьюрингом ( машина Тьюринга), и нормальный алгоритм Маркова. [48]
После осуществления нумерации входных и выходных слов любой нормальный алгоритм может быть реализован в виде частично-рекурсивной функции. Наоборот, любой алгоритм, реализуемый с помощью частично рекурсивной функции, оказывается эквивалентным некоторому нормальному алгоритму. [49]
После осуществления нумерации входных и выходных слов любой нормальный алгоритм может быть реализован в виде частично рекурсивной функции. [50]