Файл: Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы.pdf

повременное сползание на одну позицию правой конфигу­ рации влево и левой конфигурации вправо и сравнение пары подошедших к точке стыка полуконфпгурапий. Рис. 53,о изображает сравнение «Р (v) = Р (v + 1)?», рис. 53, б — сравнение «Р (v — 1) = Р (v + 2)?» и т. д. Если слово Р симметрично, то на (v — 1)-м такте появится конфигурация рис. 53, д, которая на следующем такте приведет к конфи-

гурации рис. 52, д. Допустим, что слово Р несимметрично и

на следующем такте (рис. 53, г) это зафиксируется появле­ нием нижнего символа Л' у точки стыка. Этот символ сохра­ няется при дальнейшем сползании. На предпоследнем так­ те появляется конфигурация рис. 53, е, которая еще через один такт переходит в конфигурацию рис. 52, е. Теперь ясно, что для доказательства теоремы 3 достаточно решить следующую задачу.

J86.

Вторая задача. Построить нейманову программу Э?п, которая обеспечивает переработку конфигурации рис. 52, а в конфигурацию рис. 53, а с соблюдением следующих условий:

Л(покоя), л, л, п, п\ в) по ходу этой переработки до появления конфигура­

дет переход от рис. 52, а и 53, а согласно SRn, а затем далее от 53, а к 52, д или к 52, в согласно fSls- При этом общее затра­ чиваемое время не превышает дозволенной оценки.

Роль программы 9?п заключается, очевидно, в том, чтобы довести одновременно до каждой буквы слова Р информа­ цию-о том, какой половине слова она принадлежит: левой или правой. Аналогия с задачей о стрелках достаточно проз­ рачна. Специфика новой ситуации сводится лишь к следую­ щим двум пунктам: 1) теперь мы имеем дело со стрелками двух категорий (нули и единицы), вместо прежних стрелков одной категории (сплошь палочки); 2) вместо общего для всех приказа «пли» (нижний символ*) теперь стрелкам из левой полушеренги, нужно выполнять приказ «пли на­ лево!» (нижний символ Л), а стрелкам из правой полушерен­ ги— приказ «пли. направо!» (нижний символ П). Однако обе эти особенности несущественны; и рассмотренное нами решение (§ 22) легко может быть приспособлено и к'новым

5 п тактов. Модификации, которые нужно ввести, потребуют лишь увеличения числа внутренних состояний нейманова элемента (стрелка). Например, вместо двух верхних сим­ волов I, р потребуются четыре: /°, I 1 , р°, р 1 — для запоми­ нания того, какие буквы (0 или 1) стояли в тех местах, где заканчивались очередные циклы дихотомии. В заключи­ тельном такте это позволяет восстанавливать в верхнем этаже первоначальное слово Р; кроме того, увеличение числа состояний необходимо для того, чтобы после первой дихотомии и впредь до выстрела в левой и правой полузовах длиной п/2 употреблялись различные состояния.

167

Это позволяет на заключительном такте установить всюду в левой полузоне нижний символ Л, а всюду в правой полузоне — другой нижний символ П. Опуская эти детали, можем считать теорему 3 доказанной.

состояния покоя ф. Тогда за один такт эта конфигурация перерабатывается в конфигурацию рис. 55, б, активная зона которой, очевидно, во всяком случае не длинее s -f- 2

188

изображены конфигурации «трехэтажной» машины Тью­ ринга 50?, которая на своем втором этаже стремится ими­

машины 2)?совершает колебания, изображенные посредством зигзагообразной линии под лентой на рис. 55, в. При пер­ вом пробеге — слева направо — машина записывает на верхнем этаже каждой посещаемой ячейки содержимое вто­ рого этажа соседней с нею левой ячейки. В результате воз­ никает конфигурация рис. 55, г. При возвращении налево в нижний этаж каждой ячейки заносится содержимое вто­ рого этажа соседней справа ячейки. Итак, после одного полного колебания в каждой ячейке зоны длины s + 2 уже накоплена информация о состоянии соответствующей ней­ мановой ячейки и о состояниях ее соседей слева и справа. Начиная свой очередной пробег слева направо, машина 50? осуществляет в каждой ячейке замену тройки неймановых состояний тем состоянием, которое предписывается суще­ ствующей командой программы 31; это состояние заносится на второй этаж, а другие два этажа очищаются. К концу третьего пробега запись на тьюринговой ленте уже имеет вид, указанный на рис. 55, е. Наконец, головка возвра­ щается влево, не производя никаких записей и, достигнув ячейки с записью и (0), переходит в состояние (обозначен­ ное на рис. 55, в через г0). Теперь она уже готова к сле­ дующему циклу, в котором будет моделироваться следующий нейманов такт. Ясно, что можно построить машину Тьюрин­ га 50?, выполняющую описанный нами алгоритм (подтверж­ дение основной гипотезы теории алгоритмов).

При составлении программы 50? на самом деле нужно учитывать еще некоторые другие, впрочем, довольно оче­ видные детали. Например, машине 50? необходимо как-то помечать на каждом цикле ячейку, из которой она начи­ нает свои колебания, дабы при обратном движении она могла бы обнаружить ее и продолжать свой путь ровно на

189