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

Одним из важнейших открытий теории алгоритмов в XX веке является открытие понятий алгоритма и исчисления «в качестве новых отдельных сущностей» [1], задающих эффективные процессы. Известно, что эффективный процесс может быть уточнен на основе двух типов представлений о нем: детерминированного предписания или недетерминированного разрешения. Тем самым эффективные процессы по способу вычисления подразделяются на «эффективно вычислимые» и «эффективно выводимые».

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

Алгоритмическая башня

Исчислительная башня

Конеч авт

МП-авт

Линейн авт

Рег грамм

КС-грамм

КЗ-грамм

Машина Тьюринга, алгоритмы Маркова и др

Рис.1. Иерархические башни формальных систем ния: Рег. грамм., КС-грамм., КЗ-грамм., Н-грамм. – регулярные, контекстно-свободные грамматики, контекстно-зависимые, неограниченные грамматики соответственно; Конеч. авт. – конечный автомат, МП-авт – автомат с магазинной памятью, Линейн. авт – линейно ограниченный по входу автомат). В качестве критерия упорядочения использован вид правил в грамматиках Хомского, согласно которому структура правил имеет четыре градации.

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

Сравнительный анализ свойств формальных систем

Равные дескриптивные возможности соответствующих алгоритмическихиисчислительных систем определили следующую двойственную ситуацию.

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

С другой стороны,существует возможность «при изложениитеорииалгоритмоввообщеобходитьсябез понятия исчисления» [2] вследствие дескриптивной эквивалентностисоответствующихалгоритмических и исчислительных систем двух башен.Исследование

НС-грамматики Хомского, исчисления Поста и др эффективных процессов возможно и реализуется в теоретических и прикладных вопросах на основе, прежде всего,детерминированного предписания без угрозы потери дескриптивных свойств формальной системы.Другими словами,статус исчисления как самостоятельного объекта эффективных процессов de facto нивелируется до статуса вспомогательного объекта.Законы его функционирования подменяются или ограничиваются исследованием алгоритмических законов.Работа исчисления сводится к его моделированию на основе алгоритмических представлений об эффективных процессах.

Следствием данной ситуации является несоответствие законов функционирования на основе детерминированного предписания и недетерминированного разрешения,что порождает проблему метрической (временной)избыточности исчисления при его алгоритмическом моделировании.Данная метрическая проблема избыточности функционирования является основной проблемой современной теории алгоритмов [3].

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

В рамках современной теории алгоритмов существует вторая составляющая – метрическая,предме-том исследования которой является сложность (ем-костная,временная) функционирования формальных систем.Применительно к метрической составляющей существует другое уточнение базового понятия «эффективный процесс».Согласно данному уточнению, имеющему метрическую направленность, все эффективные процессы допускают реализацию в виде линейных конструктивных или ветвящихся конструктивных процессов [1]. Линейный харак- тер конструктивного процесса означает,что всякое его текущее состояние однозначно предопределено предшествующим ходом процесса,т.е.время,как характеристика вычислительного процесса,является линейным (одномерным)и локальным параметром. Ветвящийся характер конструктивного процесса трактует время как разветвленный (многомерный)и распределенный параметр,поскольку всякое текущее состояние является всего лишь одним из возможных допускаемых предшествующим ходом процесса.

Уточнение понятия «эффективный процесс»

Концептуально, под алгоритмом как самостоя-тельнымобъектомгенерацииэффективныхпроцес-сов понимается детерминированное предписание, определяющее детерминированный вычислительный процесс преобразования начальных состояний в определенные заключительные состояния. Элементами алгоритма являются вычислительные операторы заранее ограниченной сложности. Процесс преобразования по Колмогорову разбивается на отдельные шаги и описывается следующей рекурсивной схемой общего преобразования состояний: S = Ω n ( … Ω 2 (Ω 1 (S 0 )), где S i = Ω i (S i-1 ) – шаг работы оператора Ω _i , состоящий в преобразовании ( i – 1)-го состояния в i -ое состояние; S₀ – начальное состояние.

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

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

Сущность структурнолингвистического подхода к уточнению исчисления

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

Несовпадение данных уточнений определяет метрическую проблему какв рамках теории алгоритмов (в широком смысле),так и в рамках приложений теории алгоритмов (в узком смысле)[4].Несоот-ветствия между дескриптивными и метрическими уточнениями эффективного процесса приведены в выражениях (1)-(2):

Линейный конструктивный процесс ≠ Детерминированное предписание

Ветвящийся конструктивный процесс ≠ Недетерминированное разрешение

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

(как это существует сейчас), а в определении областей эффективного применения алгоритмов и исчислений при решении прикладных задач.

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

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

Выводы

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