Лекции по "Алгебре"

Раздел 5. Понятие простейших автоматов

                                                                                                  Подражанье, повторенье – мира этого дела

                                                                                                  Если бы не повторенье, жизнь бы праздником была

                                                                                                  Награждались бы старанья, исполнялись бы желанья

                                                                                                  А возмездия угроза бесполезная спала.

                                                                                                                Омар Хайам                                                                                                               

Тема 5.1 Основные понятия и определения

Предположим, что существует несколько логических переменных u1…ur, и будем рассматривать их как вектор U. Пусть f – логическая функция от этих переменных, образующая некое сложное логическое высказывание

                                          q=f(U)

Будем рассматривать q как выходную величину РКС, реализующую логическую функцию f.

РКС, встречающиеся на практике, как правило, имеют не один выход а несколько, и каждый выход реализует свою логическую функцию.

Будем считать, что РКС осуществляет логические операции мгновенно, т.е. если в момент времени t на вход схемы поступает вектор U, то соответствующее значение q=f(u) получится на выходе в тот же самый момент времени. Для описания работы РКС во времени удобно ввести понятие дискретного времени. Т.е. физическое понятие бесконечно, равномерно, и непрерывно текущего времени мы заменим точечными моментами времени, считая, что все изменения происходят именно в эти моменты, и между ними не происходит никаких изменений. Более того, считаем, что длина этих промежутков настолько мала, что этим значением можно пренебречь. На оси t отметим моменты, в которые входная величина может претерпеть изменения t1, t2, …, tn. Эти величины называются тактами.  Уравнения q[n]=f(u(n)], где n –n-тый такт, описывает работу РКС во времени. РКС является простейшим видом конечных автоматов – конечный автомат без памяти.

Конечные автоматы принято задавать не уравнениями, а таблицами переходов и выходов или графом переходов конечного автомата. В таблице переходов строки соответствуют различным входным сигналам, а столбцы – различным состояниям автомата. На пересечении строки и столбца указывается состояние, в которое переходит автомат.

Другим способом задания конечного автомата, обеспечивающим большую наглядность, является задание автомата с помощью направленного графа. Вершины графа – это возможные состояния автомата. Вершины i,k соединяются дугами тогда и только тогда, когда существует сигнал, переводящий автомат из состояния i в состояние k, при этом дуга помечается значением сигнала U и в скобках указывается значение выходного сигнала q.

Сигнал U мы будем называть влиянием среды. Среда описывается вероятностью выпадания того или иного события. Т.е. среда Е описывается множеством своих состояний D и вероятностью наступления именно этого состояния Р. Будем считать.

Тема 5.2 Понятие стационарной и динамической среды.

Прежде чем начать конструировать и описывать какие-либо автоматы, определим такое фундаментальное понятие теории простейших автоматов, как понятие среды. В отличии от естественных наук, в теории простейших автоматов среде интересует нас только с одной точки зрения: реакции на действие нашего автомата. Значение оценок действий автомата описывается некоторым конечным множеством D = {d1, d2, …dn}. Если наш автомат может сделать на i-том такте одно из m действий, то среда описывается матрицей вероятностей А(m, n). В которой А(i. j) = вероятности выпадения j – той реакции среды (dj) на i – тое действие автомата. Если с течением времени значение матрица А остаются неизменными, то среда называется стационарной.

Такую интересную трактовку поведения биологических организмов и описания условий существования этих организмов предложил блестящий советский математик и инженер М.Л. Цетлин. Суть гипотезы простоты Цетлина сводится к тому, что любое достаточно сложное поведение слагается из совокупности простых поведенческих актов. Их совместная реализация и простейшее взаимодействие со средой приводят в результате к весьма сложным поведенческим процессам.

Приведем один из простейших биологических экспериментов, на основе изучения результатов которых Цетлин и создавал свои первые автоматы. В биологии эти опыты известны как опыты Йеркса. В начале опыта дождевой червь помещался на ярко освещенную площадку «Т-образного» лабиринта. Червь начинал движение с целью найти более комфортные условия существования. Там где коридор имел разветвление, червь имел выбор из двух альтернатив. Конечно, червь не мог знать, что по дороге в левом коридоре включено электрическое поле, а заканчивается коридор раздражающей червя солевой ванночкой. В то время как правый коридор приводит червя в затемненную влажную камеру, где он чувствовал себя превосходно.

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

