“Алгоритмы вокруг нас”

§ 2. Искусственные языки. ';

Формальные языки I ]

1^ Когда была познана (или частично познана) сущность I. Языка, совершенно естественно стали пытаться с той или иной целью строить искусственные языки. Примером ис­кусственного языка может служить “международный” язык эсперанто. Этот язык в 1887 г. был создан варшавским врачом Л. Замонгофом и получил даже некоторое распространение. На эсперанто существуют литературные и научные произведения и даже издаются журналы. Его грамматика очень проста и легко поддается изучению. Тем не менее этот, хотя и искусственный язык, очень близок по своим особенностям к естественным языкам и с пашей точки зрения имеет мало преимуществ перед ними.

С другой стороны, в составе естественных языков мож­но выделить подъязыки, которые с нашей точки зрения очень хороши. Например, чем плох подъязык русского языка, фразы которого являются названиями чисел, та­кие как “девять тысяч восемьсот девяносто пять” и т. п. Даже более того, хороша некоторая более широкая часть русского языка, с помощью которой мы можем говорить о числах и отношениях между ними (к этой части принадлежит, например, фраза “тринадцать — простое число” или “число тринадцать меньше числа семнадцать”). Мы убеждаемся, таким образом, что “достоинства” языка вов­се не связаны с путем его возникновения. Отбирая некоторые предложения естественного языка, мы можем получить вполне удовлетворяющий нас язык. Но, конечно, можно построить и искусственный язык, удобный для целей теории алгоритмов. Каким же должен быть этот язык? Во-первых, потребуем от языка, чтобы он подчинялся вполне строгим и точно сформулированным синтаксическим правилам. Во-вторых, число этих правил должно быть конечно, и эти правила никак не должны зависеть от смысла получаемых с их помощью или ис­пользуемых в соответствии с ними предложений или их частей. В-третьих, будем требовать, чтобы между формой предложений и их смыслом существовало однозначное соответствие. Можно мириться с тем, чтобы различные предложения имели один и тот же смысл, по нельзя до­пустить, чтобы некоторое предложение имело несколько смыслов. Если даже какое-либо предложение может быть получено несколькими путями, это не должно делать его многозначным.

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

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

Иногда бывает удобно для описания языка-объекта применять два метаязыка, один из которых предназначен для описания синтаксиса и называется метасинтаксичес-ким, а другой — для описания семантики и называется метасемантическим.

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

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

Идея обоснования математики заключалась в том, чтобы, записав на формальном языке все ее аксиомы, забыть далее смысл этих аксиом и с помощью правил вывода кон­струировать всевозможные, вытекающие из этих аксиом теоремы, как результат преобразования одних строк символов в другие. Совокупность аксиом, правил вывода и по­лучающихся теорем называется при этом теорией. Такой подход к обоснованию математики называется формали­стическим (после построения теорем смысл их можно вспомнить).

При этом возникает идея языков, не обладающих ника­ким смыслом, и теорий, которые ничего не значат, по тем не менее являются “правильными” и полезными в том смысле, что все их “теоремы” выводимы из “аксиом” с по­мощью определенных “правил вывода”.

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

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

Один и тот же язык можно наделять различной семан­тикой путем его интерпретации.

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

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

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

Что же касается структуры самих предложений языка, то наш подход будет очень широким. Не будем требовать, чтобы предложения были словами или последовательностя­ми слов, или последовательностями последовательностей слов, как это имеет место во многих естественных языках, а будем допускать значительно более' сложные структуры предложений.