Автомата поведение

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

Специальным случаем является так называемое А. п. в случайной среде. Под средой здесь можно понимать вероятностный автомат В, преобразующий выходные сигналы рассматриваемого автомата M в его входные сигналы. Так что можно считать, что автомат M в случайной среде B представляет собой автономную логическую сеть, построенную из автоматов M и B путем соединения выхода каждого из этих автоматов со входом другого. Тогда поведение автомата M в случайной среде B можно рассматривать как функционирование указанной автономной логической сети. Среда B называется стационарной, если она является автоматом с одним состоянием. Если рассматривать выходные сигналы автомата B как различные <<поощрения>> или <<наказания>> автомата M, то естественно возникает задача построения автомата M, поведение которого в среде B является оптимальным , т.е. дает наибольший возможный в данной среде выигрыш. Обычно предполагается, что выходной алфавит среды B состоит из букв 0 и 1 и в ответ на выходные сигналы b₁,…,b_k автомата M буква 1 выдается, соответственно, с вероятностями p₁,…,p_k. При этом <<поощрением>> автомата M считается только буква 1.

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

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

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

Функция W(M,B) является математическим ожиданием величины, называется выигрышем автомата M в среде B. Говорят, что автомат M обладает целесообразным поведением в среде B, если W(M,B)> W₀. Задача об оптимальном поведении в случайной среде ставится следующим образом. Требуется построить так называемую асимптотически оптимальную последовательность автоматов M₁,M₂… такую, что математическое ожидание выигрыша автомата M_n с ростом n стремится к максимальному выигрышу в данной среде, равному величине . В рассматриваемом случае такую последовательность образуют так называемые автоматы с линейной тактикой при условии, что . [Автомат с линейной тактикой M_n с k- буквенным выходным алфавитом имеет kn состояний s_ij, i=1, .., k, j=1,…, n, и следующие функции φ и ψ переходов и выходов:

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

Лит.: [1] Барздинь Я. М., Трахтенброт Б. А., Конечные автоматы (Поведение и синтез), М., 1970; [2] Цетлин М. Л., Исследования по теории автоматов и моделированию биологических систем, М., 1969; [3] Robbins H., <>, 1956, v. 42, Л1 12, p. 920 923. В.Б.