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

Внешние М'!' программируются и записыван>тся на .О-лс>нту до того., как они будут применены при составлении очередной программы. Следовательно, они должны реализовывать действия, которые будут применимы при состаьлении достаточно широкого класса програхлм. Отметим, что такие дсйствия существуют. Это, нешример, простейшие математические действия над целыми числами (Тл.г, Т г) и специальные служебные отношенияп1зедикаты ('1сп). Универсальная МТ, ьг-лента которой с;одержит программы, реализующие арифметические действия, имеет каис>с>пветго новый урове>сь по сравнения> с универсальной М'Г с пустой Р-лентой: алгоритмы, связанные с выполнением арифметических действий над >ислами (нап1зимер> алгоритм Евклллда), о~~с~~аю~с~ на ней гораздо боле етыми программами.

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

Действия, реализуемые МТ, записанными на В-ленту, будем называть элементарными дейсгпвиями процессора или операциями. Все внешние МТ, реализующие операции, имеют одинаковый рабочий алфавит, называемый рабочс м о.лфавггтом процессора. Этот алфавит вяляс> >с я рабо~лглм азгц>авитом всс х программ, выполняемых гга лгросгс с>с>о1зсс Каждая операция применяется к одному или неско=ським сгкп>ам пад рабочим алфавитом процессора, называемых операндами,. Количество операндов определяет ягеспгносгпь операции (например, операция сложения имеет два операнда и потому является двуместпой).

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

Если операнды помещать па эту часть ленты, то в состав функций РИМ и АДР будет входить всего по одной копирунлцей МТ. Таким образом, 115 процессор наряду с 1)->гс>нсх>й, на которой хранятся программы его операций, наделяет<>я также 11-лентой (так мы назовем часть ленты, расположенную левее ячейки с символом Дд, на которую помсгцаются операнды перед выполнением опсрации), и О'-лентой, на которой записываются программа и ее данные. Удобно ггеренормироватгь операции таким образом, чтобы их результат такжс, помещался на Л-ленте не вслед за операндами, а вместо них.

Обмен данными между Л-лентой и Я->!витой осуществляется операциями РИМ(и) и АДР(п)., где и;имя операнда. Итак, для п,остроения ггроцессора необходимо: ° выбрать и зафиксировать рабочий а>!фавн!и процессора; обычно в качестве рабочего алфавита будем брать множество Ар — — (О, 1, 2,..., р — 1) первых р неотрипательных чисел (начиная с 0); слова над алфавитом Лр допускают естественную интерпрета; цию как неотрицательные целые числа в позиционной системе счисления с основанием р; ° зафиксировать конечное или бесконечное мноогсеспгво допусти,иыт, слов пад алфавитом Ар, если множество допустимых слов конечно и включает лишь слова фиксированной длины /с (либо слова, имеющие длину не больше, чел! Аг), то удобно добавить к множеству допустимых слов еще одно слово, называемое «персис>лнениеы» Т, которое означает, что в результате выполнения операции получилось слово, имея>щее длину, большую, чем й; множество допустимых слов может также содержать слово 1., обозначающее неопределенное значение операнда, см.

и. 3.1; ° составить и записать на, 1>-лс>нту программы 1!11'. выполняющие операции процессора (включая операции РИМ и ЛДР); ° сообщить обовначеггил оггераииг1 универсальной МТ (точнее управляя>щей программе этой универсальной МТ), на основе которой строится процессор.

В число операций процессора могут входить отноигениг» т. е, такие операции, которые по о;!ному или нескольким допустимым словам (аргументам отношения) вычисляют логичс>скОС значения и (истина) или л (лОжь); количествО аргумегггов каждОго ОТИОгпю!ия постоянно и называется его месгпностью. Строго говоря, отногпсния связыван>т числовые операнды, имеют истинностные значения и не являн>тся операциями, поскольку размыкают множество допустимых операндов, В качестве примера процессора можно рассмотреть процессор с множеством допустимых слов А„' (р фиксированное натуральное число), двумя одноместными операциями Т ! и Т ! и одним одноместным отношением Тш. Схемы МТ, вычисляющих Т» ..

