Начальная лента машины С представляет собой начальную ленту машины А, где каждый символ замещен соответствующей ему двоичной последовательностью. Если работа машины А начинается с какого-то определенного символа, то работа машины С начнется с самого левого двоичного символа соответствующей группы. Если машина А начинает работу в состоянии 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; x j=0,1; s =1,…, l - 1.
Если машина находится в одном из этих состояний (s < l -1) и читает 0 или 1, то она движется вправо и 0 или 1 делается дальнейшим индексом состояния. В тот момент, когда s становится равен l – 1, машина читает последний символ последовательности длины l. Теперь правила операций зависят от конкретных правил машины А.
Допустим, текущей инструкцией машины А была команда
Машина С уже готова к выполнению соответствующей инструкции, а значит в дальнейших состояниях должна быть закодирована информация о трех параметрах:
· о новом символе ak, который следует записать на место старого символа ai,
· о направлении дальнейшего движения машины: R или L,
· о номере нового состояния Sp.
Новый символ ak может быть закодирован двузначным кодом в виде последовательности y1, y2, …, ys-1, ys, где yi =0,1. Определим два новых множества состояний, которые несколько похожи на введенное выше множество состояний Т, но соответствуют не считыванию, а записи: Rp, y1, y2, …, ys и L p, 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, переходитв состояние R i, x1, x2, …, xl-1, записывает символ уl и движется влево. В любом из состояний Rp, y1, y2, …, ys (или L p, y1, y2, …, ys) машина С записывает ys, движется влево и переходит в состояние Rp, y1, y2, …, ys-1 (или L p, 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) Теорема
