АВТОМАТ РЕГИСТРОВЫЙ

— специального вида автомат(как правило, бесконечный), введенный как математическая модель, более близкая к структурам современных цифровых вычислительных машин. В основе определения А. p. лежит понятие регистра. Регистром (точнее, -позиционным регистром) наз. мн-во переменных (элементов регистра) с одной и той же -элементной областью определения Р, занумерованных последовательными целыми числами и упорядоченных в соответствии с этой нумерацией.

В реальных машинах любой регистр состоит из конечного числа элементов. Однако в некоторых ситуациях более удобно считать их бесконечными. Если для нумерации элементов регистра использованы все целые рациональные числа (положительные и отрицательные), то регистр наз. двусторонним. Если для нумерации использованы все числа интервала или , то регистр наз. односторонним бесконечным регистром.

Состояниями регистра наз. всевозможные наборы значений (состояний) его элементов. Для задания преобразований мн-ва состояний регистров используются преобразования периодически-определенные. Каждое такое преобразование задается -значной ф-цией и базовым ур-нием определяющими значение переменной регистра после выполнения преобразований через значения . его переменных до выполнения преобразования. Набор чисел базой периода. Для бесконечного регистра в обе стороны базовое ур-ние однозначно определяет преобразование. В случае же бесконечного в одну сторону или конечного регистра может иметь место краевой эффект, когда часть или все аргументы при некоторых i выходят за пределы рассматриваемого регистра. В этих случаях рассматриваемый регистр дополняется фиктивными элементами, принимающими всегда постоянные значения.

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

Абстрактная модель центрального процессора вычислительной машины: А — управляющий автомат, В — операционный автомат.

При этом ур-ния должны быть корректными, т. е. однозначно определять результат выполнения преобразования.

Кроме указанных двух типов преобразований, применяются еще т. н. конечно-определенные преобразования, меняющие состояние только конечного числа переменных регистра, и установочные преобразования, переводящие регистр из любого состояния в некоторое фиксированное для данного регистра состояние.

Все преобразования рассмотренных типов легко переносятся на случай нескольких регистров. В этом случае можно определить мн-во состояний и ф-цию переходов А. р. В. Этот автомат состоит из некоторого конечного набора регистров и состояниями его являются наборы состояний регистров. Каждому входному сигналу входного алфавита Y автомата В соответствует некоторое преобразование мн-ва В одного из указанных типов. Для задания ф-ции выходов А. р. рассматривают разбиение Г мн-ва его состояний на попарно непересекающиеся классы и рассматривают ф-цию выходов как ф-цию, зависящую только от класса, которому принадлежит состояние автомата и входного сигнала. Разбиение Г обычно выбирается конечным, а его классы получаются путем применения булевых операций к т. н. допустимым мн-вам. К этим мн-вам етносятся прежде всего конечно-определенные мн-ва, т. е. такие, в которых заданные элементы некоторого регистра (в конечном числе) принимают заданные значения. Вообще допустимыми являются также мн-ва, в которых заданный регистр содержит определенную конечную конфигурацию значений переменных или в состоянии его заданная конфигурация периодически повторяется. Построенный т. о. автомат наз. многорегистровым конфигурационно периодическим автоматом.

Применяя указанную концепцию бесконечного автомата, можно построить абстрактную модель центр, процессора вычисл. машины. Эта модель представляет собой композицию двух автоматов — автомата управляющего А и автомата операционного В (рис.). Управляющий автомат А является автоматом конечным, операционный автомат В — бесконечным конфигурационно периодическим автоматом. К автомату В добавляют обычно еще входной канал сигналы в котором вызывают установочные преобразования, и выходной канал V, по которому передаются состояния некоторых регистров операционного автомата. Сигналы алфавита V вызывают только периодически-определенные преобразования (возможно, со вспомогательными переменными). Эти сигналы также разрешают или запрещают поступление сигналов по каналу U. Сигналы в каналах U и V наз. также векторными. Эти каналы связывают центр, процессор с внеш. устр-вами, напр., оперативным запоминающим устройством ЦВМ.

В автомате А обычно легко выделить состояния, в которых начинается или заканчивается выполнение той или иной макрооперации машины (сложение, умножение и т. д.). Выбирая такие состояния в качестве начального и заключительного, получаем дискретный преобразователь, действующий на мн-ве состояний операционного автомата В. Элементарные операторы этого преобразователя являются микрооперациями процессора.

С теорией А. p., основы которой заложил сов. математик В. М. Глушков (p. 1923), тесно связана теория автоматов итеративных. Лит.: Глушков В. М. Теория автоматов и вопросы проектирования структур цифровых машин. «Кибернетика», 1965, Кг 1. А. А. Летичевский.