Алгебраические модели вычислительных машин

Исследования, посвященные построению и анализу математических моделей цифровых вычислительных машин, развиваются в последнее время преимущественно в двух направлениях. Основу первого направления составляет предложенный В. М. Глушковым метод изучения процессов преобразования дискретной информации с точки зрения теории автоматов. Второе направление связано с работами А. А. Ляпунова, А. П. Ершова, Н. И. Глебова, а также ряда других математиков. В этих работах математические модели вычислительных машин рассматриваются с позиций общей алгебры. Сюда примыкает также ряд работ, посвященных различным способам формализации понятия программы вычислительной машины (эти вопросы подробно рассмотрены в обзоре A. П. Ершова и А. А. Ляпунова [26]).
Настоящий обзор (без претензий на исчерпывающую полноту) посвящен способам построения и исследования автоматно-алгебраических и алгебраических моделей вычислительных машин. При этом основное внимание уделяется методам построения соответствующих моделей. В заключение авторы описывают один способ модификации алгебраической модели, учитывающей некоторые элементы строения машины и вопросы функционирования вложенной в ее память программы.
От читателя предполагается знакомство лишь с некоторыми из основных понятий общей алгебры (полугруппа, изоморфизм, частично упорядоченное множество и т. д.). Эти сведения можно найти, например, в книге А. Г. Куроша [35].