Математическая энциклопедия - автомата поведение

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

Специальным случаем является так наз. А. п. в случайной среде. Под средой здесь можно понимать вероятностный автомат преобразующий выходные сигналы рассматриваемого автомата в его входные сигналы. Так что можно считать, что автомат в случайной среде представляет собой автономную логич. сеть, построенную из автоматов путем соединения выхода каждого из этих автоматов со входом другого. Тогда поведение автомата в случайной среде можно рассматривать как функционирование указанной автономной логич. сети. Среда наз. стационарной, если она является автоматом с одним состоянием. Если рассматривать выходные сигналы автомата как различные "поощрения" или "наказания" автомата то естественно возникает задача построения автомата поведение к-рого в среде является оптимальным, т. е. дает наибольший возможный в данной среде выигрыш. Обычно предполагается, что выходной алфавит среды состоит из букв 0 и 1 и в ответ на выходные сигналы автомата буква 1 выдается, соответственно, с вероятностями При этом "поощрением" автомата считается только буква 1.

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

где сумма финальных вероятностей всех состояний, определяющих выходную букву При этом

Если выходные сигналы автомата не зависят от воздействий среды и равновероятны, т. о. то

Функция является математич. ожиданием величины, наз. выигрышем автомата в среде Говорят, что автомат обладает целесообразным поведением в среде если Задача об оптимальном поведении в случайной среде ставится следующим образом. Требуется построить так наз. асимптотически оптимальную последовательность автоматов такую, что математич. ожидание выигрыша автомата с ростом пстремится к максимальному выигрышу в данной среде, равному величине В рассматриваемом случае такую последовательность образуют так наз. автоматы с линейной тактике и при условии, что [Автомат с линейной тактикой с k- буквенным выходным алфавитом имеет kn состояний и следующие функции переходов и выходов:

Впервые правила асимптотически оптимального поведения в стационарной случайной среде начали изучаться в математич. статистике. Однако получаемые там результаты естественно переводятся на язык теории автоматов.

Рассматривается А. н. и в более сложных средах, а также поведение коллективов автоматов в случайных средах. В последнем случае автоматы рассматриваются как игроки, а правила игры, в к-рой участвуют эти автоматы, выступают в роли среды.

Лит.:[1] Барздинь Я. М., Трахтенброт Б. А., Конечные автоматы (Поведение и синтез), М., 1970; [2] Цетлин М. Л., Исследования по теории автоматов и моделированию биологических систем, М., 1969: [3] Bobbins H., "Ргос. Nat. Acad. Sci. U.S.A.", 1956, v. 42, № 12, p. 920-923.

В. Б. Кудрявцев, Ю. И. Янов.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985