4.3. Первичные алгоритмы

Уже в вышеприведенном нестрогом определении алгоритма высказывается требование к нему "быть понятным". Какой математический (или, если хотите, кибернетический) смысл можно вложить в это требование? Только один: нужно знать алгоритм применения алгоритма к соответствующим (т. е. заданным) исходным данным. Для того чтобы выполнять алгоритмы, нужно знать алгоритм их выполнения. Возможен и еще один случай. Исполнитель алгоритмов так устроен, что, получая алгоритм и исходные данные, он выполняет алгоритм. Исполнитель алгоритмов - это устройство, созданное для выполнения алгоритмов. Ну, а если нам нужно создать такое устройство, как описать его необходимое для нас функционирование? Только задавая алгоритм выполнения алгоритмов.

Значит, дать точное определение алгоритма, не используя в качестве исходного это же понятие, нельзя. Но тогда получится так называемый порочный круг и никакого определения не будет. Однако, как мы уже знаем (см. с. 31), существуют еще рекурсивные определения (определения по индукции). Сначала мы определим некоторый частный вид алгоритмов путем точного математического описания. В этом случае мы сможем обойтись без предварительного знания того, что такое алгоритм. А впоследствии, зная уже некоторые алгоритмы, дадим общее определение алгоритма. Таким частным способом мы определим целый класс семейств алгоритмов, который назовем классом первичных алгоритмов.

Каждое семейство первичных алгоритмов предполагает наличие допустимых для него исходных данных. Такими исходными данными будем считать предложения (символьные конструкции) некоторого формального языка L₁. Описывать конкретно L₁ мы не будем, потому что для разных семейств первичных алгоритмов и языки исходных данных могут быть различными.

Предположим далее, что задан конечный набор операций (преобразований и логических действий), причем для некоторых из них операндами могут быть предложения языка исходных данных, а для некоторых - результаты операций-преобразований (или и те и другие).

Определим теперь для описываемого семейства первичных алгоритмов формальный язык L₂, предложения которого будут называться записями первичных алгоритмов (данного семейства). Воспользуемся для этого уже знакомой нам нотацией Бекуса.

Эти две метаформулы гласят, что запись первичного алгоритма представляет собой последовательность любого числа приказов, а приказы бывают безусловными и условными. Продолжим описание языка.

Метасимволы <метка>, <разделитель 1>, <разделитель 2>, <разделитель 3>, <разделитель 4>, <разделитель 5>, <разделитель 6>, <стоп>, <стоп 1>, <стоп 2>, а также метасимволы <знак операции-преобразования> и <знак логической операции> задают тогда, когда хотят выделить конкретный язык L₂. При этом необходимо, чтобы: метасимвол <метка> обозначал любое из некоторого бесконечного множества слов; разделитель 3 отличался от всех других разделителей; разделители позволяли в приказах находить границы их частей метасимволы <стоп>, <стоп 1> и <стоп 2> означали различные между собой слова. Значениями метасимволов <знак операции-преобразования> и <знак логической операции> являются имена вышеуказанных одноместных операций.

Для каждого семейства первичных алгоритмов должно быть задано правило их выполнения:

1. Найти первый (самый левый) приказ в записи первичного алгоритма. Перейти к п. 2.
2. Если рассматриваемый приказ является безусловным, то перейти к п. 3, а если условным - к п. 7.
3. Выполнить над операндом операцию, обозначенную в рассматриваемом приказе, и ее результат считать операндом. Выбрать из рассматриваемого приказа отсылку. Перейти к п. 4.
4. Если выбранная отсылка имеет вид <стоп>, <стоп 1> или <стоп 2>, то перейти к п. 5; во всех остальных случаях - к п. 6.
5. Считать имеющийся операнд результатом. Прекратить процесс выполнения.
6. Просматривая запись первичного алгоритма, начиная с первого приказа, искать метку, одинаковую с выбранной отсылкой. Если такой не окажется, то процесс безрезультатно обрывается. Если она будет найдена, то считать содержащий ее приказ рассматриваемым и перейти к п. 2.
7. Проверить, удостоверяет ли операнд условию, обозначенному в приказе. Если да, то перейти к п. 8, а если нет - к п. 9.
8. Выбрать первую отсылку из приказа. Перейти к п. 4.
9. Выбрать вторую отсылку из приказа. Перейти к п. 4.

Это правило выполняют при заданной записи первичного алгоритма и заданном операнде. Оно наделяет смыслом предложения языка L₂. Другими словами, для формального языка L₂ оно является семантическим. Но только в совокупности с расшифровкой знаков операций.

Правило выполнения является точным предписанием, ведущим от исходного данного (пары "запись алгоритма - операнд") к искомому результату. Оно обладает определенностью, конечно, если полностью заданы оба языка и набор операций. И хотя в строгом смысле оно не является алгоритмом, но все же может быть использовано в каждом конкретном случае для точного определения некоторого семейства первичных алгоритмов.