мальными будут только однородные линейные функции вида ЬХу + . . . + Кхп, где 6; - снова положительные натуральные числа.

Часто понятие термальной функции несколько расширяют. Р1менно, при заданных основных операциях f, . . .,/s и элементах а, . . ., а,, /г-местную операцию / называют термальной, если суш;еетвует терм й, построенный из части символов а, . . ., «г,/и . • ., Д и предметных переменных Xi,..., Xij (1 < й < . . .< h < п), такой, что значение операции / в любой точке <Сх, . . ., с„> совпадает с значением терма при значениях переменных xt, . . ., Xt, равных соответственно с, . . ., с.. Это означает, например, что терм ж + мы меняем понимать либо как терм, представ ляюш;ий двуместную функцию от х, у (старое определение), либо как терм, представляюп1;ий функцию от трех переменных х, у, z, где переменная z теперь входит в терм лишь фиктивно.

1.3. Алгебры. Алгеброй называется система, состоящая из некоторого непустого множества А и последовательности определенных на А операций /", . . . Множество А называется основным множеством алгебры, а операции/", /а", .-. . называются ее основными операциями. Последовательность (щ, . •> называется типом алгебры, а совокупность символов . . ., обозначающих основные операции, называется сигнатурой алгебры. Алгебры называются однотипными, если типы их совпадают. Классом алгебр называется произвольная система однотипных алгебр. При исследовании классов алгебр соответствующие операции этих алгебр обозначаются обычно одними и теми же символами. Алгебра с основным лшожеством А и основными операциями /j, /2, . . . обозначается через <4; f, /2, . . .>. Если некоторые из операций /1, /о, ... частичные, то п алгебра называется частичной. Однотипные частичные алгебры = <(Л; f, /2, . . .> п 5Б = <5; gj, go, • • •) называются изо.морфными, если существует одно-однозначное отобранение ф множества А на множество В такое, что

