Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Машина Тьюринга




Вычислительная машина с хранением программ в памяти с произвольной выборкой

Развитием формализма вычислительной машины с произвольной выборкой является вычислительная машина с хранением программ в памяти с произвольной выборкой (Random Access Stored Program Machine, RASPM), отличие которой состоит только в том, что программа сохраняется в памяти, а значит может изменять сама себя в процессе выполнения.

Набор инструкций для RASPM в общем случае может не отличаться от набора инструкций RAM. Впрочем, некоторые инструкции могут быть упрощены. Так, вместо непрямой адресации можно использовать возможность модификации инструкций программы для получения того же эффекта.

Известно, что имеют место две теоремы:

Теорема 2.1. Если стоимость инструкции является величиной постоянной или находится в логарифмической зависимости от длины операнда, то для любой программы RAM, имеющей сложность T(n), найдется константа k и эквивалентная программа RASPM, сложность которой будет не больше kT(n).

Теорема 2.2. Если стоимость инструкции является величиной постоянной или находится в логарифмической зависимости от длины операнда, то для любой программы RASPM, имеющей сложность T(n), найдется константа k и эквивалентная программа RAM, сложность которой будет не больше kT(n).

Большинство теоретических результатов относительно вычислительной способности различных автоматов (к которым относятся RAM и RASPM) получено для Машины Тьюринга. Следовательно, для применения к RASPM уже известных результатов, необходимо установить отношение между этими формальными системами.

Определение 2.5. Машина Тьюринга с одной лентой может быть определена как совокупность семи элементов:

,

где Q - множество состояний Машины Тьюринга, S - множество символов, которые могут быть записаны на ленте, I - множество символов входящей последовательности, - пустой символ, q0 - начальное состояние Машины Тьюринга, qf - конечное состояние Машины Тьюринга, d: Q x S -> Q x S x {l, r, s} - множество функций перехода, которые состоянию и символу ленты ставят в соответствие новое состояние, новый символ и перемещение по ленте: на шаг влево, на шаг вправо, остаться на месте

Машина начинает свою работу в состоянии q0 и в дальнейшем меняет состояния согласно функциям перехода в зависимости от текущего состояния и значения ячейки ленты. Попутно ячейки ленты перезаписываются новыми значениями согласно тем же функциям перехода.

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

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

Кроме того доказан фундаментальный результат.

Теорема 2.4. Не существует такой Машины Тьюринга, которая сможет определить остановится ли произвольная Машина Тьюринга на произвольном входе (проблема остановки)




Поделиться с друзьями:


Дата добавления: 2014-11-20; Просмотров: 392; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.011 сек.