Студопедия — Связь МТ и РАМ-машины.
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Связь МТ и РАМ-машины.






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

Рассмотрим связь между РАМ и МТ.

РАМ может моделировать работу 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)).

Моделирование РАМ машиной Тьюринга.

Представим все, не содержащие нуля, регистры РАМ на ленте МТ следующим образом:

β β i1 β c1 β β i2 β c2 β β ik β ck β β

На ленте МТ помещена последовательность пар чисел (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) на машине В.

Моделируемая машина В Моделирующая машина А
МТ (1 лента) МТ (к лент) РАМ
МТ (1 лента) - O(T(n)) O(T(n)logT(n))
МТ (к лент) O(T2(n)) - O(T(n)logT(n))
РАМ O(T3(n)) O(T2(n)) -

 







Дата добавления: 2015-09-07; просмотров: 518. Нарушение авторских прав; Мы поможем в написании вашей работы!



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

Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

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

Машины и механизмы для нарезки овощей В зависимости от назначения овощерезательные машины подразделяются на две группы: машины для нарезки сырых и вареных овощей...

Классификация и основные элементы конструкций теплового оборудования Многообразие способов тепловой обработки продуктов предопределяет широкую номенклатуру тепловых аппаратов...

ПРОФЕССИОНАЛЬНОЕ САМОВОСПИТАНИЕ И САМООБРАЗОВАНИЕ ПЕДАГОГА Воспитывать сегодня подрастающее поколение на со­временном уровне требований общества нельзя без по­стоянного обновления и обогащения своего профессио­нального педагогического потенциала...

Эффективность управления. Общие понятия о сущности и критериях эффективности. Эффективность управления – это экономическая категория, отражающая вклад управленческой деятельности в конечный результат работы организации...

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

Studopedia.info - Студопедия - 2014-2024 год . (0.01 сек.) русская версия | украинская версия