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

все ячейки ленты, за исключением конечного их числа, будут охарактеризованы именно «двухэтажной» буквой д. Те­ перь, если мы буквы из R будем интерпретировать как сос­ тояния некоторого нейманова элемента, то ясно, как всякая тьюрингова конфигурация К естественным образом коди­ руется некоторой неймановой конфигурацией К- Напри­ мер, на рис. 48, а, б изображены неймановы конфигурации, кодирующие тыоринговы конфигурации рис. 42, а, б.Более

167

того, по заданной тыоринговой программе 9J? можно по­ строить нейманову программу 9Й так, что если 9R переводит за один такт К и К!, то автомат Неймана с программой Ж пе­ реводит за один такт К в конфигурацию, кодирующую

К'. В этом смысле автомат Неймана 9Й моделирует машину Тьюринга ЗЙ, причем, как легко понять, роль состояния

Процедуру перехода от 9Й и 3)? поясним на примере тьюринговой программы 50?0 из 21.1. В этой программе имеет­ ся команда рп-*-Лп'. Поэтому для любой тройки вида

д^Л., где х, у — любые внешние символы машины Э3?0,

168

в программе $?0 фигурирует команда: * дд->-л>. Она в точ­ ности отражает факт смещения головки из ячейки а+ в ячей­ ку а и появления состояния я' . По тем же соображениям

автомата, моделирующего 5Ш0. Верхние 14 строк рис. 49 как

раз н содержат все активные команды из 59?п; пассивные команды здесь опущены, так же, как п в программе рис. 45.

Легко понять, что процедура, проиллюстрированная только что на конкретном примере, всегда приводит к цели, т. е. перерабатывает любую заданную тыорингову про­ грамму 59? в «моделирующую» ее нейманову программу 50?. Возвращаясь к неймановой программе 50?0, заметим, что, исходя из начальной конфигурации рис. 48, а или рис. 48, б, она будет моделировать соответственно тьюринговы про­ цессы, происходящие в машине 59?0, при начальных конфи­ гурациях рис. 42, а, б. Это значит, что, начиная с рис. 48, а, в нижнем этаже неймановой ленты будет происходить «быстрое» перемещение символа л вправо, а, начиная с рис. 48, б, — «медленное» перемещение символа р вправо. Однако построенная указанным способом программа 50? (и, в частности, наша программа 50?о) однозначно определяет поведение нейманова автомата и для таких конфигураций

ячейка обозревается головкой, условимся называть обоз­ ревающими. Например, начиная с конфигурации рис. 48, в с двумя обозревающими состояниями, будут происходить одновременно быстрое перемещение символа я и медлен­ ное перемещение символа р; иначе говоря, происходит мо­ делирование системы двух экземпляров машины 50?о с об­ щей лентой. Аналогичная ситуация будет иметь место всег­ да, когда обозревающие состояния не слишком близки друг к.другу. В противном случае может сложиться совсем другая картина. Допустим, например, что в качестве на­ чальной взята конфигурация рис. 48, г с двумя соседними обозревающими состояниями. Поскольку среди активных

левая часть — тройка р д д или тройка A p„ , то в первых двух ячейках (активной зоны!) никаких изменений не произойдет. Зато на следующем такте в третьей ячейке появится сос­ тояние ^, потом такое же состояние появится в четвертой ячейке и т. д. Наконец, на (п — 1)ям такте возникнет кон­ фигурация рис. 48, д, которая более уже не будет изме­ няться.

170