Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата

Схема НАМ N состоит из правил либо вида a®b, либо aab, где
a,b Є (DUW)*.

Каждому правилу вида

ai®bi

сопоставим машину Ui c функциональной схемой вида

if  then mbi(1||Q*aiR)o U*o  U1

else Uоo U*o Ui+1 .

Каждому терминальному правилу вида

aiabi

сопоставим машину Ui c функциональной схемой вида

if then mbi(1||Q*aiR) o U!

else Uоo U*o Ui+1 .

Последнему правилу подстановки в схеме НАМ N вида

ak®bk

сопоставим машину Uk с функциональной схемой

if  then mbk(1||Q*akR)o U*o U1

else Uоo U*o U! .

В части else появление машины U! связано с тем, что по определению НАМ завершается, если не применимо ни одно из правил подстановки.

Функциональная схема искомой машины U будет иметь вид

U*(P)o U1o U2o … o Uk ,

где k - число правил подстановки в схеме НАМ N.

Доказательство теоремы 4.3 закончено.

Из теорем 4.2 и 4.3 следует, что если какая-то алгоритмическая проблема разрешима в одной алгоритмической системе, то она автоматически разрешима и в другой. Если предположить, что какая-то алгоритмическая проблема неразрешимая в одной алгоритмической системе, но разрешима в другой, то придём к противоречию. Действительно, согласно теоремам 4.2 и 4.3 если эта проблема разрешима хотя бы в одной системе, то она разрешима и в другой.

Выводы :

Для любой алгоритмической системы существует универсальный исполнитель, который есть интерпретатор множества действий заданной алгоритмической системы.;

В силу тезиса Тьюринга, любой алгоритм реализуем  в  терминах действий последовательной, параллельной композиций, выбора  и цикла и базового набора действий;

Рекомендуем скачать другие рефераты по теме: сочинения по русскому языку, контрольные работы по алгебре.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата