Математическая энциклопедия » Что такое «Автомат»?

Значение слова, определение и толкование термина

Автомат

Avtomat

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

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

2. Недетерминированные А. и асинхронные А. (вторая группа). Формально недетерминированный А. определяется как система [Автомат. Фото 2] где [Автомат. Фото 3] - алфавиты, имеющие прежний смысл, а [Автомат. Фото 4]- отношение переходов-выходов. В том случае, когда отношение [Автомат. Фото 5] является функцией, отображающей [Автомат. Фото 6] в [Автомат. Фото 7] недетерминированный А. наз. детерминированным А. и фактически совпадает с конечным А., поскольку в этом случае функцию [Автомат. Фото 8] можно рассматривать как пару функций [Автомат. Фото 9] отображающих [Автомат. Фото 10] соответственно. В отличие от конечного А., инициальный недетерминированный А. [Автомат. Фото 11] имеет несколько начальных состояний, образующих подмножество S1 множества S. Под поведением этого А. обычно понимают одно из следующих обобщений [Автомат. Фото 12] поведения конечного А.

1) Вместо функции [Автомат. Фото 13] автомат реализует отношение [Автомат. Фото 14] состоящее из всех пар слов [Автомат. Фото 15] [Автомат. Фото 16] [Автомат. Фото 17] таких, что найдутся состояния [Автомат. Фото 18] [Автомат. Фото 19] для к-рых [Автомат. Фото 20] и для любого [Автомат. Фото 21] имеет место [Автомат. Фото 22] Класс отношений, реализуемых инициальным недетерминированным А., совпадает с классом ограниченно-детерминированных отношений (см. Ограниченно-детерминированная функция).

2) Инициальный недетерминированный А.[Автомат. Фото 23] к-рого выделено множество [Автомат. Фото 24] заключительных состояний, а алфавит Впуст [Автомат. Фото 25] представляет событие [Автомат. Фото 26] состоящее из всех слов [Автомат. Фото 27] таких, что найдутся состояния [Автомат. Фото 28] для к-рых [Автомат. Фото 29] [Автомат. Фото 30] и для любого [Автомат. Фото 31] имеет место [Автомат. Фото 32] Класс событий, представимых А.[Автомат. Фото 33] совпадает с классом регулярных событий, т. е. относительно такого поведения недетерминированные А. эквивалентны конечным А. В то же время большая общность понятия недетерминированного А. проявляется в том, что для представления одного и того же события с помощью недетерминированного А. и конечного А. требуется различное число состояний. Существуют события, представимые недетерминированными А. с [Автомат. Фото 34] состояниями и представимые конечными А. с [Автомат. Фото 35] состояниями, причем никакие конечные А. с меньшим числом состояний не представляют эти события.

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

Термином "асинхронный А." обычно обозначают один из двух следующих видов А. К первому относятся А. вида [Автомат. Фото 38] где функция выходов [Автомат. Фото 39] отображает множество [Автомат. Фото 40] (у конечного А. [Автомат. Фото 41] отображает [Автомат. Фото 42] ). Эти А. используются главным образом в теории кодирования. Ко второму виду относятся конечные А., функция переходов у к-рых обладает следующим свойством: [Автомат. Фото 43] для любых s и а. Эти А. также используются в теории кодирования и, кроме того, для моделирования нек-рых систем в технике и биологии.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[Автомат. Фото 49]

  • ВКонтакте

  • Facebook

  • Мой мир@mail.ru

  • Twitter

  • Одноклассники

  • Google+

См. также

  • (от греч. autochthon - местный, коренной) (геол.), часть складчатого сооружения, оставшаяся на месте при образовании тектонич. покровов - в противоп

  • введение в органич. соед. сульфогруппы SO2OH. Напр., действием триоксида серы SО3 или серной кислоты на ароматич. углеводороды получают арилсул