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

Командам вида (3)  - qja ® qsb

Командам вида (4)  - qja a b.

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

® qo , машины U.

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

Замечание: Если а=L, т. е. командам Lqj ® bqsw надо будет сопоставлять правило qj ® qsb либо qj ® bqs  в зависимости от значения w. Все такие правила подстановки надо собрать в конце схемы, сразу перед начальным правилом.

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

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

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

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

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

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

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

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

Алфавит U : DU = DNUWN.

Обозначим

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

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

1 || Q*aR если QaR=P 0 || P*     если a не входит в P

mb (1||Q*aR)=QbR

U0 (0||P*)=P

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

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





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