АВТОМАТ

- управляющая система, являющаяся автоматом конечным или некоторой его модификацией, полученной путем изменения компонент или функционирования. Основное понятие - конечный А. - возникло в середине 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 имеет несколько начальных состояний, образующих подмножество S₁ множества 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

Синонимы:

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

Смотреть больше слов в «Математической энциклопедии»

АВТОМАТ ВЕРОЯТНОСТНЫЙ →← АВТОКОРРЕЛЯЦИЯ

АВТОМАТ

Синонимы слова "АВТОМАТ":

Смотреть что такое АВТОМАТ в других словарях: