Английскому термину «алгоритм» около восьми веков. Он происходит от средневекового латинского algorismus, который имеет отношение к выполнению основных математических операций в индо-арабской системе счисления. В средневековой Европе, благодаря торговле с арабским миром, ограниченная римская система счисления постепенно вытеснялась более универсальной индо-арабской позиционной системой, которая была удобнее для сложных операций с большими числами и с тех пор стала всемирным стандартом. Латинский термин algorismus можно, например, найти в поэме Александра из Вильдьё «Песнь об алгоризме» 1240 года – руководстве по техникам расчета, составленном для облегчения запоминания процедур в виде рифмованных строф. Книга, напечатанная в Венеции в 1501 году и приписываемая монаху XIII века Иоанну Сакробоско, называется Algorismus Domini и объясняет с помощью индийских числовых символов и схем, как вести ручные расчеты.

Рис. 1.3. Аллегория Арифметики (Reisch G. Margarita philosophica, 1503)

Лишь недавно установлено, что algorismus — это латинизация имени персидского ученого Мухаммада ибн Мусы аль-Хорезми, главного библиотекаря Дома мудрости в Багдаде. Около 825 года н. э. Аль-Хорезми написал книгу о расчетах с помощью индийских числовых знаков. Арабский оригинал книги был утерян, но в XII веке имели хождение по меньшей мере четыре латинских перевода под разными названиями. Инципит рукописи в библиотеке Кембриджа гласит DIXIT algorizmi (что означает: «так говорил Аль-Хорезми»). Другую версию перевода итальянский математик Бальдассаре Бонкомпаньи назвал в 1857 году Algoritmi de numero Indorum[106]. В современную математику и компьютерную науку английский термин algorithm вошел через различные романские транслитерации, в частности французскую и испанскую. Книга Аль-Хорезми познакомила Запад с позиционной индийской системой счисления, однако купцы, например итальянский математик Фибоначчи, часто путешествовавший по Средиземноморью, вероятно, обучились этой системе не из книг, а в процессе торговых расчетов.

В математике принято считать, что усвоение термина «алгоритм» на Западе ознаменовало переход от аддитивной к позиционной системе счисления. Этот сдвиг носил как технический, так и экономический характер, поскольку был связан с ускорением товарооборота в Европе и Средиземноморье, требовавшим более совершенной системы бухгалтерского учета. Десятичная позиционная система позволяла более компактно записывать числа и ускоряла расчеты. В Италии флорентийские и венецианские купцы первыми взяли на вооружение индийские числовые символы, оценив их удобство в условиях коммерческих сделок и постоянно растущих капиталов. На рисунке 1503 года из книги Margarita philosophica под редакцией немецкого монаха-полимата Грегора Райша изображен спор между счетоводами, которые еще пользовались римской системой и абакусом, и новыми алгористами, усвоившими индийскую систему и ее алгоритмы для вычислений на бумаге с помощью стилуса. Аллегория Арифметики наблюдает за спором, явно принимая сторону алгориста; ее одеяние украшают новые числовые знаки (см. рис. 1.3). Позже термин «алгоритм» был воспринят учеными высокой европейской культуры, в частности Лейбницем, который его использовал в определении метода дифференциального исчисления[107]. Энциклопедия Д’Аламбера дает «алгоритму» широкое определение:

Арабский термин, используемый некоторыми авторами, в частности испанцами, для обозначения практики алгебры. Также иногда под ним понимается арифметика с использованием цифр… Этим же словом принято в общем обозначать метод и запись всех видов расчетов. В этом смысле мы говорим: алгоритм интегрального исчисления, алгоритм экспоненциального исчисления, алгоритм синусов и т. д.[108].

Техники и приемы выполнения расчетов вручную, которым по сей день учат в школе, представляют собой набор алгоритмов для манипулирования числовыми знаками. Алгоритмы обладают рекурсивной структурой, которая может обрабатывать бесконечную или приближенную цифровую запись, как это происходит при делении простых чисел: 2/3 = 0,666666666… Простая непрерывная форма этой дроби показывает, что даже рациональные числа нельзя вычислить и выразить без помощи алгоритма. Точнее, даже способ записи чисел в системе счисления представляет собой алгоритм – в этом случае алгоритм представления простых величин. Например, когда мы записываем число 101 в индийской системе счисления, этот простой знак следует переводить следующим образом:

Рассмотрим линейную последовательность позиций, которые должны занимать символы величин, идущие справа налево. Каждая позиция представляет постепенно возрастающую степень десяти и может наполняться одной из десяти порядковых единиц: 0, 1, 2, 3, 4, 5, 6, 7, 8 или 9. Первая позиция – десять в степени нуля (то есть одна из «обычных» единиц), вторая позиция – десять в степени один (десятки), третья – десять в степени два (сотни) и так далее. Значение числа, представленного таким образом, определяется сложением каждой единицы после возведения в степень десяти, представленную занимаемой позицией. Когда числа выражаются таким образом, шкала степеней десяти не указывается явно и остается подразумеваемой.

Таким образом, число 101 равно: (1 х сто) + (0 х десять) + (1 х один). Это развернутое объяснение десятичной системы можно легко приспособить для представления двоичной системы, заменив степень десяти на степень двух, то есть сделав другим лишь одно правило в общей процедуре счисления. В двоичной системе число 101 означало бы другую величину:

Рассмотрим линейную последовательность позиций, которые должны занимать символы величин, идущие справа налево. Каждая позиция представляет постепенно возрастающую степень двух и может наполняться одной из двух порядковых единиц: 0 или 1. Первая позиция представляет двойку в степени 0 (то есть единицу), вторая позиция – двойку в степени один (два), третья позиция – двойку в степени два (четыре) и так далее. Значение числа, представленного таким образом, определяется сложением каждой единицы после возведения в степень двух, представленную занимаемой позицией. Когда числа выражаются таким образом, шкала степеней двух не указывается явно и остается подразумеваемой.

В этом случае число 101 равно: (1 х четыре) + (0 х два) + (1 х один), то есть 5 в десятичной системе счисления. В обоих развернутых парафразах слова естественного языка используются не для объяснения, а для кодирования правил построения чисел в соответствии с пошаговой инструкцией. Эти парафразы делают видимой процедуру систем счисления, которой обучают в школе главным образом с помощью упражнений и которая обычно не проговаривается. Однако столь педантичное проговаривание десятичных и двоичных счислений помогает сказать нечто непедантичное: все системы счисления по устройству алгоритмичны. Подобно тому, как любое слово подразумевает грамматику, любое число скрывает алгоритм, то есть процедуру представления величин и выполнения операций с величинами. В итоге все числа – алгоритмические числа, поскольку производятся алгоритмами, которые и представляют собой системы счисления. Числовые символы, скажем так, ничего не считают; они занимают позицию согласно процедуре, то есть алгоритму квантификации.