Автомат

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

Источник: Математическая энциклопедия на Gufo.me


Значения в других словарях

  1. автомат — -а, м. 1. Самодействующее устройство (аппарат, машина, прибор), производящее работу по заданной программе без непосредственного участия человека. Телефон-автомат. Малый академический словарь
  2. автомат — I. индивидуальное автоматическое стрелковое оружие, созданное под патрон, занимающий по мощности промежуточное положение между винтовочным и пистолетным патронами. За рубежом подобное оружие может иметь иное название, напр. Техника. Современная энциклопедия
  3. Автомат — I Автома́т (от греческого autómatos — самодействующий) 1) самостоятельно действующее устройство (или совокупность устройств), выполняющее по заданной программе без непосредственного участия человека процессы получения, преобразования... Большая советская энциклопедия
  4. автомат — • автоматическая винтовка Сокращения, применяемые в СССР
  5. автомат — (иноск.) — болван, человек бесчувственный, действующий бессознательно, как кукла, подражающая движениям живого существа вследствие скрытого в ней двигателя Ср. Автоматически — бессознательно, невольно. Ср. Фразеологический словарь Михельсона
  6. автомат — АВТОМАТ а, м. automate m., ср.-лат. automatus, гр. 1532. Лексис. 1. Самодействующее устройство, приводимое в движение скрытым механизмом: часы, заводные игрушки и проч. Сл. 18. Автомат, самодвиг. Рейф 1861. Словарь галлицизмов русского языка
  7. автомат — Авторучка Словарь воровского жаргона
  8. автомат — см. >> кукла Словарь синонимов Абрамова
  9. автомат — Автома́т/. Морфемно-орфографический словарь
  10. автомат — сущ., м., употр. часто (нет) чего? автомата, чему? автомату, (вижу) что? автомат, чем? автоматом, о чём? об автомате; мн. что? автоматы, (нет) чего? автоматов, чему? автоматам, (вижу) что? автоматы, чем? автоматами, о чём? об автоматах... Толковый словарь Дмитриева
  11. автомат — Заимств. из франц. яз. в конце XVIII в. Франц. automate восходит к греч. automatos «самодействующий» (autos «сам», matos «действие, усилие»). Автомат буквально — «работающая без участия человека машина». Этимологический словарь Шанского
  12. автомат — орф. автомат, -а Орфографический словарь Лопатина
  13. Автомат — (от греч. autуmates — самодействующий * a. automaton; н. Automat; ф. automate; и. autуmata) — устройство (или совокупность устройств), выполняющее по заданной программе без непосредств. Горная энциклопедия
  14. Автомат — (греч. automates самодействующий, самопроизвольный) устройство, осуществляющее процессы переработки информации, энергии и (или) материала без непосредственного участия человека; различные... Медицинская энциклопедия
  15. автомат — АВТОМАТ -а; м. [от греч. automatos — самодействующий]. 1. Самодействующее устройство (аппарат, машина, прибор), производящее работу по заданной программе без непосредственного участия человека. Автоматы с газированной водой. Игровые автоматы. Толковый словарь Кузнецова
  16. автомат — См. автограф Толковый словарь Даля
  17. автомат — Заимствовано из французского языка в конце XVIII в., а французское automate в свою очередь восходит к греческому automates "самодействующий, самодвижущийся". Этимологический словарь Крылова
  18. автомат — автомат I м. 1. Устройство, самостоятельно, без непосредственного участия человека выполняющее какие-либо действия или операции в соответствии с заранее заданной программой. 2. перен. Тот, кто поступает не думая, делает что-либо механически, машинально. Толковый словарь Ефремовой
  19. автомат — АВТОМ’АТ, автомата, ·муж. (·греч. automatos, ·букв. самодвижущийся). 1. Аппарат, выполняющий определенную работу самостоятельно, действием внутреннего механизма. На вокзале автомат выбрасывает перронные билеты при опускании в него монеты. Толковый словарь Ушакова
  20. автомат — Автомата, м. [греч. automatos, букв. самодвижущийся]. 1. Аппарат, выполняющий определенную работу самостоятельно, действием внутреннего механизма. На вокзале автомат выбрасывает перронные билеты при опускании в него монеты. 2. Механическая заводная кукла. Большой словарь иностранных слов
  21. АВТОМАТ — АВТОМАТ — индивидуальное стрелковое автоматическое оружие. Действительный огонь до 400 м, скорострельность может достигать 1000 выстрелов в минуту. АВТОМАТ (от греч. Большой энциклопедический словарь
  22. автомат — АВТОМАТ, а, м. 1. Аппарат (машина, прибор, устройство), после включения самостоятельно выполняющий ряд заданных операций. Станки-автоматы. Игровые автоматы. Работать как а. (точно, ритмично). 2. Индивидуальное автоматическое стрелковое оружие с надевающимся штыком-ножом. | прил. автоматный, ая, ое. Толковый словарь Ожегова