Автомат Неймана

По принципу обработки информации вычислительное устройство, предложенное Нейманом (автомат Неймана – АН), существенно отличается от машины Тьюринга.

Важная особенность машины Тьюринга – преобразование информации на каждом такте происходит лишь в одной ячейке, остальные дожидаются посещения головки, хотя часто имеется возможность работать параллельно.

Простейшее решение – использование нескольких машин Тьюринга с общей для них внешней памятью (лентой) – не всегда допустимо из-за возможных конфликтов при обращении к одной и той же ячейке памяти.

В автомате Неймана число одновременно обрабатываемых ячеек может неограниченно расти, оставаясь в каждый момент конечным.

Элемент Неймана (ЭН) – это устройство, которое на каждом такте пребывает в одном из конечного числа состояний r_i R, образующих его алфавит. ЭН имеет два входных канала: левый и правый; по каждому из них на такте t также поступает по одному состоянию из R (рис. 2).

Рис. 2. Элемент Неймана

Элемент реализует функцию z_t+1= (r_i, r_j, r_m)_t, то есть в такте t+1 переходит в состояние z, определяемое его состоянием в текущий момент времени и значениями, поступившими по входным каналам.

Состояния элементов Неймана в момент времени t определяют конфигурацию автомата Неймана (рис. 3) в момент t: K(t).

Рис. 3. Структура автомата Неймана

Функционирование АН – это переход от состояния К(t) к состояниям K(t+1), K(t+2)...

За один такт свое состояние может менять большое число элементов Неймана, что фактически приводит к параллельной обработке информации.