d1. Информация <–> d2. Системы счисления <–> d3. Обработка информации <–> d4. Дискретные сообщения
d4. Формальный алгоритм <–> d5. НАМ, т. Шеннона <–> d6. Сочетания алгоритмов <–> d7. УМТ <–> d8. Машина фон Неймана
Нормированность вычислений означает, что в процессе выполнения программы часть ленты остаётся пустой.Имя — слово, сопоставленное с адресом значения с помощью таблицы имён.Отношения — объекты операций, или операции, которые по допустимым словам (аргументам отношения) вычисляют логическое значение Истины или Лжи.Местность — количество операндов, или постоянное количество аргументов каждого отношения.S-лента — хранит программу и её данные.R-лента — хранит операнды перед выполнением операции.D-лента — хранит программы операций.Машина фон Неймана — аппаратная реализация процессора фон Неймана.Мы доказали, что МТ может быть записана на OСТ, а дальше там один шаг до внедрения в компьютер (в режиме отладки/интерпретации).
© На машине Тьюринга далеко не уедешь.
1) Описание программы для сложения двух дробей занимает целую страницу, с учетом того, что почти все программы МТ,
через которые выполнен алгоритм, объявлены библиотечными.
2) Второй недостаток языка ОСТ — необходимость многочисленных копирований.
Копирования могут составлять около половины всех действий соответствующих МТ.
Это увеличивает время работы и усложняет читаемость программы, т.к. каждое слово встречается на ленте в нескольких экземплярах.
3) Ещё один недостаток — необходимость выписывать ситуации на ленте, иначе можно легко запутаться в расположении данных и будут ошибки в алгоритме.
Недостатки обусловлены свойствами МТ — основной модели вычислений.
Громоздкость описаний обусловлена буквальной обработкой данных МТ.Т.е. длина описания программы пропорциональна числу букв сообщения.
Частые копирования обусловлены способом нормированных вычислений:
каждое неэлементарное действие выполняется над крайними правыми словами ленты.
Постоянное слежение за ситуациями на ленте связано с постоянными изменениями положений рабочей головки.
Язык ОСТ удобен для построения математической теории алгоритмов, но не для программирования.
Для программирования нужна более совершенная модель, которая была построена в 1940-ых годах Джоном фон Нейманом (усовершенствование МТ).
Нормированность вычислений означает, что в процессе выполнения программы часть ленты остаётся пустой.Д, за которым будет эта пустота.Все данные, полученные в результате работы, хранятся в ячейках ленты. Будем отсчитывать номера ячеек от некоторой фиксированной ячейки.
адресом. Каждому значению на ленте ставится в соответствие с его положением адрес, и он не меняется во время работы программы.Адреса в явном виде нигде не записываются. Понятие адреса вторично: оно задано конструктивным образом, т.к. адрес может быть сгенерирован по известному алгоритму — вручную посчитать слова на ленте.
В программе могут встречаться переменные и константы. Значения переменных могут меняться в процессе выполнения программы, а значения констант не могут.
адресов переменных и адресов констант.Текст программы станет более понятным, если вместо адресов значений использовать их имена.
Имя — слово, сопоставленное с адресом значения с помощью таблицы имён.Таблицу имён расположим перед программой и введём символ Т.
Выходит, что текст программы расположен между символом таблицы имён Т и границой Д на ленте.
В программах широко используются внешние МТ.
Они программируются и записываются на D-ленту до их применения в программе.
Следовательно, они должны реализовывать действия, применимые при большого класса программ.
Например, простейшие математические действия над целыми числами.
Арифметический процессор — универсальная МТ, D-лента которой содержит программы для выполнения арифметических действий над целыми числами (в сравнении с пустой лентой УМТ), причем описываемые более простыми программами.Каждая операция применяется к одному или нескольким словам над рабочим алфави-
том процессора, называемых операндами.
Количество операндов определяет местность операции (операция сложения имеет два операнда и является двуместной).
Операция выполняется нормированно: результат помещается за операндами.
До выполнения операции операнды помещают в требуемом порядке перед свободным краем ленты, иначе результат
запишется на месте слов, которые нужно сохранить.
Упрощение достигается использованием свободного края ленты (за ячейкой с символом Д).
Его мы назовём R-лентой. На неё помещаем операнды перед выполнением операции.
На S-ленту будем записывать программу и все данные.
Перенормируем операции так, чтобы результат также помещался на R-ленте не вслед за операндами, а вместо них.
Для построения процессора необходимо:
1) Выбрать рабочий алфавит процессора (множество первых p неотрицательных чисел, начиная с нуля).
2) Зафиксируем множество конечных и бесконечных допустимых слов, а также зафиксируем их длину.
переполнения — T (его длина больше фикс. длины);боттом или неопределённость — перевёрнутая T (неопределенное значение операнда).3) Запишем на D-ленту программы операций процессора.
4) Сообщим обозначения операций управляющей программе этой УМТ, на основе которой построен процессор.
Отношения — объекты операций, или операции, которые по допустимым словам (аргументам отношения) вычисляют логическое значение Истины или Лжи.Местность — количество операндов, или постоянное количество аргументов каждого отношения.Отношения связывают числовые операнды, имеют истинностные значения и не являются операциями, т.к. размыкают множество допустимых операндов.
Процессоры могут использоваться по отдельности или вместе. В последнем случае необходимо уточнить понятие согласованности.
Определение 2.9.1
При согласовании процессоров их S-ленты объединяются.
двуленточный процессор, состоящий из управляющего устройства, S-ленты, двух R-лент и двух D-лент.Отметим, что каждая из двух лент двулеиточного процессора содержит операцию перениен слов с «чужой» А-ленты на’ «евою» © одновременным их преобразованием К «своему» допустимому виду
Несколько попарно согласованных процессоров образуют п-ленточный процессор.
Процессор фон Неймана объединяет D-ленты многоленточного процессора и способен выполнить все операции объединённых D-лент за счет своего УУ.
Исполнение программы — перенос операндов с S-ленты на одну из R-лент или с одной R-ленты на другую, выполнение операций над операндами,
и запись результатов операций на S-ленту.
S-лента — хранит программу и её данные.R-лента — хранит операнды перед выполнением операции.D-лента — хранит программы операций.Машина фон Неймана — аппаратная реализация процессора фон Неймана.Устройство:
S-ленты)R-лент).Устройство памяти:
1) содержит конечное число ячеек ограниченного размера (в отличие от S-ленты процессора фон Неймана)
Поэтому не любая ВТ-функция вычислима на машине фон Неймана.
2) Данные в ячейках памяти, недоступны для непосредственного восприятия человеком.
3) Язык описания программ машины фон Неймана содержит средства управления устройствами ввода и вывода, преобразующими сообщения в данные и наоборот.
Преимущества аппаратной мфн:
Вычислимый по фон Нейману — может быть получен за приемлемое время на ограниченных ресурсах памяти.Современной машиной фон Неймана можно считать языки программирования высокого уровня.