Файл: Кушнер, Б. А. Лекции по конструктивному математическому анализу.pdf

Применительно к словам общее интуитивное понятие алгорифма переходит в понятие алгорифма в данном ал­ фавите. Именно, под алгорифмом в данном алфавите А

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

расплывчатой интуитивной концепции «алгорифма в дан­ ном алфавите».

Условимся о некоторых обозначениях.

Если 21 — алгорифм в алфавите А, Р — слово в этом алфавите и процесс применения алгорифма 21 к слову Р заканчивается, то мы пишем !?l (Р) . Результат работы в этом случае обозначается через 2t(P). Таким образом, запись

21 (P) = Q

(или

Q=p3l(P))

выражает то обстоятельство, что Q является результа­ том работы алгорифма 21 над словом Р. В этой ситуации мы будем также говорить, что 21 перерабатывает слово Р в слово Q.

Мы будем использовать также знак условного ра­ венства «~»: два выражения, соединенные этим знаком, означают одно и то же слово, если хотя бы одно из них имеет смысл. Таким образом, запись

2t(P)~93(Q)

выражает то обстоятельство, что !2t(P) равносильно !23(Q) и в случае выполнения хотя бы одного из этих ус­ ловий алгорифмы 21 и 33 дают одинаковый результат на словах Р и Q.

52 АЛГОРИФМЫ И ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА [ГЛ. I

В качестве другого примера рассмотрим вхождения пу­ стого слова в слово «ба». Таких вхождений имеется три: ааба, бааа и бааа. Вообще, число вхождений пустого слова в слово длины п равно п -f- 1.

Вхождение (3) слова Р в слово Q будем называть первым вхождением Р в Q, если длина левого крыла любого вхождения Р в Q не меньше длины Ri. Напри­ мер, вхождение (4) является первым вхождением слова

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

называются левой и правой частью соответствующей формулы подстановки). Нормальный алгорифм в алфа-