markov_teorija_algorifmov (Марков - Теория алгоритмов), страница 7

Р,З вопрос о графическом равенстве двух непустых слов сводится к аналогичному вопросу для слов меньшей длины, так что у иас в наличии имеется способ„позволяющий для любых двух слов Р и Я в алфавите А выяснить, какое из высказываний РхЛ, Р-(:Л является истинным. б. Важную роль в дальнейшем изложении будет играть операции соединения слов.

Ее применение к словам Р и (~ в алфавите А будет состоять в приписывании справа к слову, графически равному Р„слова, графически равного Я, в результате чего получается слово, называемое соединением слов Р и Я. Соединение слов Р и Я мы временно будем обозначать символом !Р, Я)л. Впоследствии, когда для этой операции будет установлен сочетательный закон, мы заменим обозначение (Р, 9л более простым. Мы дадим сейчас удобное для использования (и несколько более точное) определение этой операции, учитывающее индуктивный характер определения (Р, Л!л Р, !Р, ()Ч =ГР. И ~ (знак = здесь означает равенство по определению). Из этого определения операции соединения мы и будем исходить в дальнейшем. Первое равенство позволяет найти соединение слова Р и пустого слова при любом Р. Второе однозначным образом сводит нахождение соединения слова Р со словом Щ к нахождению соединения слова Р с „предшествующим" Я$ словом (г.

Таким образом, соединение Р и Я может быть построено при любых Р и Я. Как и выше, условимся в случаях, не вызывающих сомнений, опускать индекс у знака операции. 6. Внимательный читатель уже заметил, что в пп. 4 и 5 мы существенным образом пользуемся некоторой исходной элементарной операцией — операцией правого присоединения буквы и слову. В дальнейшем ($17.3! роль этой операции будет проанализирована более подробно.

7. Алфавиты мы определили выше (э 1,3! как наборы знаков, которые мы соглашаемся считать буквами. Такой набор удобно изображать словом, составленным из букв алфавита, взятых в определенном порядке, например в порядке их следования. В дальнейшем мы часто будем поступать именно таким образом. Тем ие менее порядок букв в алфавите нас, как правило, интересовать не будет. Имея это в виду, мы два алфавита, состоящие из одних и тех же букв, будем называть равносоставленными и все наши рассмотрения, связанные с алфави'тами, будем проводить с точностью до равносоставлениости фигурирующих в них алфавитов. 8.

Мы ввели ряд основных понятий семиотики объектов, имеющих линейную структуру,— теории слов. Эта теория рассматривает слова как знаковые комплексы, взятые сами по себе, безотносительно к тому, чтб эти комплексы означают (как правило, в математике знаки что-иибудь да означают). Сейчас мы прервем изложение теории слов до 8 17 и займемся обсуждением ряда принципиальных вопросов, которым в дальнейшем предстоит играть чрезвычайно важную роль. ВВЕДЕНИЕ |гл.| 5 3.

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

Таким образом, язык является способом передачи информации с помощью конструктивных объектов. 2. Информация на данном языке, передаваемая отправителем адресату, должна быть понята последним, желательно однозначно. Этому обычно служит членение текста на куски, называемые «высказываниями», Понятие <высказывания» определяется в каждом языке посвоему. 3. Проще всего обстоит дело с этим понятием в некоторых искусственных языках. В таких языках точно формулируются правила построения высказываний. Некоторые из этих правил непосредственно квалифицируют определенные слова как высказывания.

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

Выяснив с помощью семантических соглашений, о чем поветствует данное высказывание, мы можем поставить вопрос о его истинности, вопрос о том, действительно ли имеет место то, о чем высказывание повествует. Этот вопрос может решиться по-разному, а может и не решиться вовсе при современном состоянии наших знаний. Высказывание верно (истинно), если то, о чем оно повествует, действительно имеет место *); «) Сказанное, разумеется, требует уточнений. Эти уточнения в разных ситуациях могут выглядеть по-разному.

, зз] ЯЗЫКИ. ВЪ|СКАЗЫВАНИЯ оно неверно (ложно), если то, о чем оно повествует, не имеет места. Семантические соглашения образуют семантику данного языка. Сам этот язык можно рассматривать как состоящий из двух частей — синтаксиса и семантики. Рассмотренная схема построения искусственного языка не исчерпывает всех случаев. Имеются «повествовательиые» искусственные языки, построенные по более сложным схемам. Например, построение грамматической категории конструктивных объектов, называемых высказываниями, может осуществляться одновременно с построениями некоторых других категорий объектов. Характерным для всех этих языков является наличие четкого определения высказывания, независимого от понимания высказываний.

Во всех языках этого рода высказывания оказываются конструктивными объектами. 4. Значительно хуже обстоит дело с высказываниями в так называемых „естественных" языках. Такой язык может иметь „грамматику", пытающуюся навести порядок в речи и письме. Эта грамматика тоже имеет свой синтаксис и свою семантику, однако и тот и другая обычно бывают очень запутанными и неточными. Семантика часто вмешивается в синтаксис, что далеко не способствует ясности понятий. Мы вынуждены, тем не менее, пользоваться естественными языками, которым нас учат с детства.

В частности, в этой книге мы пользуемся русским языком, лишь несколько расширенным специальными обозначениями и терминами. Мы применяем и изучаем некоторые высказывания этого языка. Здесь термин «высказывание» применяется в ие очень точном смысле. Слово «высказывание» вЂ” это синоним слова «утверждением Высказывание о чем-то повествует. Оно бывает истинным, а бывает и ложным. Впрочем, понятие высказывания русского языка, вероятно, может быть определено посредством более или менее точного синтаксиса, после чего посредством более нли менее точных семантических соглашений может быть определено наше понимание высказываний. Таким образом, „естественные" языки можно, по-видимому, рассматривать как плохие „искусственные" языки *).

5. К счастью, для построения теории алгорифмов естественный язык нам понадобится не в полном его объеме. Достаточно будет воспользоваться сравнительно узким, ограничен- ') Кавычки здесь оправданы тем, что„естественные«языки искусственны: ведь их грамматику тоже кто-то придумал, т. е. создал искусственно. С другой стороны, многие искусственные специализированные языки возникли довольно естественно ради нужд практики. 2 А.

А. Марков, Н. М. Н«торчмя ввидиник !Гл. ! АБСТРАКЦИЯ ОТОХСДЕСТБЛБИИЯ ным фрагментом этого языка, имеющим благодаря своей ограниченности относительно четкую логическую структуру, что в свою очередь позволит нам разработать относительно четкие принципы понимания высказываний, формулируемых средствами этого фрагмента. Принципы эти будут разрабатываться с учетом особой, конструктивной природы рассматриваемых объектов. При желании этот фрагмент можно было бы превратить в искусственный язык с точным синтаксисом и точной семантикой.

Фактически такая работа даже была проделана и результаты ее изложены А. А. Марковым в !18! — !27!. Однако обучение читателя этому языку потребовало бы значительных усилий, и мы откладываем его на будущее. 2 4. Абстракция потенциальной осуществимости 1. Осуществляя конструктивные процессы, мы часто наталкиваемся на препятствия, связанные с нехваткой времени, места и материала. Эти препятствия обычно удается так или иначе обойти.

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

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