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

Это шло бы вразрез с нашей основной целью — изложить теорию алгорифмов в терминах конструктивных процессов. 5. В обыденной жизни словами данного языка принято называть „осмысленные" ряды букв этою языка. В нашем о~ределении какое-либо требование осмысленности отсутствует. Так, ряд букв русского алфавита папагиглемма, пока не являющийся словом русского языка, является словом в русском алфавите в смысле нашего определения. 6. Натуральные числа, как мы убедились, могут быть охарактеризованы как слова в алфавите, единственной буквой которого является вертикальная черточка [. Присоединяя [гл.

введение 26 слова к этому алфавиту в качестве дальнейших букв горизонтальную черточку « вЂ” » и наклонную черточку «Ь, мы получаем возможность естественно строить рациональные числа как слова в трехбуквенном алфавите ((,—, с). Действительно, целые числа могут быть получены путем добавления к натуральным числам слов вида — М, где )«' — натуральное число, отличное от Л, а рациональные— путем добавления к целым числам слов вида М/М, где М вЂ” целое число, а ««' — натуральное, отличное от Л. Определенные таким образом рациональные числа суть конструктивные объекты. 7.

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

Этот вид во всех случаях, с которыми приходится иметь дело, может быть точно охарактеризован, равно как и тип конструктивных процессов, порождающих такие объекты. Таким же образом будем поступать и мы: говоря о конструктивных объектах, мы будем подразумевать конструктивные объекты определенного точно охарактеризованного типа. Прилагательное «конструктивный» мы при этом часто будем опускать. й 2. Слова 1. Линейность расположения знаков в конструктивных объектах, с которыми мы имеем дело в математике, может нарушаться.

Такие нарушения возникают уже тогда, когда мы начинаем пользоваться индексами и показателями степени. Еще большие отклонения от линейности возникают при записи матриц в виде таблиц. Тем не менее все такие нарушения обычно удается устранить без всякого изменения существа дела. Так, например, составленную из слов Р, Щ, Я, 8, Т, У систему слов (Р, (1, Я, 3, Т, У) можно условиться записывать в виде слова аРи(гиКайоТаИа, а таблицу (: :) в виде слова рРиф~йи5рТа(ф, где и и р обозначают какие- нибудь две различные, ранее не использовавшиеся буквы. Такое присоединение „новых" букв к алфавиту дает возможность записывать в строку более сложные фигуры, составленные из объектов, уже записываемых словами в этом алфавите. Приемы подобного рода дают возможность переходить к изображению рассматриваемых объектов словами. Поэтому мы не сделаем существенного ограничения общности, если условимся для дальнейшего считать, что слова в алфавитах являются конструктивными обьектами общего вида.

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

до конца процесса. Кроме того, определению слова следует, конечно, придать „рабочий" характер, который в дальнейшем обеспечивал бы удобное его использование в разного рода формулировках и конструкциях. С учетом сказанного мы сформулируем это определение в следующем виде, в котором и будем использовать его впредь. Пусть А — какой-либо алфавит. Словами в алфавите А мы будем называть конструктивные объекты, получающиеся в словх взвдяиие 28 результате развертывания конструктивных процессов, ведущихся на основании следующих правил: а) пустое слово Л мы считаем словом в алфавите А; б) если конструктивный объект Р уже оказался словом в алфавите А, то словом в ачфавите А мы считаем также и конструктивный объект Рг, где $ — любая буква алфавита А (здесь Ря означает объект, получающийся в результате приписывания к Р справа буквы я; в частности, Л$ означает я).

Слова, получающиеся в результате процессов, заканчивающихся применением правила б), мы называем непуетыгги. В дальнейшем мы убедимся, что всякое непустое слово в А единственным образом представляется в виде Р1, где Р— слово, а з — буква. 3. Определения, подобные только что сформулированному, принято называть икдуктиеиыми. Как правило, индуктивное определение используется для задания какого-либо типа конструктивных объектов.

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

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

Фиксируются некоторые конструктивные объекты — аксиомы этого исчисления. Указываются правила вывода, позволяющие по уже полученным объектам строить некоторые новые. Разрешается, исходя из аксиом и пользуясь правилами вывода, осуществлять выводи. Выводом в данном исчислении называется упорядоченный список объектов, кажк дый член которого либо является одной из аксиом исчисления, либо получается из какого-либо числа предшествующих членов по одному из правил вывода. Вывод, имеющий данный объект в качестве своего последнего члена, называется выводом этого объекта, Объект считается выводимым в данном исчислении, если может быть построен его вывод в этом исчислении.

Вывод данного объекта может рассматриваться как Его построение. 11оскольку любой начальный отрезок вывода также является выводом, всякий вывод наряду с построением воего „основного" объекта (заключительного члена вывода) содержит в себе построения всех использовавшихся в нем по ходу дела „вспомогательных" объектов. Иногда возникает потребность в рассмотрении так называемых выводов г анализом, т. е. выводов, содержащих дополнительные сведения о „происхождении" своих членов. Если какой-либо член вывода берется в качестве аксиомы исчисле ния, то в анализе указывается, в качестве какой именно. В противном случае указывается правило вывода и предшествующие члены, к которым оно применяется. Условившись писать выводы „в столбик", мы можем записывать выводы с анализом „в два столбика", приводя против каждого члена вывода требующиеся пояснения.

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

4. Сравнивая между собой слова в каком-либо фиксированном алфавите А, мы можем встретиться с двумя словами, составленными из одинаковых букв, одинаковым образом расположенных, Но может случиться и так, что одно из сравниваемых слов окажется длиннее другого или что при равной длине эти слова будут различаться на некоторых местах буквами. В первом случае мы будем называть слова графически равными, а во втором — графически различными.

С целью уточнения этих определений мы введем два бинарных отношения между словами в А — отношение Ха графического равенства слов в А и отношение ~Ел графического различия слов в А, считая, что: Р.1. Высказывание является истинным. СЛОВА [гл. ю ВВЕДЕНИЕ Р.2. Высказывания Р$ХдЛ, ЛХВР$, слов. Именно, зафиксировав алфавит А, мы для любых двух слов Р и Я в А н для любой буквы $ этого алфавита по- ложим где Р— слово в А, а $ — буква этого алфавита, являются ложными. Р.З, Высказывание ЛхЛц, где Р и (! — слова в Л, а С и т(--буквы этого алфавита, является истинным, если буквы с и Ч одинаковы и высказывание РЕВЯ истинно, и ложным, если с и т) различны или высказывание Рел Я ложно.

Р 4. Высказывание является истинным, если высказывание Р оХ9 ложно, и, наоборот, ложным, если это последнее истинно. Нетрудно понять, что отношения этн можно было бы определить и независимо друг от друга, но технически удобнее сначала определить отношение Хд, а затем отношение:)Гл выразить через него. В случае, если ясно или безразлично, о каком алфавите А идет речь, индекс А у знаков э.л и,~А будет опускаться. Заметим, что в силу п.