Реферат: Существование универсальных вычислителей. Алгоритмические проблемы и взаимосвязь алгоритмических систем.

1 || Q*aR если QaR=P

0 || P* если a не входит в P

m_b (1||Q*aR)=QbR

U₀ (0||P*)=P

Надеемся, что читателю будет не сложно построить функциональную схему любой из этих машин.

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

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

a_i ®b_i

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

if then m_{b i} (1||Q*a_i R)o U^* o U₁

else U_о o U*o U_i+1 .

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

a_i ab_i

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

if then m_{b i} (1||Q*a_i R) o U_!

else U_о o U*o U_i+1 .

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

a_k ®b_k

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

if then m_{b k} (1||Q*a_k R)o U*o U₁

else U_о o U*o U_! .

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

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

U*(P)o U₁ o U₂ o … o U_k ,

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

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

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

Выводы :

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