Формальная схема построения

Начальная лента машины Спредставляет собой начальную ленту машины А, где каждый символ замещен соответствующей ему двоичной последовательностью. Если работа машины Аначинается с какого-то определенного символа, то работа машины Сначнется с самого левого двоичного символа соответствующей группы. Если машина Аначинает работу в состоянии Sj, то Сначнет работу в со­стоянии Tj.

Формально машина Сстроится так. Состояниям S1, S2, ..., Sn машины Амы ставим в соответствие состояния T1, Т2,…,Тп машины С (последние будут встречаться, когда машина Сначинает операцию, считывая первый символ в двоичной последовательности длины l). Для каждого из этих Тj определим два состояния Tj0 и Тj1. Если машина С находится в состоянии Тj и читает символ 0, то она движется вправо и переходит в состояние Tjo. Если она читает 1, то движется вправо и переходит в состояние Тj1. Таким обра­зом, с помощью этих двух состояний машина запоминает, каким был первый символ двоичной последовательности. Для каждого из этих Tj0 и Тj1 определим опять по два состояния: Tj00, Tj01 и Tj10, Tj11. Если, например, машина находится в состоянии Tj0 и читает символ 0, то она переходит в состояние Tj00 и т. д. Таким образом, c помощью этих состояний запоминается начальное состояние и два первых символа, прочитанных в процессе работы машины. Продол­жим такое построение состояний вплоть до l-1 шагов. Получившееся в итоге разнообразие состояний можно обозначить через Tj, x1, x2, …, xs, где j=1,2,…,n; xj=0,1; s=1,…, l - 1.

Если машина находится в одном из этих состояний (s < l-1) и читает 0 или 1, то она движется вправо и 0 или 1 делается дальнейшим индексом состояния. В тот момент, когда s становится равен l – 1, машина читает последний символ последовательности длины l. Теперь правила операций зависят от конкретных правил машины А.

Допустим, текущей инструкцией машины А была команда

Формальная схема построения - student2.ru

Машина С уже готова к выполнению соответствующей инструкции, а значит в дальнейших состояниях должна быть закодирована информация о трех параметрах:

· о новом символе ak, который следует записать на место старого символа ai,

· о направлении дальнейшего движения машины: R или L,

· о номере нового состояния Sp.

Новый символ ak может быть закодирован двузначным кодом в виде последовательности y1, y2, …, ys-1, ys, где yi=0,1. Определим два новых множества состояний, которые несколько похожи на введенное выше множество состояний Т, но соответствуют не считыванию, а записи: Rp, y1, y2, …, ys и Lp, y1, y2, …, ys. Название состояния (R или L) будет индикатором движения машины А, первое число в индексе (p) – будет показывать номер нового состояния Sp машины А, а индексы y1, y2, …, ys-1, ys - значения кода нового символе ak.

Пусть последовательность x1, x2, …, xs-1, xs соответствует некоторому символу машины А. Допустим машина Ачитает этот символ в состоянии Sj, тогда она записывает символ, соответствующий двоичной последователь­ности y1, y2, …, ys-1, ys, переходит в состояние Sp и дви­жется, скажем, вправо. В этом случае, по определению, машина С, будучи в состоянии Ti, x1, x2, …, xl-1 и читая символ xl , переходитв состояние Ri, x1, x2, …, xl-1, записывает символ уl и движется влево. В любом из состояний Rp, y1, y2, …, ys (или Lp, y1, y2, …, ys) машина Сзаписывает ys, движется влево и переходит в состояние Rp, y1, y2, …, ys-1 (или Lp, y1, y2, …, ys-1). Посредством этого процесса двоичная последовательность, соответствующая новому символу, записывается вместо ста­рой двоичной последовательности. При s=1 эта запись заканчивается на символе y1. Остается только передвинуть считывающую голову на l клеток вправо или влево, в зависимости от того, находится ли машина в состоянии R или в состоянии L. Это делается с помощью множеств состояний Ui,s и Vi,s (i= 1, 2, ..., n; s= 1, 2, …, l-1). В состоянии Rix1 машина записывает x1, движется вправо и переходит в состояние Ui1. В каждом из состояний U машина продолжает движение вправо, не записывая ничего и переходя в состояние U со следующим по величине индек­сом, пока не будет достигнуто последнее состояние U. Таким образом, Ui,s вызывает движение вправо и состояние Ui,s+1 (s<l-1). Наконец состояние Ui,l-1 приводит после движения вправо к состоянию Тi, завершая тем самым цикл. Аналогично, Li,x приводит к движению влево и состоя­нию Vi,1. Vi,s дает движение влево и Vi,s+l (s< l -1), нако­нец, Vi,l-1 дает движение влево и Тi.

Т.1.5.(1) Теорема

Наши рекомендации