АВТОМАТЫ БЕСКОНЕЧНЫЕ

— автоматы, м-во состояний которых является бесконечным. Формально А. -это пятерка , где X и У — соответственно входной и выходной алфавиты (они могут быть как конечными, так и бесконечными), А — мн-во состояний автомата (бесконечное), - ф-ция переходов и к: У — ф-ция выходов автомата. Чаще всего рассматриваются А. б. с конечными входным и выходным алфавитами и счетным мн-вом внутр. состояний. Для класса всех А. б. еще не удалось получить значительных результатов, что объясняется чрезмерной общностью понятия А. б. Такие результаты имеются для отдельных специально выделенных классов А. б. Выделение этих классов А. б. идет, в основном, по двум направлениям: а) автомат рассматривается как абстрактный автомат, т. е. пятерка , где мн-во А является некоторой матем. структурой (по Н. Бурбаки), напр., пространством линейным, топологическим, метрическим, группой и т. п., а ф-ции и к являются некоторыми естественно определяемыми в этих терминах ф-циями или операторами, напр., операторами линейными; б) автомат задается в структурном виде, т. е. как автомат, реализованный в той или иной сети логической. Структура логич. сети и ее элементы определяют структуру мн-ва А и операций 8 и 1. Такое выделение классов А. б. является преобладающим в исследованиях по теории А. б. А. б., заданные в структурном виде, часто наз. абстрактными машинами (напр., Тьюринга машина). Изучают их в связи с возможностью выполнения на них тех или иных классов алгоритмов. Считают, что само понятие алгоритма может быть уточнено только на основе понятия А. б. (см. Автоматы растущие). Хотя все реальные дискретные устр-ва, предназначенные для переработки информации, могут иметь только конечное число внутр. состояний, т. е. их абстрактными моделями являются автоматы конечные, тем не менее бывает удобно рассматривать один А. б. как модель целого класса таких устройств. Это позволяет выявить общие закономерности, имеющие место для всех таких устр-в, и зачастую имеет большое прикладное значение. Примером могут служить автоматы регистровые.

А- б. широко изучают в теор. кибернетике, в алгоритмов теории, лингвистике математической и др.

Лит.: Глушков В. М. Теория автоматов и вопросы проектирования структур цифровых машин. «Кибернетика», 1965, Ml; Мальцев А. И. Алгоритмы и рекурсивные функции. М., 1965 [библиогр. с. 375—381]; Arbib М. A. Automata theory and control theory - a rapprochement. «Automatica», 1966, v. 3; Hоpсгоft J. E., Oilman J. D. An approach to a unified theory of automata. «The bell system technical journal», 1967, v. 46, № 8.

М. И. Кратка.