АВТОМАТЫ ИТЕРАТИВНЫЕ

— логические сети, состоящие из одинаковых элементов — конечных автоматов, соединенных некоторым регулярным образом. Понятие А. и. можно считать обобщением понятия Тьюринга машины. В этой машине информация, записанная на ленте, подвергается в каждый такт работы машины локальным изменениям, т. е. меняется состояние не более чем одной ячейки ленты. Заменяя это требование локальности требованием иовсеместности, параллельности вычислений в каждой ячейке, приходят к понятию одномерного А. и., если ячейку ленты рассматривать как автомат конечный, а буквы, записываемые в ячейку, — как состояния этого автомата. Состояние любой ячейки ленты в момент времени однозначно определяется состоянием этой ячейки и состояниями двух соседних с ней ячеек в момент t (рис. 1). Такое обобщение машины Тьюринга, включая также рассмотрение двумерных и многомерных структур, впервые предложили амер. математики Дж. фон Нейман (1903—57) и А. Черч (р. 1903). Поэтому такого рода автоматы часто наз. автоматами Неймана — Черча. В частности, фон Нейман, изучая вопросы самовоспроизведения в теории автоматов (см. Автомат самовоспроизводящийся), рассматривал плоскость, разбитую на равные квадраты (двумерную, или плоскую, «ленту»), в каждом из которых помещался экземпляр заданного конечного автомата, причем каждый такой -земпляр соединялся только с четырьмя своими соседями (рис. 2).

1. Схема одномерного итеративного автомата.

2. Схема двумерного итеративного автомата.

Он же впервые выдвинул общее требование однородности структуры автомата, которому удовлетворяют А. и. Оно заключается в том, что все элементы автомата должны быть «равноправны», ни один из них не должен получать никакого преимущества

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

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

Рассматривались различные способы ввода внеш. информации в А. и. Так, напр., амер. математик Ф. Хенни, изучая преобразования и распознавание пространственных образов на А. и., т. е. прямоугольных массивов из нулей и единиц (или в общем случае n-мерных «параллелепипедов» — из нулей и единиц), предполагал, что каждая компонента образа поступает на соответствующую ячейку А. и. Процесс «обработки» образа происходит до наступления устойчивого состояния А. и., в котором выдается результат. При этом предполагается, что в процессе вычисления остальные ячейки А. и. находятся в состоянии покоя и в них не поступает никакой внеш. информации. Др. словами, А. и. функционирует как конечная итеративная сеть, размер которой ограничен входным образом. Хенни получил много результатов о свойствах А. и., связанных с такого рода вычислениями. Он показал алгоритм, неразрешимость многих проблем в теории А. и.; дал методы синтеза А. и., распознающих некоторые классы образов. Возможен и др. способ ввода внеш. информации, когда она поступает последовательно на специально выделенную ячейку или группу ячеек.

Дж. фон Нейман рассматривал А. и., как автоматы растущие, следующим образом: ячейка А. и. в числе др. внутр. состояний имеет т. н. состояние покоя А, которое характеризуется тем, что если некоторая ячейка и все ее непосредственные соседи в момент t находятся в состоянии Л, то в момент данная ячейка также будет находиться в А. Находящуюся в состоянии покоя ячейку можно рассматривать как несуществующую. Если в начальный момент времени конечное число ячеек находится в состояниях, отличных от Л (такая совокупность ячеек с указанием состояния каждой из них наз. конфигурацией), а все остальные ячейки — в Л, то эта конфигурация может «расти» за счет «присоединения» новых ячеек, т. е. ячеек, вышедших из состояния Л. Как показал амер. математик Э. Мур, для очень широкого класса А. и. существуют такие конфигурации, называемые «райскими садами», которые не могут быть созданы никакой др. конфигурацией (т. е. такие, которые могут существовать только в начальный момент времени). Польский математик С. Улам исследовал экспериментальным путем на ЦВМ многообразие конфигураций, которые можно получить в дву- и трехмерных А. и. из достаточно простых исходных конфигураций при простых правилах функционирования А. и. Такие исследования, по мнению Улана, могут пролить свет на вопрос о том, сколько «информации» необходимо для описания структур живых организмов, имеющих но виду чрезвычайно сложное строение. А. и, обладают рядом свойств, делающих их весьма интересными с инженерной точки зрения. Прежде всего, это технологичность: достаточно спроектировать только один элемент — ячейку. Соединения элементов между собой простые, что позволяет легко наращивать сеть до нужных размеров, не перестраивая уже имеющихся в ней соединений. А это облегчает обслуживание таких сетей. На А. и. легко «распараллеливать» некоторые вычисления. Структуры, аналогичные А. и., обнаружены в живой природе (напр., сетчатка глаза, некоторые области коры головного мозга, молекулы ДНК и т. п.). Примерами применения итеративных структур в вычислительной технике могут служить устр-ва памяти ЦВМ, а также регистры и сумматоры. В связи с развитием Технологии интегральных схем, где сама специфика производства такова, что там удобно строить устр-ва с итеративной структурой, интерес К теории А. и. все возрастает.

С теорией А. и. тесно связана теория т. н. автоматов регистровых, основы которой заложил сов. математик В. М. Глушков. Она направлена на изучение микропрограммирования ЦВМ.

Лит.: Глушков В. М. Теория автоматов и формальные преобразования микропрограмм. «Кибернетика», 1965, № 5; Барздинь Я. М. Моделирование логических сетей на автоматах Неймана — Черча. «Проблемы кибернетики», 1966, в. 17; Мур Э. Ф. Математические модели самовоспроизведения. — Улам С. Некоторые математические проблемы, связанные с процессом роста фигур. В кн.: Математические проблемы в биологии. Пер. с англ. М., 1966; Henriie F. С. Iterative arrays of lagical circuits. New York - London, 1961. М. if. Кратко, Г. С. Плесневич.