1.7. СВЯЗЬ МАШИН ТЬЮРИНГА И РАМ

Основное применение машины Тьюринга находят в установлении нижних опенок на время и память, необходимые для решения данной задачи. В большинстве случаев мы можем установить нижние оценки только с точностью до полиномиальной связанности. Для более точных оценок потребуется рассматривать более специфические детали конкретных моделей. К счастью, вычисления на РАМ и РАСП полиномиально связаны с вычислениями на МТ.

Рассмотрим связь между РАМ и МТ. Очевидно, что РАМ может моделировать работу -ленточной МТ, помещая по одной клетке МТ в регистр. В частности, клетку ленты можно хранить в регистре где с — постоянная, назначение которой — дать РАМ некоторое "оперативное пространство". В него включаются к регистров для запоминания положений головок МТ. РАМ может считывать клетки МТ, используя косвенную адресацию с помощью регистров, содержащих положения головок на лентах.

Предположим, что данная МТ имеет временную сложность Тогда РАМ может прочитать ее вход, запомнить его в регистрах, представляющих первую ленту, и смоделировать эту МТ за время при равномерном весовом критерии и при логарифмическом. В любом случае время на РАМ ограничено сверху полиномом от времени МТ, ибо любая функция типа есть, разумеется,

Обратное утверждение верно только при логарифмическом весовом критерии для РАМ. При равномерном весе -шаговая программа для РАМ без входа может вычислять числа порядка что требует порядка клеток МТ только для запоминания и считывания. Поэтому при равномерном весе, очевидно, нет полиномиальной связи между РАМ и МТ (упр. 1.19).

Хотя при анализе алгоритмов мы предпочитаем равномерный весовой критерий в силу его простоты, мы должны отвергнуть его, если пытаемся установить нижние границы на временную сложность. РАМ с равномерным весом вполне разумна, когда рост чисел по порядку не превосходит размера задачи. Но, как мы уже говорили, при использовании РАМ в качестве модели размер чисел "заметается под ковер", и вряд ли можно получить полезные нижние оценки. Для логарифмического веса, однако, верна следующая теорема

Теорема 1.3. Пусть язык, допускаемый некоторой РАМ за время при логарифмическом весе. Если в -программе

Рис. 1.23. Представление РАМ на МТ.

нет умножений и делений, то на многоленточных машинах Тьюринга имеет временную сложность не более

Доказательство. Представим все не содержащие нуля регистры рассматриваемой РАМ, как показано на рис. 1.23. На ленте помещена последовательность пар чисел записанных в двоичной форме без нулей в начале слова и разделенных маркерами. Для каждого число есть содержимое регистра Содержимое сумматора РАМ хранится в двоичном коде на второй ленте, а третья играет роль рабочей памяти. Еще две ленты служат для записи входа и выхода РАМ. Каждый шаг программы РАМ представлен конечным числом состояний МТ. Мы не будем описывать моделирование всех команд РАМ, а рассмотрим только команды которые разъясняют общую идею. Для можно устроить МТ так, чтобы она работала следующим образом.

1. На ленте 1 разыскивается место, соответствующее регистру 20 в РАМ, т.е. последовательность . Если оно находится, на ленту 3 помещается следующее за ним число, которое будет содержимым регистра 20. Если такое место не нашлось, машина останавливается — содержимое регистра 20 равно 0, и поэтому косвенную адресацию произвести нельзя.

2. На ленте 1 разыскивается место, где хранится регистр РАМ, номер которого записан на ленте 3. Если оно находится, то содержимое этого регистра записывается на ленту 3. Если нет, туда помещается 0.

3. Число, записанное на ленту 3 на шаге 2, прибавляется к содержимому сумматора, которое хранится на ленте 2.

Для моделирования можно так построить МТ, чтобы она работала следующим образом.

1. Разыскивается место расположения регистра 30 в РАМ, т. е.

2. Если оно находится, то на ленту 3 записывается все, что расположено справа от кроме числа, стоящего непосредственно справа (т. е. старого содержимого регистра 30). Затем содержимое сумматора (на ленте 2) записывается непосредственно справа от а за ним помещается слово, скопированное на ленту 3.

3. Если на ленте 1 не нашлось места, соответствующего регистру 30, то, дойдя до самого левого пустого символа, машина печатает затем содержимое сумматора и, наконец,

Подумав немного, нетрудно понять, что можно указать МТ, которая правильно смоделирует РАМ. Мы должны показать, что вычисление на РАМ с логарифмическим весом к потребует не более шагов на машине Тьюринга. Сначала заметим, что регистр может появиться на ленте 1, только если его текущее значение когда-то раньше было помещено в этот регистр. Вес записи в регистр равен что с точностью до постоянной равно длине нашего представления Отсюда мы заключаем, что длина непустой части ленты 1 есть

Моделирование любой команды, отличной от имеет порядок длины ленты 1, т. е. ибо основное время уходит на поиск на ленте. Аналогично время моделирования не больше суммы времен поиска на ленте 1 и копирования ее — все вместе Следовательно, одну команду РАМ (кроме умножения и деления) можно промоделировать не более чем за шагов МТ. Так как одна команда РАМ занимает при логарифмическом весе по крайней мере одну единицу времени, общее время, затрачиваемое соответствующей МТ, есть что и требовалось доказать.

Если в РАМ-программе участвуют команды умножения и деления, то можно написать подпрограммы для МТ, выполняющие эти операции с помощью сложений и вычитаний. Читателю предоставляем доказать, что логарифмические веса этих подпрограмм не больше квадрата логарифмических весов соответствующих команд. Таким образом, нетрудно доказать следующую теорему.

Теорема 1.4. РАМ и РАСП с логарифмическим весом и многоленточные машины Тьюринга полиномиально связаны.

Доказательство. Примените теоремы 1.1 — 1.3 и проанализируйте подпрограммы для умножения и деления.

Аналогичный результат справедлив и для емкостной сложности хотя он представляется менее интересным.