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

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

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

Множество L может быть, например, задано следующими словесными описаниями:

1) множество L содержит все последовательности длины, большей трех, у которых четвертым является символ

2) множество L содержит все последовательности, оканчивающиеся символом и нигде не содержащие символов .

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

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

Для того чтобы получить ответ на этот вопрос, надо формализовать понятие алгоритм распознавания. И мы вновь вынуждены обратиться, к теории алгоритмов и рекурсивных функций, утверждающей, в частности, что всякое множество последовательностей, для которого могут быть высказаны «правила распознавания», является рекурсивным, и наоборот (это утверждение является прямым следствием тезиса Чёрча — см. стр. 487).

Пусть L — произвольное рекурсивное множество входных последовательностей, — произвольные состояния Я-машин и G соответственно. Тогда имеет место следующая теорема.

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

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

Рассмотрим П-машину, имеющую три состояния; ее диаграмма состояний изображена на рис. 9.2. Для этой машины , т. е. входной алфавит состоит лишь из двух символов .

Рис. 9.2.

На выходе может либо .

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

Множество при любой рекурсивной функции рекурсивно. Действительно, каждой последовательности из 0 и 1 длины можно поставить в соответствие определенное значение целочисленной функции

из множества . Функция -возрастающая функция, и в силу рекурсивности является также рекурсивной. Следовательно, множество перечисляется в порядке возрастания рекурсивной функцией и потому является рекурсивным множеством. Отсюда и следует рекурсивность множества последовательностей .

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

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

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

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