МЕРЫ СЛОЖНОСТИ в теории автоматов.

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

Сложность автоматов. В качестве М. с, здесь рассматривается некоторый функционал относящий каждому автомату ЯЛ из исследуемого класса автоматов число характеризующее его громоздкость (сложность). Напр., в качестве М. с. конечного детерминированного автомата можно принять число к его состояний; более тонким критерием сложности является число его команд, равное произведению тк, где т — число букв во входном алфавите. Это же произведение можно рассматривать в качестве М. с.и для некоторых типов автоматов растущих. К ним относятся Тьюринга машина, имеющая ленточных символов и к состояний головки, автомат Неймана, элементы которого являются автоматами конечными с параметрами и т. д. Удачность такого выбора меры подтверждается, напр., следующим фактом: работу любой машины Тьюринга можно достаточно хорошо имитировать работой другой машины имеющей лишь два состояния (или два ленточных символа), причем для обеих машин число команд остается почти неизменным.

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

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

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

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

Сложность вычислений. Пусть зафиксированы некоторый класс К автоматов и концепция поведения автоматов из К, в соответствии с которой каждый автомат реализует словарный оператор. Считают, что все эти операторы заданы на словах в одном и том же алфавите Z (но не обязательно определены для всех слов в этом алфавите). В качестве М. с. вычислений рассматривается функционал относящий каждой паре , где ЭЛ а — слово в Z, для которого оператор, реализуемый автоматом К, определен, — число а . Это число характеризует сложность работы автомата применительно к исходным данным, закодированным в виде слова а, до выдачи соответствующего результата. Напр., в качестве а можно взять число элементарных шагов, из которых складывается эта работа (иначе говоря — длительность процесса вычисления), или объем памяти, который может понадобиться для записи всех промежуточных результатов по ходу данного процесса и т. д. Можно также считать, что в рассматриваемой ситуации М. с. является оператор (т. н. сигнализирующий оператор), который сопоставляет автомату ф-цию аргумента а (сигнализирующую функцию).

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

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

Явления инвариантности. Рассматривают различные М. с. в зависимости от исследуемого класса автоматов. Однако даже для одного и того же класса автоматов возможны различные сигнализирующие операторы, подобно тому, как выше были указаны различные М. с. для автоматов одного класса. Напр., для машин Тьюринга можно рассматривать сигнализирующие времена, сигнализирующие емкости (т. е. памяти) и т. д. Оценки сложности операторов зависят от того, какая М. с. автоматов или какая М. с. вычислений положена в основу теории. Но при этом обнаруживаются и некоторые явления

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

Лит.: «Труды Математического института им. В. А. Стеклова АН СССР», 1958, т. 51; Трахтенброт Б. А. Сложность алгоритмов и вычислений. Новосибирск, 1967 [библиогр. с. 255—258]; Проблемы математической логики. Сложность алгоритмов и классы вычислимых функций. М., 1970.

Б. А. Трахтенброт.