С точки зрения Цетлина общая схема этого опыта выглядит таким образом.

Каким же образом описывается этот автомат и его среда обитания. У нашего автомата есть два возможных действия: {«Направо», «Налево»}, среда также имеет две реакции:{«Наказание», «Поощрение»}. Матрица вероятностей будет выглядеть так:

Немного изменим условия опыта. Эти опыты описаны Торндайком. В такой же, как и в первом опыте, Т-образный лабиринт помещается крыса. В конце и правого, и левого коридора помещена пища. Но по дороге к пище в обоих коридорах крысу ждут неприятные ощущения от раздражения электрическим током. Эти раздражения происходят с фиксированной вероятностью Рп и Рл, которые не меняются в процессе одной серии опытов. Цель эксперимента – определить, сможет ли крыса в процессе обучения научиться выбирать тот коридор, ведущий к пище, в котором вероятность электрического раздражения меньше. При ощутимой разнице между Рп и Рл , после более или менее длительного обучения крысы правильно оценивали эту разницу и принимали целесообразное решение о выборе маршрута. Матрица вероятностей для этого опыта будет выглядеть так:

С точки зрения теории простейших автоматов в обоих случаях рассматривается пример стационарной среды. Но такой мир возможен только в эксперименте. Процессы, протекающие в природе, значительно сложнее и разнообразнее. Как описать их?

С описанием более сложных сред обитания и «жизни» автоматов связано понятие динамической среды. Поскольку законы изменения параметров внешней среды могут быть очень различными мы рассмотрим самый простой способ описания динамической среды. Будем рассматривать динамическую среду как набор конечного числа стационарных сред, описанных уже известным нам способом, Е1 , Е2 … Еk . И будем считать, что каждая из этих сред представляет собой моментальную фотографию состояния динамической среды. Эти фотографии, меняясь, как кадры кинофильма, воссоздают нам динамическую среду. Схема взаимодействия автомата с такой средой выглядит так:

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

Мы рассмотрим только один, наиболее хорошо изученный, частный случай работы коммутатора. Будем считать, что коммутатор производит переключение сред, руководствуясь некоторой квадратной матрицей. Назовем ее вероятностной матрицей переключения сред Т. Тij – вероятность перехода от Еi  к Еj на следующем шаге. По законам теории вероятностей

i  ΣjТij = 1

Такую динамическую среду еще называют переключающейся.

Тема 5.3 Понятие целесообразности поведения автомата.

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

Лиса вернулась с богатой добычей. Часть ее насытила лисий выводок, а оставшуюся пищу лиса прячет «на черный день». Тщательно роет яму, кладет в нее мясо и засыпает ее землей. Наблюдая за поведением лисицы, можно прийти к выводу, что цель действий лисицы порождена ее «интеллектом». Столь целесообразно и «разумно» ее поведение.

Но судьба нашей героини оказалась не очень счастливой. Она попала в западню и стала жительницей зоопарка. Теперь ей уже не приходится тратить силы на добывание пищи. Ее кормят служители. Но что делать лисице, когда пищи избыток? Конечно, прятать! И лиса скребет когтями бетонный пол вольера, а через некоторое время, когда «яма» готова, «прячет» в нее мясо. И после этого перестает замечать остаток трапезы, который, конечно, так и остается лежать на полу вольера. Лиса просто игнорирует его, не видит «зарытое» мясо. То, что в привычной для животного среде выглядело целесообразным, в условиях другой реальности становится лишенным каких-либо черт разумности.

Такие узко специализированные действия, тесно связанные с типовой ситуацией в окружающем мире, принято называть рефлексами. Чем проще организован организм, тем жестче схема рефлекса. Тем нелепее выглядит его поведение в изменившейся среде.

Как же оценивать целесообразность поведения искусственно сконструированных автоматов? Для этого заменим наш автомат устройством равновероятного выбора действий. На каждом шаге своего функционирования этот механизм, никак не учитывая приходящих на его вход сигналов «штраф» - «поощрение», с одинаковой вероятностью, равной 1/n, выбирает одно из доступных ему действий.