1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 3
Текст из файла (страница 3)
В следующих разделах мы обсудим несколько основных моделей вычислительных устройств, наиболее важными из которых являются машина с произвольным доступом к памяти, машина с произвольным доступом к памяти н хранимой программой и машина Тьюринга. Эти три модели эквивалентны с точки зрения принципиальной вычислимости, но не с точки зрения скорости вычислений. Быть может, наиболее важным мотивом, побудившим рассмотрение формальных моделей вычисления, было желание раскрыть подлинную вычислительную сложность различных задач.
Нам хотелось бы получить нижние оценки на время вычислений. Чтобы показать, что не существует алгоритма, выполняющего данное задание менее чем за определенное время, необходимо точное и подчас высоко специализированное определение того, что есть алгоритм. Одним из примеров такого определения служат машины Тьюринга в равд. 1.6. Для описания алгоритмов желательно иметь обозначения, более естественные н легче понимаемые, чем программа для машины с произвольным доступом к памяти, машины с произвольным доступом к памяти и хранимой программой или машины Тьюринга. Поэтому мы введем также язык высокого уровня, называемый Упрощенным Алголом. Именно этот язык будет использоваться во всей книге для ьз, машины с ппоизвольным достппом к памяти описания алгоритмов. Однако, чтобы понимать вычислительную сложность алгоритма, написанного на Упрощенном Алголе, мы должны соотнести Упрощенный Алгол с более формальными моделями.
Это будет сделано в последнем разделе настоящей главы. т.2. МАШИНЫ С ПРОИЗВОЛЬНЫМ ДОСТУПОМ К ПАМЯТИ Машина с произвольным доступом к памяти (или, иначе, равнодоступная адресная машина — сокращенно РАМ) моделирует вычислительную машину с одним сумматором, в которой команды программы не могут изменять сами себя.
РАМ состоит из входной ленты, с которой она может только считывать, выходной ленты, на которую она может только записывать, и памяти (рис. 1.3). Входная лента представляет собой последовательность клеток, каждая из которых может содержать целое число (возможно, отрицательное). Всякий раз, когда символ считывается с входной ленты, ее читающая головка сдвигается на одну клетку вправо. Выход представляет собой ленту, на которую машина может только записывать; она разбита на клетки, которые вначале все пусты.
При выполнении команды записи в той клетке выходной ленты, которую в текущий момент обозревает ее головка, печатается целое число и головка затем сдвигается на одну клетку вправо. Как только выходной символ записан, его уже нельзя изменить. Память состоит из последовательности регистров гм го гм ..., каждый из которых способен хранить произвольное целое дееееап еееае /баеве ее пеев) о)пзпюпее 1 ! ВимаЪая еееюм упелеее лиатма) Рвс. ЦЗ. Машина с произвольным доступом к памяти. гл. ь модвли вычислвнии число.
На число регистров, которые можно использовать, мы не устанавливаем верхней границы. Такая идеализация допустима в случаях, когда 1) размер задачи достаточно мал, чтобы она поместилась в основную память вычислительной машины, 2) целые числа, участвующие в вычислении, достаточно малы, чтобы их можно было помещать в одну ячейку. Программа для РАМ (или РАМ-программа) не записывается в память. Поэтому мы предполагаем, что программа не изменяет сама себя. Программа является, в сущности, последовательностью (возможно) помеченных команд. Точный тип команд, допустимых в программе, не слишком важен, пока они напоминают те, которые обычно встречаются в реальных вычислительных машинах.
Мы предполагаем, что имеются арифметические команды, команды ввода- вывода, косвенная адресация (например, для индексации массивов) и команды разветвления. Все вычисления производятся в первом регистре гм называемом суммапюром, который, как и всякий другой регистр памяти, может хранить произвольное целое число. Пример набора команд для РАМ показан на рис.
1.4. Каждая команда состоит из двух частей — «ода операции и адреса. В принципе можно было бы добавить к нашему набору любые другие команды, встречающиеся в реальных вычислительных машинах, такие, как логические или литерные операции, и при этом порядок сложности задач не изменится. Читателю разрешается думать, что набор команд дополнен так, как это его устраивает. Операнд может быть одного из следующих типов: 1) =( означает само целое число 1 и называется литералом, 2) 1 — содержимое регистра 1 (1 должно быть неотрицательным), 3) «1 означает косвенную адресацию, т. е. значением операнда служит содержимое регистра 1, где 1 — целое число, находящееся в регистре(; если 1(0, машина останавливается. Эти команды хорошо знакомы всякому, кто программировал на языке ассемблера. Можно определить значение программы Р с помощью двух объектов: отображения с нз множества неотрицательных целых чисел в множество целых чисел и «счетчика команд», который определяет очередную выполняемую команду.
Функция с есть отображение памяти, а именно с(1) — целое число, содержащееся в регистре ( (содержимое регистра 1). Вначале с(1)=0 для всех 1)0, счетчик команд установлен на первую команду в Р, а выходная лента пуста. После выполнения и-й команды из Р счетчик команд автоматически переходит на и+1 (т.
е. на очередную команду), если й-я команда не была командой вида П)МР, НА1.Т, )ОТЕ или ЗсЕ(«0. »а ьк мдшины с пвоизвольным достнпом к пдмяти Адрес Код операции !. 1.ОАР 2. БТОКЕ 3. АРР 4. Я)В 5. М('1.Т 6. О!'ч' 7. КЕАР 8. %К!ТЕ 9. ЖМР 19..) ОТК 1!. 3ХЕКО 12. НА1.Т операнд операнд операнд операнд операнд операнд операнд операнд метка метка метка Рнс. !.4. Таблица команд РАМ. Чтобы описать действие команды, зададим значение с(а) операнда а: п(=1) =1, с (1) = с (1), о (н() = с (с (1)) .
Таблица на рис, 1.5 определяет действие каждой команды из таблицы на рис. 1,4. Команды, действию которых не дано определения (такие, как ЬТОК Е = — 1), можно считать эквивалентными команде НА1.Т. Аналогично деление на нуль останавливает машину. При выполнении любой из первых восьми команд счетчик команд увеличивается на единицу. Поэтому команды в данной программе выполняются последовательно, до тех пор пока не встретится команда ) УМР или НА).Т либо )ОТЕ при содержимом сумматора, большем нуля, либо )ЕЕКО при содержимом сумматора, равном нулю.
Вообще говоря, РАМ-программа определяет отображение из множества входных лент в множество выходных лент. Так как на некоторых входных лентах программа может не останавливаться, это отображение является частичным (т. е, для некоторых входов оно может быть не определено). Это отображение можно интерпретировать разными способами. Две важные интерпретации — интерпретация в виде функции и интерпретация в виде языка. Предположим, что программа Р всегда считывает с входной ленты л целых чисел и записывает на выходную ленту не более одного ГЛ.
1. МОДЕЛИ ВЫЧИСЛЕНИЙ Лействие Команда с(0) - о(а) с(1) - с(0) с(с(1)) — с(0) с(0) - с(0) + и(а) с(0) — с(0) — о(а) с(0) — с(0) Х В(а) с(0) — ( с(0)/о(а)) ') с(1) - очередной входной символ. с(с(1)) — очередной входной символ. В обоих случаях головка входной ленты сдвигается иа одну клетку вправо. о(а) печатается в той клетке выходной ленты, которую в данный момент обозревает ее го- ловка.
Затем зта головка сдвигается на одну клетку вправо. Счетчик команд устанавливается на команду с меткой Ь. Если с(0)) О, то счетчик команд устанавли- вается на команду с меткой Ь, в противном случае на следующую команду. Если с(0) =О, то счетчик команд устанавли- вается на команду с меткой 6, в противном случае на следующую команду. Работа прекращается. 1.
ЬОА1) а 2. ЗТОКЕ 1' ВТОР,Е е1 3. АИЭ а 4. Я)В а 5. М1)ЬТ а 6. 01Н а 7. ЕЕАР 1 ЕЕА() иг' 8. %Е1ТЕ а 9. Л)МР Ь 10. и'ОТ2 Ь !1. ЛХЕКО Ь 12. НА1.Т Рис. Ьб. Действие команд РАМ. Операнд о есть =1, 1 илн ° Ь целого числа. Пусть х„х„..., х„— целые числа, находящиеся в л первых клетках входной ленты, и пусть программа Р записывает у в первую клетку выходной ленты, а затем через некоторое время останавливается. Тогда говорят, что Р вычисляет функцию 7 (х„..., х„)=у. Легко показать, что РАМ, как и всякая другая разумная 18 1) Повсюду в этой книге ( х 1 (лошолох х) обозначает наименьшее целое, большее или равное х, 1 х 1 (дно, или целая чапаю х) обозиечает наибольшее целое, меньшее нли равное х. ья млшины с произвольным дострпом к плмяти модель вычислительной машины, может вычислять в точности частично рекурсивные 4ункции.
Иными словами,для произвольной частично рекурсивной функции 7" можно написать РАМ-программу, вычисляющую ), и для произвольной РАМ-программы можно указать эквивалентную ей частично рекурсивную функцию. (По поводу рекурсивных функций см. Дэвис П958) или Роджерс (1967).) Другой способ интерпретировать программу для РАМ вЂ” это посмотреть на нее с точки зрения допускаемого ею языка. Алфавит — это конечное множество символов, язык — множество цепочек (слов) алфавита. Символы алфавита можно представить целыми числами 1, 2,..., й при некотором Ь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
