lekcii2 (Лекции), страница 3

Необходимость частых копирований данных на ленте обусловлена выбранным способом нормированных вычислений, согласно которому каждое неэлементарнос действие выполняется над крайними правььми словами,ленп>ы, так что перед выполнением каждого неэлементарного действия необходимо переместить к правому кран> ленты слова,, над которыми оно должно быть выполнено (количество слов зависит от конкретного действиями. Необходимость постоянного слежения за ситуациями на ленте при составлении программы возникает в связи с тем, что положение слов на ленте определяется относительно текущего положения, головки, которое все время меняется. Итак, мы показали, что недостатки языка ОСТ как средства, для описания алгоритмов предопределены особенностями выбранной модели вычислений.

То, что удобно для построения красивой математической теории алгоритмов, малопригодно для составления реальных алгоритмов и программирования. Поэтому для разработки более удобных и эффективных средств описания алгоритмов необходимо прежде всего построить более совершенную модель вы шслений. Такая модель была построена Джоном фон Нейманом 110 в середине 40-х годов. Машина фон Неймана., к рассмотрению которой мы переходим, была, получена путем усовершенствования машины '!'ьюринга.

2.9.2 Адреса и имена Рассмотрим нормированное вычисление функции !(им и,э,..., п,„) па универсальной машине Тьюринга (УМТ). До начала работы УМТ на ее ленту записывается программа Р~ нормированного вычисления функции 1 и начальные данные. Головка, УМТ помещается непосредственно за начальными данными. Для удобства будем помещать программу на ленте между специальными символами Пни Дк. Будем считать, что программы внешних МТ, используемых в программ; Р~, расположены слева, от ячейки с символом Дни ограничены слева, ячейкой с символом Я.

Тогда начальная ситуация на ленте оудет иметь вид ('П П'П'-' ' ®'- где многоточие между символами (д)и Днобозначает часть ленты, занятую внешними программами. Нормированность вычисления функции ! программой Р~ означает, что в процессе выполнения программы Ру часть ленты, расположенная левее ячейки с символом Пд, будет оставаться пустой. Более того, головка никогда не будет гюпадать в эту часть ленты, и если, например, эту часть ленты «отрезать» и убрать, то УМТ при выполнении программы этого даже «нс заметит». Все данные, появляннцисся на ленте в результате работы программы Р», размещаются в ячейках ленты, расположенных правее ячейки., содержащей символ [к~.

Воспользуемся этим обстоятельством, чтобы избавиться от пресловутой необходимости постоянного слежения за ситуапиями на ленте при составлении программы. Для опредегдния положения слова на ленте не будем использовать рабочую ячейку, указываемую текущим положением головки, поскольку. оно все время меняется. В качестве начала отсчета примем некоторую фиксированную ячейку ленты, например, содержащую символ П к: слову, расположенному непосредственно вслед за этой ячейкой, сопоставим номер 1, следующему слову -- номер 2 и т, д.

Номер, сопоставленный некоторому слову, назовем адресол«этого слова. Таким образом, каждому значению (слову), расположенному на ленте, ставится в соответствие его афес, который не меняется в процессе выполнения программы. Подчеркнем, что припнсанные словам адреса, нигде в явном виде не записываются: ни в самих словах, ни где-либо отдельно. Чтобы получить адрес конкретного слова, надо «проехать со счетчиком в руках» от первого слова к заданному. То есть понятие адреса вторично; оно задано конструктивным образом, так как адрес каждого слова может быть сгенерирован по известному алгоритму.

Наличие постоянных адресов у данных позволяет сконструировать МТ, которал по адресу некоторого слова, записанному на ленте в виде целого десятичного числа, устанавливает головку на пробеле, расположенном непосредственно вслед за этим словом. Мы назовем эту МТ именем © (поиск по адресу). Действие этой машины описывается следу- 111 ющей парой ситуаций: [ЛЯ .. ЯР Пкл,ЛИЛ... ЛиьЛизь~.~... Лш„ЛАь(Л)Л > О ~* (Лпд .. ЦнРЯи~,Ли~гЛ... Лш~(Л)лл,, ~...

и>„ЛфЛ > где Аь -- адрес слова и~в, т. е. десятичная запись целого числа, Й, ф -- некоторый специальный символ, используемый для разметки ленты. В заключительной ситуации машины Ф адрес Аь оказывается стертым, а пометка ф сохраняется, чтобы облегчить работу машин, использующих поиск по адресу, т. е. гюдобно собаке-пойнтеру машина © «делает стойку» у искомого слова. Схема машины © может быть сконструирована из машин й,1, Л ы десятичного декремептора Т ~ и предиката Тш (состоит ли слово из нулей?). Схема машины Ф имеет вид ЮТТА В схеме машины Ф использованы следующие «П': е~: Б,, (а, Ь) некоторые буквы. т„., (т„.„,,) — е 112 Из приведенных схем видно, что маппина 7сг выясняет, состоит ли слово, к которому она применяется, из одних нулей или нет, т.

с, проверяет число, изображаемое этим словом на равенство нулю; машина 1', преобразует слово, к которому она применяется, в новое слово, изображающее чисгкг на едипипу меньшее, чем исходное слово, т. е. заменяет число предыдучпим. Используя машину Ф, нетрудно сконструировать машины Т„и Т, первая из которых записывает вместо адреса, слово, расположенное по этому адресу, а вторая заменяет слово, записанное по адресу, указанному на, ленте, на слово, непосредственно предшествующее слову, представляющему адрес; 7'„ !ЛЯ.. ПнР1пкийЛиг...

Ли~ьЛи~ь г.,. Ли,,ЛАьЯЛ > =~' ~Л~д]... [н)ЛР~~ к~~ю~Лиг... ЛгюьЛгюь ~... Ли~„Лгюь(Л)Л > и !ЛЯ.. ЯР~яю~Лиг .. ЛиьЛгюь г... Лт„,ЛгюЛАь(Л)Л > ==~" ~ЛЯ... н~Л11~к~гю~Лиг .. Лгюь ~ЛиЛиь г... Ли~„Ли,(Л)Л > Заметим, что машины '1„' и '1,', моделирукгт последовательное запоминающсе устройство — хранилище слов на участке ленты машины Тьюринга, фактически реализуя их копирование. 1!ри этом они значительно мощнее машин копирования типа К„с их постоянным плечом (и = сопв$!), поскольку чтение и запись осуществлянгтся в ячейки с переменными номерами. На основе машин Т, и Т,„, можно сконструировать машины Т,:в(!с) и Т.,вЯ, где !г-- адрес слова. В самом деле, диаграммы этих машин имеют вид Т,в® = И'л„, .Т, Т„;,,(Й) = И'л„, Т где машина И'г„записывает на ленту слово, изображающее десятичное число !с, т.

е. изображение числа из текста программы переносится на,ленту МТ. Машины Т„~Я и Т, вЯ позволяют существенно упростить программы МТ, сделав их более гюпятными. Например, они дают возможность записать программу машины НОД в виде МТ НОД ВЕС1Х А1РНАВЕТ: О, 1, 2, 3, 4, Б, 6, 7, 8, 9; МТ-; ЫВ; МТф; ЫВ; МТ>; ЫВ; НН; 7~; 1)О И7 Т„а(3); 7'„и(4); > П' И. '1'„с (3); 7'„в(4); —; Т,- (3) Ц Л? 7",~ц(4); 7;и(3); —; 7',,~д(4) Е1; 7'в(3) ~ '1'в(4) ~ ф ОР; КН; Е1х1В НОД В этой программе все преобразования осуществляются над словами с адресами 3 и 4, 113 причем В 1ц)Оцессс.' ВьшОлнения нрОГ)заымы зн11чсния этих слОВ меняются (В слОВах с а!Н росами 1 и 2 сохранены исходные значения).

В сас!ьнейшем такие слова будем называть перел!синь!.ми, а их адреса адресами 11еременнь!т, С:и!ва, значения которых в проиессе выполнения программы не меняются (В программе машины 11ОД это слова с адресами 1 и 2), будем называть константами, а, их адреса адрес!а.ми констант.

Текст программы становится еще более понятным, если вместо адресов пс;ременных и кОнстйнт испОльзовйть имс1нй . 11,с!еисми перемснной или констйнты мы будеь! Ийзывйть слово над произвольным алфавитом, сопоставленное адресу этой переменной или константы. Сопоставление может быть осуществлено с помощьн! таблицъс имен, т. с, последовательности слов, в которой перечислены все используемые в программе имена, причем вслед за каждым именем помещен соответствующий адрес. Таблицу имен мы расположим на ленте УМТ непосредственно перед программой 1>с, отметив ее начало ячейкой, в которуп! записан специальный символ Дт (начало таблицы имен).

Таким образом, программы внешних МТ располагаются на ленте между ячейками с с:имволами Яи ~т]. Мы будем считать, что таблица имен составляет часть программы 7>1. При использовании имен машины Т„~„Я и 1„,.~„(!С) заменяются соответственно машинами Т (и) и Т (и), которые сначала находят имя и, в таблице имен, за !ем по этому имени опрсдслгаот адрес 7с, после чего работают кйк мйп!ины 7'„а(11) и 7;„а(Й) соосвегственно. Знасси Т (11) и Т (и) сиывозп!зируют зйгрузку значений из именованной памяти ма!пины фон Неймана на регистры и, соответственно, их запоминание под указанными именами. Использование имен позволяет записать программу машины НОД в более понятном виде МТ НОД; ВЕС1Х А1РНАВЕТ: О, 1, 2, 3, 4, 5, б, 7, 8, 9; ХАМЕЯ! и, и, х, у; МТ-; ЫВ; МТ ф; 1ДВ; МТ>; ЫВ; Т(п); 1(х); ТЬ); 1(у) ' Т(х) ' Т(у) ' ф ' 1)0 И? Т (х); Т (у); > П' Иу Т(х); Т(у); -; Т(х) П Л' Т(у); Т(х) ' — ' Т(у) Е1; Т(х); Т(у); ф ОП; МОВИ(п, и, х) ЕЯБ НОД В программу добавляется строка ХАМЕДЕ, по которой составляется таблица имен: машины 1Ш и КН заменяются машиной ХОНМ, которой сообщаются имена аргументов и„ и и результата х; машина ХОг(М нормирует вычисление, реализуемое машиной НОД, сохраняя на ленте лишь слова с именами и, ь, т в указашюм порядке.

Итак, мы показали, что использование имен существенно прсиюняет текст программы и позволяет читать его бс! параллельного рассмотрения ситуаций на ленте. Однако вОбозпачепве певзвеетпых величин в козффпцвесгтов именами было предложено пзвестпым математиком Франсуа Виетом еще в 1591 т. 114 программы все равно остаются громоздкими и нсудобочитаемыми, что побуждаст к даль- нейшему усовершенствованию языка программирования. 2.9.3 Построение процессора фон Неймана В программах, рассмотренных в качестве примеров, широко использовались внешние МТ, программы которых считались заранее заггисаннымгг па специально отведенном для этого участке ленты универсальной МТ (назовехл этот участок Гг-яенгпойГ Использование внешних МТ позволило существенно упростить указанные программы, так как они запис:ывались уже нс чсрез элементарные действия т; 1, а, а через более содержательные дс>йствия, опрслдсляемые Внегннелми М Г.