§ 5. Натуральные алгоритмы

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

Итак, пока, кроме натуральных операций не определены никакие операции. Все же уже можно построить некоторый класс первичных алгоритмов. Для этого нужно определить язык операндов и алгоритмический язык.

Язык операндов определим так. Выберем некоторый алфавит А; далее составим формулу Бекуса;

<буква> :: = [перечислены все однобуквенные слова в А, разделенные знаками «|» (или) «]»

В качестве второй формулы возьмем

<слово> ::= <пусто> | <буква> | <слово> <буква>

Эти две формулы Бекуса являются формальной граммати­кой, определяющей очень простой язык. Любая цепочка букв в А является словом, а значит и предложением нашего языка.

Сами формулы Бекуса требуют только одноместной и двухместной операций соединения слов. Натуральные one рации позволяют нам построить такой язык.

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

Предположим, что для записей меток выбраны арабские цифры. Любая их строка будет меткой. Пусть разделитель-1 имеет вид « ) », разделитель-2 имеет вид: «, перейти к п.», разделителем-3 является знак « ; » (точка с запятой); раз-делителем-4 пусть будет «)Если», разделителем-5 — «, то перейти к », разделителем-6 — «, иначе перейти к ». Примем, что знак действия состоит из слова «выполнить» и следующего за ним в винительном падеже названия натуральной операции. Тогда знак действия может иметь вид «выполнить аннигиляцию» или «выполнить нахождение начала слова» и т. д. Знак условия пусть совпадает с фразой, состоящей из слова «справедливо» и названия натурального условия (см. § 2). Тогда знак условия может иметь вид «справедливо условие конца» или «справедливо условие «-тождественности» и т. д.

Предположим теперь для определенности, что алфа вит А — это алфавит латинских строчных букв. Приведем пример алгоритма из семейства построенных нами первич­ных алгоритмов. Представим себе, что задано некоторое слово в Л, и мы хотим все имеющиеся в нем буквы а заме­нить на i, а все имеющиеся буквы i заменить на а. Ясно, что если преобразуемое слово в А является пустым, алго­ритм к нему должен быть неприменимым.

Искомый алгоритм можно записать в следующем виде.

1. Если справедливо условие непустоты, то перейти к п. 2, иначе перейти к п. 1.

2. Выполнить нахождение начала. Перейти к п. 3.

3. Если справедливо условие а-тождественности, то перейти к п. 4, иначе перейти к п. 5.

4. Выполнить i-замену. Перейти к п. 7.

5. Если справедливо условие i-тождественности, то перейти к п. 6, иначе перейти к п. 7.

6. Выполнить а-замену. Перейти к п. 7.

7. Если справедливо условие конца, то перейти к п. 9,

иначе перейти к п, 8.

8. Выполнить продвижение вправо. Перейти к п. 3.

9. Выполнить отключение, перейти к п. 100.

Такой алгоритм переработал бы слово в A «magistr» в другое слово «migastr».

Прочитав текст алгоритма, читатель может воскликнуть «Вот тебе и на! Трудились мы, трудились, и пришли к тому, с чего начали!» — к алгоритму на естественном языке. Позвольте вас успокоить. Мы пришли не к тому, с чего начали, а к такому новому широкому определению алго ритма, что многие алгоритмы, составленные на естествен­ном языке, оказались частными случаями нашего широкого понятия алгоритма, а не алгоритмами в интуитивном смысле.

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

Первичные алгоритмы, в которых используются только натуральные операции, называются натуральными алго­ритмами.

Теперь построим еще один класс натуральных алгорит­мов. Пусть по-прежнему метка имеет вид последователь­ности цифр, разделитель-1 и разделитель-4 пусть состоят из единственного знака «:» (двоеточие), разделитель-2 и раз-делитель-5 пусть имеют вид «,», разделителем-3 пусть будет «;», а разделителем-6 знак «/» (косая черта).

В качестве знаков действия и знаков условия мы исполь­зуем символы, которыми были обозначены натуральные операции в § 2, т. е.

<знак действия> ::= | h <α> | * | X | → | ← | !<α>| ↓ | | l | d

<знак условия> ::= Δ | н | k | При этом

<а> ::= <буква в А>

В новом классе натуральных алгоритмов построим в ка­честве упражнения алгоритм нахождения конца слова. Он может иметь следующий вид:

Это уже не похоже на русский язык, но все-таки абсолютно понятно (если заглянуть в правило выполнения пер­вичного алгоритма). Первый приказ гласит: если преобра­зуемое слово непусто, то перейти к приказу 2, а иначе — снова к приказу 1. Значит, если слово пусто, то сдвинуться с приказа 1 не удается. Это значит, что наш натуральный алгоритм к пустому слову неприменим. Приказ 2 предпи­сывает найти начало преобразуемого слова и перейти к при­казу 3, приказ 3 — проверить, является ли рассматривае­мая буква концом слова, и если да, перейти к приказу 100, которого нет. Это значит, что процесс окончен. Если же рассматриваемая буква еще не конец слова, то по приказу 4 нужно продвинуться вправо и снова вернуться к приказу 3 для проверки, не найден ли еще конец.

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

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

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