2.3.1. Машины Тьюринга и языки типа 0

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

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

Для иллюстрации важности этого результата рассмотрим грамматику определенную в табл. 2.1 и 2.2. Ее правила, приведенные в табл. 2.2, можно с тем же успехом назвать правилами вывода для алгебраических преобразований или операторами задачи в пространстве состояний. Вообще, имея задачу в пространстве состояний, как она описана в гл. 1 (и подробнее в части III), можно построить правила, определяющие состояния и операции на них. В общем случае потребуются правила преобразований, как в табл. 2.2. Отсюда мы заключаем, что любую задачу, допускающую представление в пространстве состояний, можно связать с языком типа 0 и, значит, решить с помощью программы, которая, подобно машине Тьюринга, имеет неограниченный доступ к принципиально бесконечному участку динамической памяти. Схема работы машины

Тьюринга приведена на рис. 2.6. Второй основной вывод формальной лингвистики состоит в следующем:

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

В настоящее время общепринято, что естественные языки не могут порождаться менее мощной грамматикой, чем грамматика типа 0 (Хомский, 1965; менее технические соображения содержатся у Томаса, 1965). Необходимость в грамматике типа 0 показать легко.

Рис. 2.6. Переход в машине Тьюринга от одного состояния к другому. В этом примере машина считывает затем передвигает читающую головку на две ячейки вправо и на ленте записывается .

Томас (1965, стр. 100) указывает, что в английском языке требуется правило

для того, чтобы выводить предложения вида John was (был) из John be (есть) (прошедшее время). Правило (24) нарушает ограничение типа 1 о том, что длина цепочки в результате вывода не должна уменьшаться. Английский язык требует также правила для перестройки предложения. Возьмем пример с предложениями в страдательном залоге. Предложения

имеют одно и то же значение и, как подсказывает интуиция, одну и ту же основную структуру. На рис. 2.7 приведена диаграмма грамматического разбора, использующая простую грамматику.

Предложение в действительном залоге получается из дерева разбора сразу же. Предложение в страдательном залоге требует правила типа

для замещения активной формы пассивной. Правило -трансформационное правило, подобное правилу из разд. 2.2.

Рис. 2.7. Грамматический разбор предложения на естественном языке.

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