(а) и То! (а), аналогичны упомянутым ранее (поскольку 1с-лента является зеркальным отражением ленты, рассматривавшейся выше, в этих схемах необходимо все действия 1 заменить на г, все т --- на с, все В -- на Х). Схема машины Т, (эта машина увеличивает слово, трактуемое как число в позиционной системе счисления с основанием р, на единицу) такова,: 116 РТ„ В последней схеме использована машина Т«, выполняющая действие т„ 1Ла1а2... а~ 1(сц)„д)1.. Л ) ===~* [Ла1а2... аг — 1а~(Л)Я... Л > где а, Е Ая.

Эта гиашина описывается следующей схемой: т„ 2.9.4 Согласование процессоров Построенные процессоры могут использоваться гю отдельности, или вместе. В последнем случае необходимо уточнить понятие согласованности. Определение 2.9.1. Два процессора называются согласованными, если определены функции (операции) перевода всех допустимых слов одного процессора в допустимые слова другого процессора и обратно.

При согласовании двух процессоров их Я-ленты обьединяются в одну. В результате получается конструкция, состоящая из управляющего устройства, Я-ленты, двух Л-лент и двух В-лент. Назовем ее двуленто юным процессором. Отметим, что каждая из двух лент двуленточного процессора содержит операцию переписи слов с «чужой' Л-ленты на «свою с одновременным их преобразованием к «свосму» допустимому виду. Несколько попарно согласованных процессоров образуют многолвнгпочный или и-ленточный процессор. Если управляющ1 ю программу и все .0-жнты многоленточного процессора заменить новым управляющим устройством, которое может выполнять все операции рассматриваемых В-лент, получится новый тип процессора, называемый процессором фон Неймана.

'1аким ооразом. процессор фон Неймана состоит из полубесконечной Я-ленты, на которую записывается программа и ее данные, одной или нескольких В-лент, на которые вызыван>тся операнды ссютветствующих процессоров перед выполнением операций, и управляклцего устройства,, просматривающего и интерпретирующего программу, записанную на 117 Я-леллтль Исполнение программы состоит в переносе операндов с Я->леытьл на одну из Л- лент или с одной В-ленты на другую, .в выполнении требуемых операций над операндами, вызванными на одну из >л-глеллт, и в записи резулыатов операций на Я->ленту.

2.9.5 Машина фон Неймана Мпилинолл фон Неймана называется аппаратная реализация процессора фон Неймана. Машина фон Неймана состоит из управляющего устройства, устройства памяти (аш>аратллая реализация Я-ленты) и одного или нескольких регистров (аппарат>лая реализация Л-лент). Далее в нал>ем курсе будет изложен язык описания программ лдя четырехленточного процессора фон Неймана, и соответствукицей машины фон Неймана. Описание языка, ориентировано на программиста. Оно полностьк> определяет процессор (машину) л1>он Неймана как некоторое абстрактное устройство, обеспечивакпцее выполнение (интерпретацию) программ. Прежде чем переходить к описанию конструкщлй языка программирования, необходимо рассмотреть один принципиальный вопрос.

Устройство паъляти машины фон Неймана имеет два существенных различия с Ь'-лентой. Бо-первых, в отличие от Б-ленты, устройство памяти содержит лишь кол*с:иное. число ячеек огралличенлшго размера, так что не лк>- бая вьглислимая по Тьк>рингу (Маркову, Посту, Черчу., Флойду, Тромпу и т. д.) функция вычислима на машине фон Неймана. Во-вторых, данные, записанные в ячейки устройства памяти, недоступны для непосредственного восприятия человеком.

Следовательно, в состав машины фон Неймана должны входить устройства записи сообщений в память (устройство ввода) и вывода данных из памяти на носитель, доступный лля восприяти;я органами чувств человека (устройство вывода). Все устройства ввода так или иначе преобразуют сообщения разного вида во внутримашинные данные (двоичные слова: именно фон Нейман предложил использовать двоичную систему счисления при атшаратпой реализации ЭВМ!). На>>ример, микрофон >й>еобразует люперечные звуковые колебания воздуха в релевантные аналоговые электрические сиплалы. Для их обработки цифровыми устройствами, эти сип|алы должны бытылреобразованы в дискретную форму звуковой платой. Современные устройства вывода способны воздействовать не только на зрение, но и на слух, обоняние, осязание, .вкус.

Кроме того, исллользуя инерцию орга>нов зрения, возможно создание движущихся изображений. По этой жс причине даже если бы мы смогли чувствовать дапньк, во внутримашиппом представлении, мы не поспевшли бы за их слишком быстрым изменении>ьл, Следовательно, язык описания программ для маплины фон Неймана должен содержать средства управления устройствами ввода и вывода, преобразующими сообщения в данные и наооорот. Итак, в результате аппаратной реализации процессора фон Неймана мы перешли от сообщений к данным, потеряв абсолк>тнук> вычислимость и лишивплись возможности непосредственно созерцать процесс обработки данных в ЭВМ и тем более участвовать в нем. Но приобретения более значительны; мы получили возможность быстрой и безошибочной автоматической обработки данных без участия человека.