Cтраница 4
Основная задача здесь состоит в том, чтобы получить определенные сведения о строении автомата путем наблюдения его реакции на те или иные внешние воздействия. При этом возникает большой круг задач, связанный с классификацией экспериментов и с вопросами разрешимости задач определенными видами экспериментов, а также с оценками длин минимальных экспериментов, достаточных для решения тех или иных задач. Понятие эксперимента с автоматами используется также в задачах надежности и контроля управляющих систем, в частности контроля автоматов. Многие из перечисленных выше задач могут рассматриваться как алгоритмические проблемы. Для конечных автоматов большинство из них имеет положительное решение. [46]
В одиннадцатой главе рассматриваются комбинаторные в собственном смысле приложения, группирующиеся вокруг так называемой Главной теоремы Мак-Магона. Здесь вскрывается опять-таки полугрупповая природа этой старой теоремы комбинаторики, обобщаемой затем с помощью удобного для подобных комбинаторных приложений понятия факторизации свободного моноида. Что касается десятой главы, то ее содержание - вместе с частью содержания гл. Поста), самым тесным образом связано с алгоритмическими проблемами и проблематикой условий конечности, а в последнее время обогащается содержательными связями с теорией многообразий. [47]
Была поставлена задача построения по возможности более простых примеров. В этом направлении блестящий успех был достигнут ленинградским математиком Г, С. Цейтиным и насчитывающего всего лишь семь допустимых подстановок, проблема эквивалентности слов также алгоритмически неразрешима. В течение последних тридцати лет были выявлены и многие другие алгоритмические проблемы, для которых невозможен разрешающий алгоритм. Для некоторых из них это очень долго не удавалось установить, хотя они уже давно числились в списке кандидатов на алгоритмически неразрешимые проблемы. Лишь в конце 1969 г. молодому ленинградскому математику Ю. В. Мати-ясевичу удалось доказать, что эта знаменитая проблема алгоритмически неразрешима. [48]
В зависимости от правил пометки переходов и от правил формирования последовательностей срабатываний выделяются различные классы языков, порождаемых сетями Петри. Эти классы сравниваются в данной главе друг с другом и с языками, порождаемыми другими типами абстрактных систем, предназначенных для моделирования дискретных систем, в частности, с языками конечных автоматов и машин Тьюринга. Такое сравнение позволяет характеризовать моделирующие возможности сетей Петри, их способность адекватно описывать системы со сложной динамикой функционирования. Оказывается, что моделирующие возможности сетей Петри выше, чем у конечных автоматов, но ниже, чем у универсальных систем типа машин Тьюринга. В этой главе рассмотрены также массовые алгоритмические проблемы для различных классов языков сетей Петри. [49]