Методы искусственного интеллекта для машинного перевода текстов. Роганов В.Р - 33 стр.

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

                                                                         33