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

В функциональной схеме машины U могут встретиться команды следующих видов:

aq_j ®bq_s Л

aq_j ®bq_s П

aq_j ®bq_s Н

aq_j ®b!{Л,П,Н}.

Рассмотрим сначала команды машины U вида (1), т. е. запись в текущую позицию вместо символа a символа b и сдвиг влево. В соответствующем НАМ N мы будем обрабатываемый символ в слове р метить слева символом состояния т. е. D_N =D_U UQ_U U{Ñ}. Тогда команде (1) сопоставим следующую группу правил подстановки:

q_j a®q_s Ñb

{c_i q_s Ñ®q_s c_i } , c_i ЄD_U

Здесь символ Ñ “экранирует” q от следующего за ним символа в обрабатываемом слове.

Командам вида (2) сопоставим правила подстановки вида

q_j a®bq_s

Командам вида (3) - q_j a®q_s b

Командам вида (4) - q_j aab.

Самым последним в системе правил подстановки НАМ будет начальное правило

®q_o , машины U.

где q_o - начальное состояние U.

Замечание: Если а=L, т. е. командам Lq_j ®bq_s w надо будет сопоставлять правило q_j ®q_s b либо q_j ®bq_s в зависимости от значения w. Все такие правила подстановки надо собрать в конце схемы, сразу перед начальным правилом.

Обратите внимание, что если на вход N подать слово, к которому U не применим, то N будет бесконечно долго подставлять q_o в начало слова.

N применим к тем же словам, что и U.

Допустим существование слова Р, к которому U применим, а N - нет. Раз U применим, то пусть его заключительной командой является команда aq®b!H. Ей по построению N соответствует терминальное правило подстановки, которое должно выполняться, т. к. в схеме N нет двух правил с одинаковыми правыми частями..

Пришли к противоречию.

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

Теорема 4.3. Для любого НАМ N существует машина Тьюринга U такая, что

N(P)= U(P) для всех PЄD_N ^* .

Доказательство:

Алфавит U : D_U = D_N UW_N .

Обозначим

U*(Р)=*Р, т. е. МТ , ставящую символ * перед обрабатываемым символом.

U_! (P)=P осталось без изменения слова.

« 1 2 3 4 5 6 » К-во Просмотров: 225 Бесплатно скачать Реферат: Существование универсальных вычислителей. Алгоритмические проблемы и взаимосвязь алгоритмических систем. >>> Скачать <<< Меню Поиск