гл. V. АЛГОРИТМЫ и МАШИНЫ ТЫОРИНГА

§ 12. МАШИНЫ ТЫОРИНГА

Отметим следу10И];ее очевидное положение: если иро- грамма машины содержит команду qiL, то

1дД gOl

Аналогично, если программа машины содержит коман- ду дД qiR, то

дД . . . 10 1 1 . . . IgO.

Ниже указывается серия машин Тьюринга, нреобра-i зуюш;их машинные слова одного заданного вида в машин-, ные слова другого заданного вида. Программы машин! пишутся столбцами. Для контроля против некоторых команд указываются те машинные слова, в которые перехо-i дит первоначальное заданное машинное слово после вы- полнения всех предыдуш;их команд, включая в их число: и стояш;ую слева команду.Выписанные нин-ге программы отнюдь не самые короткие, но в каком-то смысле естественные.

A) Перенос нуля: gOOlO И ggOlOO. Имеем: дО -> qR OggOlO

gO -> ggl

ggl -> qR Oll-ggO ggO -> qjj

qd ~> q,0 Ol-gOO gO -> goL

gel -> q,L ge01•"00 gsO -> goO goOl-ОО.

Б-) Л e в ы Й сдвиг: OlgjO => goOlO.

Имеем; gO ggL

gal gaL gOl-O gaO goO goOlO.

Б+) П p a в Ы Й сдвиг: giOTO И OlgoO. Програмлха этой машины получается из предыдуш;ей програмлш заменой символа L символом i?.

B) Транспозиция: OTgOlO И 01%01-""0. Сначала переводим слово OlgiOr-О в слово 01gl00.

При г/ > О это достигается следуюш;ей очевидной программой:

Б+ : 0101"дз0 дзО -> qiL qd -qfi gsO qaL

gel qoL 0Гдв01У-100 geO qA 01=g7l00.

Чтобы получить слово Olg? 1"00 и при у = О, добавляем команду

дО-дтО Oiqdm {у > 0).

Теперь из подслова перебрасываем один символ 1 п промежуток между двумя последними нулями. Очевидно, это достигается следуюш;ей программой:

д,1 -> qsL OligellOO gel -> двО двО gioi?

giol qioR Ol--iOlgioOO gioO gill

gial gisO 01-Ю1У-1д1з010 gisO -> quL

qui->quL Ol-guOl-OlO

guO gisl Ol-igislOlO.

Мы достигли своей цели, но в предположении а; ]> О, У>0.

Чтобы тот же результат получился и прп у - К), добавляем к записанной программе еш;е приказы

дтО giel giel QnL

gnl gi50 01-3gi5l010 (ж > 0, г/ > 0).

Теперь «зацпкливаею программу приказами

giol g7l . giO дтО Ol-igTlOlO.

Если X - 1 > О, то, как легко видеть, слово 01•-lg7l010 переработается в слово 01*--g7l0110. Если а; - 2 > О, то процесс дальнейшей переработки даст слово М--ЭдДуоИЮ и т. д. Через х «циклов» получим слово

Og7l01"0, которое после выполнения приказа дЛ -5- gsL (если г/ > 0) или приказов g0 -> gii и т. д. (если I У = 0) перейдет в слово g-sOlOl или в слово qnOWb. Чтобы получить требуемое слово, далее присоединяем 5 приказы

gsO gisR qui -> gisR

gisO-geO 01>01«0 (г/> 0) gijO -> guR

gigl goO OlOlO (y = 0).

Г) Удвоение: gi01=0+3 s) goOlOlOO. Полагаем: gO -> giR

gi gR 01"g20"3.

Полученное слово 01*20+ представляем в виде, 01g200°00°0+i и далее пишем программу, для которой 1 при X - iQ

Полагаем: gO gL 01-("l)gзl0101"0 ggl giO g40 gR gsO gel

gel gsi? 0-(+l)01+lgв010

goO g-iR

дЛ -> gri?

g70 -> ggl

gel ggb

gsO ggL

gel gL 01--*--(i)g901+i01i.

Теперь приказом

geO gaO 01•-(+l)g201+Юl+l

зацикливаем программу п машина, пользуясь фиксированными выше приказами, начинает перерабатывать указанное слово. Еслп X - (i -Ь 1) > О, то после цикла работы машины ползится слово 01-<2)201+-01+2 и т. д. Заметим, что в течение каждого цикла машина вводит в игру новую ячейку лентыснрава, беря ее из того запаса пустых ячеек 0*+ который нами был заранее написан в

исходном слове. Если этого не было Бы сделано, то машина пристраивала бы сама по одной новой пустой ячейке в каждом цикле работы.

Итак, имея начальное состояние gi01"0+3 указанную выше программу, машина через х циклов работы придет в состояние OgaOlOlO. Приказ q-J) -> gL переведет машину в состояние ggOOlOlO. Производя теперь перенос нуля А, затем правый сдвиг Б"*", еш;е раз перенос нуля А и, наконец, левый сдвиг Б", получим требуемое слово goOrOl00.

