13508-1 (Существование универсальных вычислителей. Алгоритмические проблемы и взаимосвязь алгоритмических систем.), страница 2

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

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

q_jabq_s

Командам вида (3) - q_ja q_sb

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

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

q_o , машины U.

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

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

Обратите внимание, что если на вход 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_NUW_N.

Обозначим

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

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

(1||Q*R)=QR

U₀ (0||P*)=P

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

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

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

_ii

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

if then _i(1||Q*_iR) U^* U₁

else U_о U* U_i+1 .

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

_ii

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

if then _i(1||Q*_iR) U_!

else U_о U* U_i+1 .

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

_kk

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

if then _k(1||Q*_kR) U* U₁

else U_о U* U_! .

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

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

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

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

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

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

Выводы :

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

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

Проблема самоприменимости алгоритмической системы алгоритмически не разрешима;

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

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

Вопросы :

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

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

В чем проблема линеаризации Ф.с. для МТ?

Что такое универсальный исполнитель:
- он может исполнять заданный А в любой А.с.?
- он может исполнять любой А, выразимый в данной А.с.?

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

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

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

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

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

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

Если F_a (*P), то M(1||Q*aR) U^* U₁ иначе U₀ U^* U_i+1?

Список литературы

Для подготовки данной работы были использованы материалы с сайта http://www.ergeal.ru/