АВТОМАТА ПОВЕДЕНИЕ

Расстановка ударений: АВТОМА`ТА ПОВЕДЕ`НИЕ

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

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

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

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

Если выходные сигналы автомата не зависят от воздействий среды и равновероятны, т. е. σ₁ = σ₂ =... = σ_k = 1/k, то

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

φ (s_ij, 1) = s_{i, j + 1}, если j = 1, 2, ..., n - 1, φ (s_in, 1) = s_in, φ (s_ij, 0) = s_{i, j - 1}, если j = 2, ..., n, φ (s_i1, 0) = s_{i + 1, 1}, ψ (s_ij, a) = b_i, i = 1, ..., k, j = 1, ..., n.]

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

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

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

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

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.