Существование универсальных вычислителей

 

U*(Р)=*Р, т. Е. МТ , ставящую  знак * перед обрабатываемым эмблемой.

 

U!(P)=P осталось без конфигурации  слова.

 

 

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

 

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

 

 

mb (1||Q*aR)=QbR

 

U0 (0||P*)=P

 

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

 

Схема НАМ 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 если эта неувязка разрешима  хотя бы в одной системе, то она  разрешима и в другой.

 

Выводы :

 

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

 

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

 

неувязка самоприменимости алгоритмической системы алгоритмически не разрешима;

 

Если алгоритмическая  неувязка не разрешима, то она не разрешима  в хоть какой другой эквивалентной  алгоритмической системы;

 

Алгоритмические системы  МТ и НАМ эквивалентны.

 

Вопросы :

 

Что такое интерпретация?

 

Что такое кодирование?

 

В чем неувязка линеаризации Ф.С. Для МТ?

 

Что такое универсальный  исполнитель:

- он может исполнять  заданный А в хоть какой  А.С.?

- он может исполнять  хоть какой А, выразимый в  данной А.С.?

 

Как решается неувязка произвольности алфавита в УМТ?

 

Что такое А.П.?

 

Самоприменимость - что это  такое?

 

А.П. Самоприменимости разрешима?

 

В МТ А не закончен если нет  применимого правила, в  НАМ  в  этом случае А - закончен. Как это  несоответствие решается  при подтверждении  сводимости МТ к НАМ и напротив?

 

Что значит запись:

 

 Если Fa (*P), то M(1||Q*aR)o U*o U1  по другому U0o U*o Ui+1?