Subject: Re: Детерминированность в РЕФАЛ
From: A.A.Vladimirov (vladimi@mech.math.msu.su)
Date: Mon Mar 29 2004 - 17:06:23 MSD
> Добрый всем день!
>
> На сколько я помню из институтского курса порядок просмотра
> правил входит в определение Нормальных алгоритмов Маркова (и,
> кстати, Машины Тьюринга тоже). Именно порядок просмотра правил
> в большинстве случаев обеспечивает конечность алгоритма...
Возможно, в разных институтах рассказывают про разные машины
Тьюринга? Вроде бы, шаг машины определяется парой "буква в поле
зрения + описывающая состояние машины буква внешнего алфавита",
причём внутри текста программы такие пары не повторяются (чего и
добивался Дмитрий Подкорытов). А вот для нормальных алгориФмов
(именно через "ф"!) порядок продукций абсолютно критичен.
Поэтому я и привёл в качестве примера соотношение "Тьюринг vs
Марков", и считаю, что сущность проблемы примерно в этом и
состоит.
С уважением,
Антон Владимиров
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:25:00 MSD