Автомат

АВТОМАТ – управляющая система, являющаяся  автоматом конечным или некоторой его модификацией, полученной путём изменения компонент или функционирования. Основное понятие – конечный А. – возникло в середине 20 века в связи с попытками описать на математическом языке функционирование нервных систем, универсальных вычислительных машин и других реальных А., предпринятыми впервые У. Мак-Каллоком и У. Питтсом (W. McCulloch, W. Pitts, 1943), С. К. Клини (S. C. Kleene, 1951), А. Бёрксом и Дж. Райтом (A. W. Burks, 1954, J. Wright) и др. Характерной особенностью такого описания является дискретность соответствующих математических моделей и конечность областей значений их параметров, что приводит к понятию конечного А.  При этом внешние воздействия, реакции и состояния рассматриваются как буквы трех алфавитов А, S называемые, соответственно, входным алфавитом, выходным алфавитом и алфавитом состояний. Тогда законы их взаимодействия могут быть заданы двумя функциями – функцией переходов и функцией выходов, отображающими пары «состояние – входная буква» в состояния и выходные буквы, соответственно. В каждый из моментов дискретного времени устройство, находящееся в определенном состоянии, воспринимает входной сигнал – букву входного алфавита, выдает выходной сигнал – букву выходного алфавита, определяемую функцией выходов, и переходит в новое состояние, определяемое функцией переходов. Наряду с понятием конечного А. рассматриваются различные его обобщения и модификации, отражающие те или иные особенности реальных устройств. Для конечного А.  (А, С, В, φ, ψ)  существующие модификации можно разбить на следующие три основные группы. К первой группе относятся А., у которых некоторые из алфавитов A, S  или B бесконечны, в связи с чем такие А. называются  бесконечными . Ко второй группе относятся А., у которых вместо функций   φ и   ψ допускаются произвольные отношения или случайные функции. Таковы частичные, недетерминированные, вероятностные и другие А. К третьей группе относятся А. со специфическими множествами входных объектов. Таковы А. с переменной структурой, А. над термами ( см. Автоматов алгебраическая теория ). Существуют А., принадлежащие одновременно разным группам; например, А. нечеткие относятся ко всем трем группам. Наряду с этим большую роль играют специальные подклассы конечных А.; например, А. без памяти, автономные, обратимые А. и т. д. Кроме того, использование понятий и методов из других разделов математики также приводит к появлению специфических классов А. и связанных с ними задач. Например, А. над термами, линейного, группового, свободного и других А. (см.  Автоматов алгебраическая теория ); вопросы теории кодирования порождают понятия самонастраивающихся, обратимых А. и др. (см. также  Автомат вероятностный ). Для структурных А. также имеется целый ряд обобщений, сводящихся в основном к допущению бесконечных сетей и возможности изменения связей между элементами в процессе функционирования. Таким образом возникает понятие  растущего А . Ниже описываются основные модификации и подклассы конечных А., а также их важнейшие свойства.

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

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

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

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

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

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

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

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

5.  Специальные классы конечных А.

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

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

 А. обратимые , или  А. без потери информации , – это конечные А., реализующие взаимно однозначные функции. Эти А. также используются в теории кодирования.

Микроподход. Существует три вида обобщений структурных А., которые можно рассматривать как обобщенные логические сети: 1) обобщенные логические сети с неизменной структурой, у которых элементы и связи между ними не меняются в процессе функционирования; 2) обобщенные логические сети с изменяющейся структурой; 3) обобщенные логические сети из объемных элементов и связей. Ниже приведены основные классы таких А.

1.  Обобщенные логические сети с неизменной структурой . К ним относятся мозаичные структуры и  итеративные сети , являющиеся конечными фрагментами мозаичных структур с аналогичным кругом задач.

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

Мозаичную структуру можно рассматривать как бесконечный А., входной и выходной алфавиты, а также, множество состояний которого равны и являются бесконечным декартовым произведением множеств состояний всех переходных систем, содержащихся в ней. Это позволяет сводить многие задачи для мозаичных структур к задачам для бесконечных А. К числу специфических задач для мозаичных структур относится моделирование эффективных процедур и, в частности, вычислительных процессов. Иногда рассматривают мозаичные структуры, в которых вместо переходных систем используются произвольные А.

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

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

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

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

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

References

[1]  Мак-Каллок У., Питтс В., в сб.:  Автоматы, м., 1956, с. 362-84;

[2]  Клини С., там же, с. 15-67;

[3]  Бёркс А., Райт Д., в кн.:  Кибернетический сборник, в. 4, М., 1962, с. 33-57;

[4]  Глушков В. М.,  Успехи математических наук, 1961, т. 16, № 5, с. 3-62; 1962, т. 17, № 2;

[5]  Рабин М. О., Скотт Д., в кн.:  Кибернетический сборник, в. 4, М., 1962, с. 58-91;

[6]  Zadeh L. A.,  J. Math. Anal. and Appl., 1968, v. 23, № 2, p. 421-427;

[7]  Аладьев В. З.,  К теории однородных структур, Тал., 1972.

 В. Б. Кудрявцев.