7.1.1. Разрешимость

Представим себе гипотетическую машину М, которая выводит грамматики следующим образом. Машина способна перечислять (возможно, бесконечное) множество кандидатов в грамматики. Всеведующий экспериментатор выбирает некоторую грамматику в качестве правильной. Затем он строит постепенно возрастающие выборки используя информаторное или текстуальное представление. Для каждой выборки машина М порождает соответствующую грамматику находя в своем перечне первую грамматику, удовлетворительно объясняющую . В дальнейшем мы обсудим специальное определение „удовлетворительного объяснения", а сейчас будем считать, что этот термин означает выполнение условий

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

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

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

Доказательство. Пусть машина М перечисляет в порядке Предположим, что грамматика действительно согласуется с На любом этапе процесса вывода машина М выбирает в качестве своей гипотетической грамматики первую грамматику в перечне которая удовлетворяет (8), правильно классифицируя все предложения в Пусть — первая такая грамматика, поэтому Так как то не согласуется с Следовательно, поскольку увеличивается, в конце концов найдется

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

Наше доказательство основано на том, что для любой грамматики какая-то цепочка из будет отвергнута или какая-то цепочка из будет допущена. При текстуальном представлении можно сделать ошибку только первого типа. Этого достаточно, чтобы нарушить условие разрешимости. Теоремы Голда и Фельдмана (Фельдман, 1972; Фельдман и др., 1969) подтверждают следующий результат о неразрешимости для текстуального представления.

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

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

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

Этот недостаток текстуального представления вызывает серьезные трудности, поскольку, как было показано во введении, во многих реальных ситуациях решения задач текстуальное представление будет единственным способом порождения выборки. К счастью, текстуальное представление можно использовать для определения грамматик, которые постепенно приближаются вполне определенным образом к правильной грамматике. Фельдман (1972) дает две интерпретации понятия „ближе", одна из которых включает другую.

Условие приближения

Говорят, что перечисляющая машина М приближает грамматику если

(П1) после некоторого шага грамматики выбранные машиной М в качестве пробных, допускают любую цепочку, допускаемую грамматикой

(П2) любая грамматика порождающая язык, который собственно включает в себя в конечном счете будет отвергнута:

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

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

Условие сильного приближения

(П3) Если существует грамматика согласованная с то для бесконечно многих

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

Займемся теперь вопросом выбора наилучшего объяснения для выборки. Безусловно, это как раз то, чем мы интересовались бы в большинстве практических приложений. Сначала надо определить, что мы будем считать наилучшим объяснением. Пусть функция несовместности для выборки и грамматики Функция должна быть вычислимой функцией сложности грамматики и степени, до которой естественно укладывается в Обозначим через функцию внутренней сложности, связывающую с классом и через функцию сложности вывода, определяющую степень, до которой следует естественно из Например, может быть числом нетерминальных символов в каждой грамматике (и тем самым она будет упорядочивать может быть числом шагов в самом длинном выводе, необходимом для порождения из Вообще говоря, нельзя минимизировать одновременно.

Предположим, что — приемлемое объяснение для Иными словами, должны выполняться условия (8). Для того чтобы из приемлемых объяснений выбрать одно, попытаемся минимизировать при следующих условиях:

(УI) Функция несовместности при заданной грамматике должна быть вычислимой функцией ее внутренней сложности и сложности вывода для выборки:

(У2) Если заданы две одинаково сложные грамматики, то функция несовместности должна быть меньше для грамматики, дающей менее сложный вывод.

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

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

и

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

оккамовским. Если оккамовское перечисление, то для Что же может делать машина, способная осуществлять оккамовское перечисление?

Ясно, что такая машина могла бы находить наилучшее объяснение для любой конечной выборки Для этого машина рассматривает грамматики в порядке перечисления. Пусть — первая приемлемая по (8) грамматика при заданной выборке Машина вычисляет , поскольку она уже „знает" , она может установить

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

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

Можно получить более сильные результаты, если рассматривается информаторное представление. Фельдман (1972) доказал, что при последовательность лучших догадок будет приближать для любого множества . В самом деле, если функция сложности вывода имеет верхнюю границу при неограниченном росте то машина, минимизирующая несовместность и использующая оккамовское перечисление, может в пределе дать грамматику, согласованную с Это важно, поскольку предположение о наличии верхнего предела сложности вывода вполне разумно. Пусть, например, как-то определена вероятность того, что некоторое предложение х появилось бы в выборке при условии, что — правильная грамматика. Определим как вероятность того, что грамматика породила бы выборку размера отличную от

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

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

Размышления адресуются психологам. Как ребенок может обучиться языку? Было высказано предположение, что обучение языку — процесс „вербального ограничения", аналогичный обучению механическим навыкам. Это предположение не подтвердилось фактами. Во всем мире дети начинают разговаривать, используя простые грамматики, затем переходят к более сложным. Оказывается, что порядок, в котором типы грамматик „рассматриваются" детьми, почти не зависит от самого изучаемого языка (Дейл, 1972). До какой степени идея естественного перечисления грамматик применима к построению модели обучения первому языку? Эта идея, возможно, сначала кажется „притянутой за уши", но проверка предположений, сделанных рядом современных структурных лингвистов (Леннеберг, 1967, 1969; Келли, 1967), показала, что по крайней мере внешне идея онтогенетической последовательности пробных грамматик похожа на идею оккамовского перечисления.