§ 8.3. Алгоритмическая неразрешимость проблемы распознавания представимости рекурсивных событий

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

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

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

Если такие множества заданы для всех выходных символов , то это и означает, что установлено однозначное соответствие между входными и выходными последовательностями. Так, если входной алфавит содержит четыре символа , а выходной алфавит три символа и если известно, что:

а) символ появляется в такт , если в предшествующие два такта (т. е. такты) во входной последовательности появлялся символ и за ним

б) символ появляется, если не выполняются условия . а) и на протяжении предшествующих такту трех тактов не появлялся символ

в) символ появляется во всех остальных случаях, то для любой входной последовательности, заданной в алфавите , мы можем немедленно выписать выходную последовательность. ,

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

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

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

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

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

Теорема 1. Проблема распознавания регулярности рекурсивных событий алгоритмически неразрешима.

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

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

где — символ из , индекс которого совпадает со значением рекурсивной функции при .

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

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

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

В соответствии с теоремой, доказанной в § 7.6, рекурсивное событие регулярно тогда и только тогда, когда рекурсивная функция является в конечном счете периодической. Но поскольку, как известно, задача распознавания того, является ли любая заданная рекурсивная функция в конечном счете периодической, алгоритмически неразрешима, то алгоритмически неразрешима и проблема распознавания регулярности события а значит, тем более, и проблема регулярности рекурсивных событий. Теорема доказана.

Предположим теперь, что хотя алгоритма распознавания регулярности рекурсивных событий не существует, тем не менее каким-либо иным образом («творчески») каждый раз удается выяснить, является ли заданное рекурсивное событие регулярным. Тогда возникает задача об определении алгоритма синтеза автомата, представляющего заданное рекурсивное событие. Однако и в этом случае нет общего приема, решающего поставленную задачу, в силу следующей теоремы, также установленной Б. А. Трахтенбротом и приводимой ниже без доказательства.

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

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

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

Алгоритм синтеза П-машины, заданной таким способов, заведомо существует. Он, например, легко следует из рассуждений, приведенных в гл. VII при доказательстве первой, теоремы Клини. В § 8.4 приводится другой (относительно более удобный и экономичный по числу получающихся состояний) алгоритм синтеза машины, представляющей заданные регулярные события.

Другим примером языка, относительно которого установлено, что все выраженные на нем задания заведомо реализуемы Я-машиной, и для которого существует алгоритм синтеза, является предикатный язык Б. А. Трахтенброта, который подробно описан в [101, 102].

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

Язык, удобный для выражения задания и дальнейшего синтеза, должен был бы поэтому удовлетворять следующим трем требованиям:

1) Наиболее естественные и часто встречающиеся словесные описания должны легко «переводиться» на этот язык.

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

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

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

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