Комбинируя между собой машины А, Б+, Б , В, Г, легко получить машины, выполняюш;ие более сложные преобразования слов. Так, например, имеем:

ББ*) Двойной перенос:

Б+Б+: giOlOlON 01010. Ц) Циклический сдвиг: Ц = ВБ~В.

Ц: OlOlgiOlN 01go01=01"0.

Гг) Копирование: Гг = Б+ВГВБ+ВГВ.

Гг: giOlOl" Н OrOlgoOlW.

Проверка того, что указанные композиции машин действительно выполняют заданные преобразования машинных слов, очевидна.

Как уже говорилось, для доказательства основной тео-релш нам достаточно назгчиться строить машины, правильно вьгчисляюш;ие простейшие функции и функции, возникающие пз правильно вычислимых функций с помощью операций суперпозиции, примитивной рекурсии и минимизации. К этим построениям мы теперь и перейдем.

Лемма 2. Функции о (х) = О, s (х) =х + i, d {х) = X - i правильно вычислимы.

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

о (х) = 0: giOlO 1=. goOO+i giO gsR дЛ дгй Ol-gaO gaO -> дзЬ ggl -> giO Ol--igiOO giO gsL gsOO+i gsO goO goOO-+i

d (х) = X i:

некоторых слов uq, bo, йу, Ъу, . ., ut, bi в алфавите {О, 1} н каких-то машин U, V, . . ., W

uogibo iU)iaiqbi (FjeOagyba. . • (W)6uiqJ>i,

aagiboiiUV)...W}uig,bi.

Докажем теперь оставшиеся нужные нам леммы.

Лемма 3. Простейшие функции /< (ху, . . ., х) = - Xi {s i; S, t == i, 2, . . .) правильно вычислимы.

Укажем, наприлшр, программу для J. Символы А, Б, В, Г, {О), . . . обозначают программы рассмотренных ](ыше машин. Очевидно,

giOlOl! (BOlgpOl" (B)pOlJgOl (О)уОРдвО ... О (Б-)бде01". Таким образом, искомой машиной, вьг1зисляюш;ей правильно функцию ll, является композиция Б* * В * (0) * Б~.

Лемма 4. Если частичные функции g {ху, . . ., Xs), III [xi, . . ., Xt), . . ., hs {xi, . . Xi) правильно вычислимы, то суперпозиция / ii, . . .,xt) = g {hy {xy, . . ., Xt), . . .,K [xy, . . ., Xt))

-также правильно вычислимая частичная функция.

Пусть {g), {hy), . . ., {hs) - программы машин, правил ьно вычисляющих указанные функцип. Если g - одноместная функция, то из

giOT"... Oit {hy)ygff)i..... (g)egvO№

видно, что машпна (AJ * () правильно вычисляет нужную нам функцию g {hy).

Чтобы не писать излишне длинных выражений, рассмотрим еще лишь случай, когда заданные частичные функции g, hy, /г-з двуместны. Пользуясь введенньиш выше машинами сдвига, транспозиции, удвоения и нулевой функции, получим

gi01--01(rr)i 01-01g„01=01« {hi)a 01-01!gp01.(=. У) (Ц)в OIW. !)gvO101! (/i2)v •01W.J)g601W».s) (Б-)в ggOl.e. у)01л=(--. У) (g)e д.01(л„/.) g.,0-goO до01г(Л..л,).

s{x) = х + I: giOlO im goOl+i qyO -> qR qd qR OiqO З2О 9з1

giOl0 goOlOO qyO -H. дЛ

gl -> дЛ OlgO gaO -> qsL

ggl -> giO 01«-ig400 qS -qL

q,i -> q,L gOl-iOO

ggO goO для a; = 0.

Выше прослен<ен процесс переработки слова gjiOlO для ж > 1. Легко убедиться, что результатом переработки указанного слова по изложенной программе для х = О будет требуемое слово доОО.

.Для того чтобы легче было следить за работой машин в оставшихся более сложных случаях, введем следуюш;ие обозначения. Пусть Т - программа какой-то машины с алфавитами - внешним О, 1 и внутренним gg, gi, . . ., g„, причем go - символ заключительного состояния. Пусть а - положительное натуральное число. Заменяя в записи команд программы Т символы д, . . ., д„ соответственно символами да, . . ., ga+n-i, а символ до символом д+п, получим программу машины с тем же внешним алфавитом {О, 1} и внутренним алфавитом (д, g<x+i, • • , Яа+п}, причем заключительным символом теперь служит символ да+п Эту новую программу будем обозначать через Та илп, подробнее, через Тр, где чпсло р = а + /г целиком определяется машиной Т п числом а. Условимся также писать

еслп машпна Т, начав работать в состоянпи адаЬ, переходит через некоторое врелш в заключительное состояние %?pbiO ... О прп условпи, что в процессе работы лента не надстраивалась слева. Вспоминая теперь опреде.ление композиции машин, непосредственно видим, что еслп для