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

- математическое понятие, описывающее взаимодействие автомата с внешней средой. Так, для автомата конечного внешней средой обычно является множество входных слов, а поведением - словарная функция, реализуемая автоматом, или событие (иногда сверхсобытие), представимое автоматом. Для автомата над термами (см. Автоматов алгебраическая теория).внешней средой является множество константных термов, а поведением - класс тех термов, значения к-рых, вычисляемые с помощью данного автомата, принадлежат выделенному подмножеству элементов соответствующей алгебры. Для мозаичных структур внешней средой является множество начальных конфигураций, а поведением - последовательности конфигураций, возникающих в тактовые моменты времени. Вообще, для большинства автоматов А. п. представляет собой ту или иную модификацию поведения конечных автоматов. Специальным случаем является так наз. А. п. в случайной среде. Под средой здесь можно понимать вероятностный автомат [img: http://localhost:8080/file/010105-109.jpg] преобразующий выходные сигналы рассматриваемого автомата [img: http://localhost:8080/file/010105-110.jpg] в его входные сигналы. Так что можно считать, что автомат [img: http://localhost:8080/file/010105-111.jpg] в случайной среде [img: http://localhost:8080/file/010105-112.jpg] представляет собой автономную логич. сеть, построенную из автоматов [img: http://localhost:8080/file/010105-113.jpg] путем соединения выхода каждого из этих автоматов со входом другого. Тогда поведение автомата [img: http://localhost:8080/file/010105-114.jpg] в случайной среде [img: http://localhost:8080/file/010105-115.jpg] можно рассматривать как функционирование указанной автономной логич. сети. Среда [img: http://localhost:8080/file/010105-116.jpg] наз. стационарной, если она является автоматом с одним состоянием. Если рассматривать выходные сигналы автомата [img: http://localhost:8080/file/010105-117.jpg] как различные "поощрения" или "наказания" автомата [img: http://localhost:8080/file/010105-118.jpg] то естественно возникает задача построения автомата [img: http://localhost:8080/file/010105-119.jpg] поведение к-рого в среде [img: http://localhost:8080/file/010105-120.jpg] является оптимальным, т. е. дает наибольший возможный в данной среде выигрыш. Обычно предполагается, что выходной алфавит среды [img: http://localhost:8080/file/010105-121.jpg] состоит из букв 0 и 1 и в ответ на выходные сигналы [img: http://localhost:8080/file/010105-122.jpg] автомата [img: http://localhost:8080/file/010105-123.jpg] буква 1 выдается, соответственно, с вероятностями [img: http://localhost:8080/file/010105-124.jpg] При этом "поощрением" автомата [img: http://localhost:8080/file/010105-125.jpg] считается только буква 1. Если среда [img: http://localhost:8080/file/010105-126.jpg] стационарна, то множество состояний автономной логич. сети совпадает с множеством состояний автомата [img: http://localhost:8080/file/010105-127.jpg] Если, кроме того, выходная буква автомата [img: http://localhost:8080/file/010105-128.jpg] однозначно определяется состоянием, то функционирование этой логич. сети может быть описано стохастич. матрицей [img: http://localhost:8080/file/010105-129.jpg] переходов состояний. Как правило, рассматривают случаи, когда матрица [img: http://localhost:8080/file/010105-130.jpg] эргодическая (см. Эргодичность). Тогда определена функция: [img: http://localhost:8080/file/010105-131.jpg] где [img: http://localhost:8080/file/010105-132.jpg] - сумма финальных вероятностей всех состояний, определяющих выходную букву [img: http://localhost:8080/file/010105-133.jpg] При этом [img: http://localhost:8080/file/010105-134.jpg] Если выходные сигналы автомата [img: http://localhost:8080/file/010105-135.jpg] не зависят от воздействий среды и равновероятны, т. о. [img: http://localhost:8080/file/010105-136.jpg] [img: http://localhost:8080/file/010105-137.jpg] то [img: http://localhost:8080/file/010105-138.jpg] Функция [img: http://localhost:8080/file/010105-139.jpg] является математич. ожиданием величины, наз. выигрышем автомата [img: http://localhost:8080/file/010105-140.jpg] в среде [img: http://localhost:8080/file/010105-141.jpg] Говорят, что автомат [img: http://localhost:8080/file/010105-142.jpg] обладает целесообразным поведением в среде [img: http://localhost:8080/file/010105-143.jpg] если [img: http://localhost:8080/file/010105-144.jpg] Задача об оптимальном поведении в случайной среде ставится следующим образом. Требуется построить так наз. асимптотически оптимальную последовательность автоматов [img: http://localhost:8080/file/010105-145.jpg] такую, что математич. ожидание выигрыша автомата [img: http://localhost:8080/file/010105-146.jpg] с ростом пстремится к максимальному выигрышу в данной среде, равному величине [img: http://localhost:8080/file/010105-147.jpg] [img: http://localhost:8080/file/010105-148.jpg] В рассматриваемом случае такую последовательность образуют так наз. автоматы с линейной тактике и при условии, что [img: http://localhost:8080/file/010105-149.jpg] [Автомат с линейной тактикой [img: http://localhost:8080/file/010105-150.jpg] с k- буквенным выходным алфавитом имеет kn состояний [img: http://localhost:8080/file/010105-151.jpg] [img: http://localhost:8080/file/010105-152.jpg] и следующие функции [img: http://localhost:8080/file/010105-153.jpg] переходов и выходов: [img: http://localhost:8080/file/010105-154.jpg] Впервые правила асимптотически оптимального поведения в стационарной случайной среде начали изучаться в математич. статистике. Однако получаемые там результаты естественно переводятся на язык теории автоматов. Рассматривается А. н. и в более сложных средах, а также поведение коллективов автоматов в случайных средах. В последнем случае автоматы рассматриваются как игроки, а правила игры, в к-рой участвуют эти автоматы, выступают в роли среды.