2.7. Резюме и комментарии к практическому использованию
Мы определили четыре типа языков, от относительно неструктурированного языка типа 0 до сильно структурированного языка типа 3. Каждый из языков более высокого порядка представляет собой собственное подмножество всех языков более низкого порядка. Этой последовательности языков соответствует последовательность все более ограниченных автоматов: машина Тьюринга, линейно ограниченные автоматы, автоматы с магазинной памятью, конечные автоматы. Эти четыре класса автоматов различаются по степени доступа к принципиально неограниченной ленте памяти. Каждый из них можно рассматривать как основной план для класса программ с аналогичным ограничением на доступ к принципиально бесконечной динамической памяти.
Современная практика вычислений, возможно, скрадывает это соответствие между программами и автоматами. При программировании МТ или МП-автомата мы часто моделируем „первую часть" принципиально бесконечной ленты памяти в конечной памяти реальной ЭВМ. Язык, который реально воспринимается, не предъявляет к ленте больших требований. Чтобы оценить это, заметим, что в „чистом" определении Фортрана как языка непосредственно составляющих должна быть возможность вставлять круглые скобки на любом уровне. Это позволило бы рассматривать арифметические выражения вида
которые могут содержать, например, 974 вложенных скобок. На практике длина ленты памяти, требуемой для МП-автомата, моделируемого транслятором, превзошла бы объем оперативной памяти, отведенной для программы в реальной ЭВМ, и оператор не был бы воспринят. Это „теоретическое" основание для ограничений,
записанных в большинстве учебников по программированию, предостерегающих программиста от использования операторов с более чем 12 уровнями вложенных скобок.
Если программа моделирует верхнюю часть ленты памяти на конечном участке, то независимо от того, как этот участок обрабатывается, сама программа определяет конечный автомат, а не МП-автомат. Можно ли быть уверенным, что эта ограниченная система воспримет подмножество языка, которое, как чистый Фортран или Алгол, было порождено грамматикой составляющей структуры? Ответ заключается в том, что подмножество языка, доступное программе, будет конечным, если любой язык, содержащий конечное множество цепочек, порождается регулярной грамматикой и, следовательно, воспринимается конечным автоматом. В действительности гораздо проще рассматривать транслятор как МП-автомати не забывать о побочных эффектах, которые ограничивают его операции. Это же справедливо и для ряда других псевдо-МП-автоматов.
Язык, воспринимаемый машиной Тьюринга, рекурсивно перечислим. Если дополнение этого языка также рекурсивно перечислимо, то это рекурсивный язык. Множество правильно построенных выражений (п. п. в.), выводимых из множества аксиом исчисления предикатов первого порядка, рекурсивно перечислимо, но не рекурсивно. Поэтому нельзя гарантировать, что программа распознавания таких утверждений закончит обработку произвольного п. п. в. за конечное время. Это важное теоретическое ограничение в области искусственного интеллекта. Рассмотрим „предельную" систему информационного поиска, которой сначала придан очень большой банк данных и затем задан вопрос: „Следует ли утверждение X из этих данных и правил логического вывода?". Если нет, то программа может попасть в цикл.
В других интересных ситуациях появляются еще более значительные ограничения. Существуют задачи, в которых требуемый входной язык не является рекурсивно перечислимым. Примером служит множество всех истинных утверждений в теории чисел. На практике, однако, ограничения вследствие нерекурсивности важнее ограничений из-за отсутствия рекурсивной перечислимости.
В сущности все интересные языки для п. п. в. в математике и логике имеют контекстно-свободные грамматики. Поэтому любая программа, которая должна обрабатывать такие утверждения, должна моделироваться по меньшей мере МП-автоматом. Естественные языки, однако, нуждаются в трансформационных грамматиках и потому могут обрабатываться только программами, моделируемыми машинами Тьюринга. Это значит, что программы анализа естественных языков должны содержать сложные механизмы для адресации принципиально бесконечной памяти. Подобный же вывод справедлив и для программ, осуществляющих алгебраические преобразования или доказательство теорем.
Эти результаты могут показаться обескураживающими, поскольку они означают, что существует ряд интересных задач, которые нельзя решить алгоритмически, и еще больше таких, для которых недостаточно простых алгоритмов. Мы заканчиваем эту главу более оптимистичным напоминанием о том, что на практике почти всегда можно ограничиться конечным подмножеством мыслимых предложений во входном языке и чисто прагматически решать задачу, написав программу — возможно и большую, но не требующую доступа к внешним устройствам с бесконечной памятью. Пока что подавляющее большинство приложений вычислительной техники обладает таким свойством.
