Связь МТ и РАМ-машины.Основное применение МТ находят в установлении нижних оценок на время и память, необходимые для решения данной задачи. В большинстве случаев установить нижние оценки можно только с точностью до полиномиальной связанности. Для установления точных оценок потребуется рассматривать более специфические детали конкретных моделей. Рассмотрим связь между РАМ и МТ. РАМ может моделировать работу k-ленточной МТ, помещая в регистр одну ячейку с ленты МТ. В частности, i-ю ячейку j-той ленты можно записать в регистре k*i+j+c, c=const. k регистрами РАМ пользуются для запоминания k состояний головок МТ. РАМ может считывать исходные слова (буквы) из ячеек МТ, используя косвенную адресацию с помощью регистров, содержащих состояния головок. Предположим, что данная МТ имеет временную сложность Т(n)≥n. Тогда РАМ может прочитать её вход, запомнить его в регистрах, представляющих первую ленту, и смоделировать эту МТ за время O(T(n)) при равномерном весовом критерии и O(T(n)logT(n)) при логарифмическом. В любом случае время на РАМ ограничено сверху полиномом от времени МТ, т.к. любая функция O(T(n)logT(n))≤O(T2(n)). Обратное утверждение верно только при логарифмическом критерии. Утверждение. Пусть L - язык, допускаемый некоторой РАМ за время T(n) при логарифмическом критерии. Если в РАМ-программе нет умножений и делений, то на многоленточных МТ язык L имеет временную сложность не более O(T2(n)). Моделирование РАМ машиной Тьюринга. Представим все, не содержащие нуля, регистры РАМ на ленте МТ следующим образом:
На ленте МТ помещена последовательность пар чисел (ij, cj), записанных в двоичной системе счисления без нулей в начале слова и разделённых несобственной буквой β, где ij - номер регистра, cj - содержимое регистра в двоичной системе счисления (i=1,n). Содержимое сумматора РАМ хранится в двоичном коде на второй ленте. Третья лента МТ играет роль рабочей памяти. Ещё две ленты служат для записи входа и выхода РАМ. Каждый шаг РАМ-программы представлен числом состояний МТ. Рассмотрим как можно смоделировать команды РАМ на МТ. ADD *20 1. На ленте 1 отыскивается входное слово wj=ββ10100β, соответствующее регистру 20 в РАМ. Если такое слово wj находится, то на ленту 3 (которая играет роль рабочей памяти помещается следующее за ним число cj, которое будет содержимым регистра 20. Если же слова wj на ленте нет, машина останавливается, т.к. содержимое регистра 20 равно 0, и поэтому косвенную адресацию провести нельзя (на ленту были записаны все регистры с содержимым ≠ 0). 2. На ленте 1 отыскивается слово wcj, записанное на ленте 3. Если оно находится, то следующее за ним слово, отделённое несобственной буквой β записывается на ленту 3. Если этого символа нет, то на ленту помещается 0. 3. Число, записанное на ленту 3 на шаге 2, прибавляется к содержимому сумматора, которое хранится на ленте 2. Для моделирования команды STORE 30 (C(30)← C(0)) можно построить МТ, чтобы она работала следующим образом: 1. На ленте 1 отыскивается слово wj, соответствующее регистру 30 в РАМ, т.е. wj=ββ11110β. 2. Если оно находится, то на ленту 3 копируется лента 1, но слово cj непосредственно следующее за словом wj (т.е. указываещее на содержимое регистра 30) заменяется на слово, записанное на ленте 2. 3. Если на ленте 1 нет слова wj, то после того как на ленту 3 скопированы все исходные данные машина печатает слово wj=ββ11110β, затем содержимое сумматора и конец ββ. Аналогично можно смоделировать любые команды РАМ. Рис. Время, требуемое машиной А для моделирования работы алгоритма сложности Т(n) на машине В.
|
