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

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

Формально машина Сстроится так. Состояниям S₁, S₂, ..., S_n машины Амы ставим в соответствие состояния T₁, Т₂,…,Т_п машины С (последние будут встречаться, когда машина Сначинает операцию, считывая первый символ в двоичной последовательности длины l). Для каждого из этих Т_j определим два состояния T_j0 и Т_j1. Если машина С находится в состоянии Т_j и читает символ 0, то она движется вправо и переходит в состояние T_jo. Если она читает 1, то движется вправо и переходит в состояние Т_j1. Таким обра­зом, с помощью этих двух состояний машина запоминает, каким был первый символ двоичной последовательности. Для каждого из этих T_j0 и Т_j1 определим опять по два состояния: T_j00, T_j01 и T_j10, T_j11. Если, например, машина находится в состоянии T_j0 и читает символ 0, то она переходит в состояние T_j00 и т. д. Таким образом, c помощью этих состояний запоминается начальное состояние и два первых символа, прочитанных в процессе работы машины. Продол­жим такое построение состояний вплоть до l-1 шагов. Получившееся в итоге разнообразие состояний можно обозначить через T_{j, 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. Теперь правила операций зависят от конкретных правил машины А.

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

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

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

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

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

Новый символ a_k может быть закодирован двузначным кодом в виде последовательности y_1, y₂, …, y_s-1, y_s, где y_i=0,1. Определим два новых множества состояний, которые несколько похожи на введенное выше множество состояний Т, но соответствуют не считыванию, а записи: R_{p, y1, y2, …, ys} и L_{p, y1, y2, …, ys}. Название состояния (R или L) будет индикатором движения машины А, первое число в индексе (p) – будет показывать номер нового состояния S_p машины А, а индексы y_1, y₂, …, y_s-1, y_s - значения кода нового символе a_k.

Пусть последовательность x_1, x₂, …, x_s-1, x_s соответствует некоторому символу машины А. Допустим машина Ачитает этот символ в состоянии Sj, тогда она записывает символ, соответствующий двоичной последователь­ности y_1, y₂, …, y_s-1, y_s, переходит в состояние S_p и дви­жется, скажем, вправо. В этом случае, по определению, машина С, будучи в состоянии T_{i, x1, x2, …, xl-1} и читая символ x_l , переходитв состояние R_{i, x1, x2, …, xl-1}, записывает символ у_l и движется влево. В любом из состояний R_{p, y1, y2, …, ys} (или L_{p, y1, y2, …, ys}) машина Сзаписывает y_s, движется влево и переходит в состояние R_{p, y1, y2, …, ys-1} (или L_{p, y1, y2, …, ys-1}). Посредством этого процесса двоичная последовательность, соответствующая новому символу, записывается вместо ста­рой двоичной последовательности. При s=1 эта запись заканчивается на символе y₁. Остается только передвинуть считывающую голову на l клеток вправо или влево, в зависимости от того, находится ли машина в состоянии R или в состоянии L. Это делается с помощью множеств состояний U_i,s и V_i,s (i= 1, 2, ..., n; s= 1, 2, …, l-1). В состоянии R_ix1 машина записывает x₁, движется вправо и переходит в состояние U_i1. В каждом из состояний U машина продолжает движение вправо, не записывая ничего и переходя в состояние U со следующим по величине индек­сом, пока не будет достигнуто последнее состояние U. Таким образом, U_i,s вызывает движение вправо и состояние U_i,s+1 (s<l-1). Наконец состояние U_i,l-1 приводит после движения вправо к состоянию Т_i, завершая тем самым цикл. Аналогично, L_i,x приводит к движению влево и состоя­нию V_i,1. V_i,s дает движение влево и V_i,s+l (s< l -1), нако­нец, V_i,l-1 дает движение влево и Т_i.

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