fi («1.....anf = gi {al а[г.) (i = 1, 2, . . .) (4)

для любых значенпп переменных а,ц, взятых в А

(через af обозначается образ элемента а нрп отображении ф).

Само отображение ф, обладающее свойством (4), называется изоморфизмом первой алгебры на вторую.

Если операции gj частичные, то знак равенства в (4), как и всюду в дальнейшем, означает, что значение левой части, в том числе и «неопределенное значение», совпадает с значением правой части.

Пусть на множестве А определена какая-либо частичная операция Подмнолество Aш А называется замкнутым относительно если для каждых элементов

. . ., а„ из для которых значение /"(«1, . . ., а) определено, это значение принадлежит Л.

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

Рассмотрим теперь некоторое непустое множество А, на котором определены произвольные частичные операции /1, /а, . . . Выделим в этом множестве какую-либо совокупность элементов D. Рассмотрим систему всех тех подмножеств из А, которые содержат D и замкнуты относительно каждой из операций Д, Д, . . . Эта система непуста, так как само у1 э Z> и замкнуто относительно операций f, /2, . . . Пересечение D* всех множеств этой системы замкнуто относительно рассматриваемых операций и содержит coBOKjrnnocTb D. Это пересечение называется подмно-леством, порожденным в А элементами мнол<ества D с помощью операций /j, /2, . . .

Очевидно, подмножество D* можно такне определить и как наименьшее подмножество в А, содержащее D п замкнутое относительно рассматриваемых операций.

Несколько более ясное представление о строении множества D* дает

Теорема 1. Подмножество D*, порожденное в А элементами совокупностиD с помощью операций f, Д, . . ., состоит из элементов, являющихся значениями термов, записанных при помощи символов операций f, /2, ... и си.чво.гов некоторых элементов D.

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

., а,1. - элементы Т, для которых (а, . . ., а„.) имеет значение а. По условию о, . . ., а„. являются зна-чениялш некоторых термов . . й„. указанного выше

вида. Но тогда а есть значение терма /j- (й, . . йп), такнад имеющего указанный выше вид. Следовательно, а£ Т я, значит, Т замкнута относительно операций /а, . . . Из замкнутости Т и условия D Як Т следует, что D* CZ Т.

Остается доказать, что Т содержится в D*. Для этого достаточно доказать, что каждое подмнон;ество В Як А, замкнутое относительно операций Д, /а, ... и содержащее совокупность D, содержит значение канодого терма указанного в теореме вида. Для термов длины 1 это утверждение очевидно. Ес.чи же терм, имеет вид /,• (Oj, . . . . . ., й„.) и значения термов а, . . ., й„. содержатся в В, то из замкнутости мнон<ества В следует, что значение терма /; (й, . . ., Лщ) такл(е содержится в В. В силу индукции наше утверждение можно считать доказанным, а вместе с ним доказана и теорема.

Рассмотрим некоторую частичную алгебру Э1 = /i, /2, . . .>. Берем произвольное непустое подмножество ЛX из J и определяем на А операцию /,-, п олагая для произвольных ai • • ч (1щ из 4i значение ft (а, . . ., Ощ) равным значению (а, . . ., Ощ), если последнее входит в Ах, и полагая (aj, . . ., Ощ) неопределенным, если значение fi (fli, . . ., йщ) не входит в Ai или не определено. Алгебра = <(Ai, Д, . . .> называется частичной подалгеброй алгебры 5f. Для операций /j, /2, . . . обычно употребляются те же символы Д, /а, . . ., что и для операций самой алгебры , и вместо «подалгебра ЗС = = /j,/,, . . .у» говорят кратко: «подалгебра А алгебры А». Частичная подалгебра называется замкнутой,- если] ишожество Ai замкнуто относительно операций /1, /2,. . .

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

Говорят, что совокупность D элементов частичной алгебры St = <(Л; /1, /з, . . .у порождает частичную подалгебру 1 = <i; /1, /21 • • •>. если D порождает множество Ас помощью основных операций/j, f, ... в А. Элементы множества D называются порождающими частичной алгебры У, если порожденная совокупностью D частичная подалгебра совпадает с 3f.

Принимая во внимание теорему 1, видим, что совокупность D элементов частичной алгебры 5t тогда и только тогда является порождающей совокупностью этой алгебры, когда каждый элемент % есть значение подходящего терма, образованного из символов основных операций и символов элементов D.

Иначе говоря, элементы Z> тогда и только тогда порождают алгебру 5(, когда каждый элемент % можно получить из элементов D, применяя конечное число раз основные операции алгебры.

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

Например, алгебра <(Ж; конечнопорожденная.

В качестве поронадающего множества можно взять любое множество чисел, содержащее О, 1.

Напротив, алгебра <(Л; х> не является конечнопорожденной. Действительно, беря какое-нибудь конечное множество чисел uj, . . ., Or, мы с помопц>ю операции умножения можем получить из них числа,, делящиеся лишь на те простые числа, на которые делится хотя бы одно из заданных чисел а, . . ., a- Так как простых чисел бесконечно много, то все натуральные числа получить умножениями из чисел flj, . . ., Яг нельзя.

1.4. Кодирование. Теория алгоритмов имеет дело со словами в конечном алфавите. Однако существуют математические объекты, играющие основную роль, которые нельзя без натяжки непосредственно рассматривать как слова в некотором алфавите. К такшг объектам, например, .можно отнести рациональные числа, алгебраические числа, функции и многое другое. Тем не менее ряд таких объектов может быть охарактеризован конечным числом целочисленных параметров пли просто словом в подходящем конечном алфавите. Например, возьмем алфавит, состоя-ш;пп .чшпь пз знака j. Словалш в этом алфавите являются последовательности «палочек»: , , (, . . . Сопоставим с каждым словом . . . , содержащим п -f 1 «палочек»,

натуральное число п. Говорят, что указанное слово изображает число п или является кодом числа п.

Аналогичным образом, вместо алфавита, состоящего

из одной буквы из двух букв о.

, можно рассмотреть алфавит, состоящий , , и в качестве кодированной записи натурального числа п брать его двоичную запись. Например, кодом числа «пять» в новом алфавите будет слово 101.

При двоичном кодировании мы встречаемся с той особенностью, что не кан{дое слово является кодом какого-нибудь натурального числа. Например, слово 01 не является кодом никакого натурального числа.

Рассмотрим еще обычное кодирование положительных рациональных чисел. Вводим алфавит, состоящий из прямой черты I и косой черты /. Слово вида . . . j / . . . , состоящее из от + 1 знаков , косой черты / и последующих п + 2 знаков , условимся называть кодом рацио-

нального числа -. Ясно, что теперь не только не каж-

дое слово является кодом рационального числа, но каждое полон<ительное рациональное число имеет бесконечно много различных кодов. Например, число 1/2 имеет коды

Во всех указанных случаях было выполнено следующее существенное требование: по заданному коду закодированный объект восстанавливался однозначно. Это требование обычно сохраняется и в общем определении кодирования.

Пусть Ж - совокупность некоторых объектов, А - какой-нибудь конечный алфавит. Закодировать совокупность Ш в алфавите А - это значит задать однозначное отображение х некоторого множества слов в алфавите А на совокупность Ш. Слово й из множества называется кодом (иногда - шпенем) объекта х (й) при кодировании X.

В этом определении не требуется, чтобы отображение X было одно-однозначным. Поэтому может слутчиться, что один и тот же объект будет иметь несколько различных кодов.

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

а) Кодирование слов в многобуквенном алфавите. Пусть алфавит А состоит из

букв О, 1, а алфавит 5 - из букв Ъ-, Ъ, . . ., Ъ, Рассмотрим совокупность тех слов в алфавите А, которые начинаются с 1, оканчиваются буквой О и не содержат подслов вида 00. Обозначим через 1" слово 111 ... 1 длины п. Каждое слово из 31 однозначно записывается в виде Г01Ю . .. 10. Этому слову ставим в соответствие слово bifii . . . bif алфавита В. Ясно, что полученное копирование одно-однозначно.

В рассмотренном случае алфавит В бесконечен. Если он конечен, то в качестве кода можно взять то не отобраие-пие X. Изменится лишь множество

б) Бесконечные алфавиты. Согласно основному определению алфавитом называется конечное множество символов. Однако фактически очень часто удобнее рассматривать бесконечные алфавиты, состоящие из конечного числа букв, снабженных той или иной системой индексов, принимающих натуральные значения О, 1, 2, . . . Например, пусть алфавит В состоит из символов а, Ь, . . ., с, fi, gi{i, j = О, 1, 2, . . .). Этот алфавит формально бесконечен. Рассмотрим алфавит А, состоящий из символов а, Ъ, . . ., с, f, g м новых символов а, р. Условимся символы fi тл. gi кодировать в языке А словами fa ... а ш соответственно . . . аР . . . р, где символ а входит i раз, а символ р входит / раз. Символы а, Ь, . . ., с пусть кодируются ими салшми. Обозначим через {х} {х 6 b В) кодовое значение символа х в алфавите А. Если й - слово в алфавите В, то, подставляя в й вместо символов пх кодовые значения, получим некоторое слово в алфавите А, которое обозначим через {й}. Ясно, что по коду {й} однозначно восстанавливается и слово й. Поэтому, вместо того чтобы рассматривать произвольные слова а, Ь, . . . в бесконечном алфавите В, можно рассматривать их кодовые значения {й}, {ь}, . . . в конечном алфавите А и тем самым избежать рассмотрения бесконечных алфавитов.

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

• . . в алфавите А придется часто рассматривать пары слов <(й, Ьу, тропки слов <й, Ь, с> и т. д. Однако пару слов "(й, ьу в алфавите А можно закодировать словом ааЬ в алфавите В, тройку <(й, Ь, су слов из А можно закодировать словом йаЬхс в алфавите 5 п т. д.