4.5. Широкое формальное определение алгоритма

Теперь, когда мы имеем некоторые алгоритмы (первичные), можно дать циклическое определение, которое уже не будет порочным кругом. Это определение очень похоже на определение первичных алгоритмов, но только в нем вместо правила выполнения фигурирует алгоритм выполнения. Но давая циклическое определение, сделаем это в самом общем виде, чтобы сократить текст книги.

Прежде всего нужно указать объекты преобразований. Пусть это по-прежнему будут предложения формального языка исходных данных L₁. Но такие предложения можно "обрабатывать" не только поодиночке, а сразу наборами. Учтем в нашем определении такую возможность. Пусть имеется некоторая связь n-го ранга и n-го жанра, не присутствующая в предложениях языка L₁. Обозначим ее z. Связывая с ее помощью различными способами предложения языка L₁, предварительно заключая каждое из них в оболочку, получаем более сложные конструкции, которые, если через s,- обозначить предложение языка L₁, можно изобразить как (s₁, s₂, ..., s_n) z. Эти новые конструкции образуют новый формальный язык. Обозначим его L₃. Если n = 1, нет надобности привлекать связь z первого ранга. В этом частном случае считаем, что L₃ совпадает с L₁. Итак, объектами преобразований будем считать предложения языка L₃.

Далее, пусть задан формальный язык L₂, предложения которого будем называть записями алгоритмов. Пусть t - произвольное предложение языка L₂, a q - языка L₃. Выберем бинарную связь z', не применяемую ни в языке L₂, ни в языке L₃, и построим символьные конструкции (t, q) z' .Их совокупность образует еще один язык L₄.

Алгоритмом выполнения назовем алгоритм W, записанный на любом, но определенном языке, для которого L₄ является языком операндов.

Таким образом, записями нового семейства алгоритмов являются предложения языка L₂, а алгоритм выполнения W наделяет эти предложения семантикой.

Можно приведенное циклическое определение перефразировать так: алгоритмами называются предложения языка, для которого задан язык исходных данных и алгоритм выполнения.

Определенное нами семейство алгоритмов по отношению к языку L₁ называется семейством n-местных или n-арных или n-го ранга алгоритмов.

Замечание. Если предложения языков L₁ и L₂ являются только слова, то можно вместо n-арной связи n-го жанра (z) и бинарной связи 2-го жанра (z') применить набор из n букв x₀, x₁, ..., x_n-1, не используемых ни в L₁, ни в L₂, и предложения языка L₃ строить как последовательные сцепления слов q = s₁ x₁ s₂ x₂ ... х_n-1 s_n. Предложения языка 14 при этом строят с помощью последовательных сцеплений в виде t x₀ q. Этот прием делает ненужными оболочки и упрощает алгоритм W.

Теперь можно сформулировать широкое формальное определение алгоритма. Алгоритмами называются:

1. первичные алгоритмы;
2. n-арные (при n = 1, 2, ...) алгоритмы, определение которых приведено выше.

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