«От абака к цифровой революции»

От абака к цифровой революции (fb2) - От абака к цифровой революции [Алгоритмы и вычисления] (Мир математики - 15) 2916K скачать: (fb2) - (epub) - (mobi) - Бизенц Торра

БизенцТорра «Мир математики» № 15 «От абака к цифровой революции. Алгоритмы и вычисления»

Предисловие

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

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

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

Число 71 прекрасно иллюстрирует эволюцию вычислений и их взаимосвязь с технологиями. Еще в Месопотамии и Древнем Египте предпринимались попытки вычислить 71 с помощью доступных в то время приспособлений. Были получены удивительные результаты: уже Архимед в III веке до н. э. рассчитал приближенное значение 71 с невероятно малой погрешностью в 0,002. С развитием информатики вычислялись всё новые и новые знаки 71: в настоящее время известно несколько триллионов знаков этого числа. Были созданы алгоритмы, позволяющие вычислить любой отдельный знак числа 71.

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

Глава 1 Начало эпохи вычислений. Позиционные системы счисления

Методы вычислений развивались на протяжении многих тысяч лет.

Этот процесс изначально проходил очень медленно, и ему предшествовало развитие систем счисления. Подобно многим другим проявлениям культуры, вычисления и системы счисления возникли в разных частях Земли. Изначально они не были связаны между собой, но затем широко распространились и оказали взаимное влияние друг на друга. Различные системы счисления были известны в Месопотамии, Древнем Египте, Древней Греции, Риме, Индии и других государствах. Им на смену пришли арабские цифры и позиционная система счисления, появление которой произвело переворот, сравнимый с тем, что произвела теория Коперника в астрономии.

Происхождение систем счисления

Цифры и системы счисления появились в древности. У разных культур они различались, а где-то, например у амазонского народа пирахан, цифры отсутствовали вовсе.

Старейшие свидетельства использования чисел — кости с отметками, найденные на археологических раскопках. Древнейшая из подобных находок — кость бабуина, обнаруженная в горах Лебомбо африканского государства Свазиленд во время раскопок в 1973 году, возраст которой оценивается в 35 000 лет. На этой кости нанесено 29 отметок. Считается, что она использовалась для подсчета фаз луны; возможно также, что она применялась в качестве календаря менструального цикла. Эта кость напоминает палочки, которые и поныне в ходу у бушменов Намибии.

Другое примечательное свидетельство — волчья кость, найденная в 1937 году в Вестонице (Моравия). На эту кость нанесено 55 отметок, объединенных в пять групп по пять отметок. После отметки под номером 25 нанесена одна дополнительная. Эта кость является артефактом ориньякской культуры, а ее возраст — порядка 30000 лет. Поблизости от нее была найдена голова мраморной статуи Венеры.

Следующий выдающийся экземпляр — так называемая кость Ишанго, найденная в Конго в 1960 году, возраст которой оценивается не менее чем в 20000 лет.

Кость Ишанго, одно из древнейших доказательств использования чисел, хранится в Королевском институте естественных наук в Бельгии.

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

Сторонники второй теории полагают, что числа возникли в ритуалах. В церемониях участники должны были располагаться в определенном порядке; поэтому сначала появились порядковые числа, а затем количественные. Последняя теория утверждает, что числа возникли в конкретном географическом регионе, откуда распространились по миру. В ней же целые числа делятся на четные и нечетные: нечетные считаются мужскими, четные — женскими. Эта классификация сегодня встречается во многих мировых культурах.

Использование десяти цифр и системы счисления по основанию 10 для представителей современной западной цивилизации кажется крайне логичным и естественным. Нам сложно представить, что эта система была известна не во всем мире.

Однако факты неоспоримы: например, исследования нескольких сотен племен американских индейцев показывают, что они использовали совершенно разные системы счисления, некоторые из которых применялись чаще других. Почти в трети племен была принята десятичная система, однако почти столько же индейцев использовали пятеричную систему (в некоторых случаях пятерично-десятичную). В оставшейся трети племен применялась преимущественно двоичная система (свыше 20 %), затем — двадцатеричная (10 %) и троичная (1 %).

* * *

ПИРАХАН

Эта история больше похожа на сюжет приключенческого романа. В 1970-е годы американский миссионер Дэн Эверетт, который сегодня является одним из ведущих лингвистов современности, прибывает в Амазонию, чтобы изучить удивительный язык племени пирахан и проповедовать туземцам христианство. После семи лет, проведенных с жителями племени, сам Зверей утратил веру. Племя пирахан в высшей степени удивительно: в языке племени, также известном под названием пираха, в отличие от всех известных современных языков отсутствует подчинительная связь. Кроме того, язык содержит всего десять фонем. У туземцев этого племени нет мифов и коллективной памяти. Они упоминают лишь о событиях, которые видели своими глазами они сами или кто-то из известных им людей, а также не представляют себе отдаленное будущее. Но самым удивительным результатом исследований Эверетта оказалось то, что в языке племени полностью отсутствуют числа и способы счета. Например, индейцы племени не различают единственное и множественное число и практически не проводят грань между исчисляемыми и неисчисляемыми предметами. Дэн Зверей рассказал о результатах своего исследования в книге Don't Sleep, There Are Snakes: Life and Language in the Amazonian Jungle, опубликованной в 2008 году.

* * *

С другой стороны, в поисках доказательств существования разных систем счисления совершенно не обязательно изучать далекие племена. В индоевропейских языках слово, означающее «восемь», происходит от слова, означающего «четыре», а латинское слово novem, означающее «девять», по-видимому, происходит от novus — «новый», что опять-таки указывает на использование систем счисления с основанием 4 и 8. Остатки двадцатеричной системы счисления прослеживаются в словах языка басков hogei, berrogei, hirurogei и laurogei, которые означают 20, 40, 60 и 80, в буквальном переводе — 20, 2·20, 3·20, 4·20, а также во французском слове «восемьдесят» — quatre-vingt. Аналогично в английском языке, где используется десятичная система счисления, можно заметить артефакты древности: eleven («одиннадцать») и twelve («двенадцать») происходят от one left — «остался один» и two left — «осталось два» (в том смысле, что они «остались» после 10).

* * *

ПРОИСХОЖДЕНИЕ МАТЕМАТИКИ

Спор о происхождении математики столь же древний, как и сама математика. 06 этой теме много размышляли Геродот и Аристотель. Первый считал, что геометрия возникла в Египте для разделения земель после ежегодных разливов Нила, следовательно, ее появление было вызвано практической необходимостью. Второй, напротив, полагал, что математика была создана жрецами в свободное от богослужений время. По его мнению, математика возникла как умственная деятельность, лишенная практического интереса.

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

* * *

Может показаться, что большие числа появились лишь недавно, а в античных текстах и записях упоминаются лишь сравнительно малые числа, но это совершенно не так. В Оксфордском университете хранится египетский папирус, возраст которого составляет около 5000 лет, с записью о победе фараона Нармера над ливанцами к западу от дельты Нила. В папирусе указано, что египтяне увели 120000 пленных, 400000 волов и 1422000 коз. Сотни тысяч и миллионы также упоминаются в древнеегипетской «Книге мертвых».

Папирус из «Книги мертвых»— сборника религиозных текстов, в котором упоминаются большие числа.

Хотя числа были известны в большинстве культур (пусть и различных систем счисления), дроби практически нигде не использовались. Египтяне рассматривали исключительно дроби вида 1/n; вавилоняне, которые располагали инструментарием, близким к современному, опирались на шестидесятеричную систему (по основанию 60).

Десятичная система, которая в наше время используется для записи дробей, — современное изобретение. В XVI веке математик Симон Стевин опубликовал небольшой труд, в котором изложил, как следует использовать десятичную систему.

Вычисления и вычислительная техника во все времена развивались параллельно с развитием технологий и систем счисления. Применение папируса оказало непосредственное влияние на исчисление и счет в Древнем Египте: система счисления была изменена так, чтобы ее легко было использовать в расчетах на папирусе.

Римская система счисления, напротив, была очень неудобна при записях на бумаге, поэтому для расчетов в этой системе счисления широко использовался абак.

Страница из книги Симона Стевина De Thiende («Десятая»), опубликованной в 1585 году, в которой предлагается новая система обозначений для записи десятичных чисел.

Вычисления в Вавилонии

Область, охватывающая долины рек Тигр и Евфрат на территории современного Ирака, была известна в Древней Греции под названием Месопотамия, что в дословном переводе означало «междуречье». Благодаря расположению между двух полноводных рек регион отличался плодородной почвой. Именно в этом районе образовалась одна из древнейших цивилизаций в истории человечества. Примерно в 3000 году до н. э. в Междуречье возникла письменность, ставшая отражением культуры шумеров. Первые знаки этой письменности представляли собой пиктограммы, графические обозначения предметов, на смену которым позднее пришла клинопись. И вновь причиной изменений стали технологии: новая письменность возникла благодаря появлению новых материалов.

Знаки клинописи записывались на табличках из сырой глины. Изначально знаки наносились палочками из тростника, позднее — клиновидными деревянными палочками (отсюда и название). Эту письменность можно подробно изучить, так как, к счастью, многие таблички прекрасно сохранились. До наших дней дошло примерно 400 000 глиняных табличек из Месопотамии, которые хранятся в музеях всего мира. 400 из них содержат информацию, имеющую отношение к математике. Древнейшие из этих табличек были найдены в городе Урук.

Пример клинописи на шумерской глиняной табличке, датируемой 2600 годом до н. э. На табличке записан договор купли-продажи дома и прилежащего участка.

* * *

ГОРОД-ГОСУДАРСТВО УРУК

Урук, древний город Месопотамии, располагался в долине реки Евфрат всего в 225 километрах от современного Багдада. В период наибольшего расцвета в III тысячелетии до н. э. он был крупнейшим городом мира. В шумерской традиции этот город считался местом рождения Гильгамеша — героя одной из древнейших саг в истории. Кроме этого, Урук называют родиной счета и бухгалтерии. Некоторые ученые полагают, что современное название государства Ирак происходит от шумерского «Урук», однако эта теория крайне противоречива.

Археологический центр Урука — города, где предположительно возникли бухгалтерия и счет.

* * *

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

Символы клинописи для обозначения чисел.

В Вавилонии использовалась шестидесятеричная система счисления, то есть система счисления по основанию 60, в которой каждая цифра соответствовала числу от 0 до 59. Эта система счисления была позиционной: значение одного и того же символа в ней отличалось в зависимости от того, на каком месте он находился. В случае с шестидесятеричной системой значение каждого символа умножалось на 60 в соответствующей степени. Чтобы проиллюстрировать принцип этой системы счисления, рассмотрим в качестве примера число, состоящее из трех шестидесятеричных цифр: (3, 3, 3). В этом числе значение, соответствующее цифре 3, зависит от ее положения. Первая слева цифра 3 соответствует значению 3·60·60, вторая цифра 3 соответствует значению 3·60, третья — значению 3. Следовательно, в десятичной системе счисления это число будет записываться так: 3·60·60 + 3·60 + 3 = 10983.

Названия вавилонских чисел.

Существует несколько теорий, объясняющих происхождение этой системы счисления. Георг Кевич, исследователь ассирийской цивилизации, в 1904 году опубликовал свое доказательство того, что шести десятеричная система счисления является результатом смешения двух предшествующих систем: по основанию 6 и по основанию 10. Однако Джордж Ифра, более поздний труд которого «Всеобщая история чисел» считается классическим, полагает, что гипотеза о системе счисления по основанию 6 не подкреплена фактами, так как эта система почти не использовалась. Согласно его теории, шести десятеричная система воз¬ никла в результате смешивания системы по основанию 12 и системы по основанию 5. Существуют документальные подтверждения тому, что использовались обе эти системы. Если внимательно рассмотреть шумерские числа от 1 до 10, создается впечатление, что в названиях чисел 6, 7 и 9 скрыты следы системы счисления по основанию 5.

Обложка английского издания монументальной «Всеобщей истории чисел», автором которой является историк математики Джордж Ифра.

Следующая таблица взята из «Всеобщей истории чисел». Заметим, что иа — шумерское слово, означающее «пять», используется как основание для представления других чисел путем сложения. Так, шумерское число 6 звучит как иа-хеш, где иа — 5, хеш — 1. Следовательно, на языке шумеров 6 выражалось составным словом «пять-один», что наводит на мысль об использовании пятеричной системы счисления.

Вавилонская система счисления была очень гибкой. Тройка (a, b, с) могла обозначать как а·602 + b·60 + с, так и другое число, в котором используются три последовательные степени числа 60, например а + b·60-1 + с·60-2. Так как с помощью отрицательных степеней можно представить дроби, в последнем случае число (1, 2, 3) соответствует числу 1 + 2/60 + 3/(60·60). Следовательно, с помощью этой системы счисления можно представлять дроби с очень большой точностью.

* * *

ПРИМЕТЫ ДРЕВНОСТИ

Возможно, читатель уже обратил внимание, что шестидесятеричная система счисления вовсе не похоронена в песках Ближнего Востока, а присутствует в нашей повседневной жизни, поскольку мы используем ее ежедневно и даже ежеминутно, когда смотрим на часы. При отсчете времени мы используем систему счисления по основанию 60. Вавилоняне делили сутки на 24 часа, час — на 60 минут, минуту — на 60 секунд. Аналогичная система используется и при измерении углов. Она также была введена вавилонянами и сохранилась до наших дней.

Астрономические часы в итальянском городе Брешиа.

* * *

Однако позиционная система счисления обладает одним недостатком: в ней нужно как-то представить отсутствие значения. В эпоху, когда ноль был неизвестен, устранить это неудобство было не так-то просто. Для обозначения разряда, не содержащего значение, вавилоняне использовали определенный символ. Позднее, примерно в 130 году в Александрии Птолемей использовал для этих целей омикрон — пятнадцатую букву греческого алфавита, внешне напоминающую современную букву О.

В вавилонской системе счисления сохранились связи с пиктографическим письмом, которое бытовало в прошлом и повлияло на внешний облик символов для обозначения цифр. В Вавилоне существовали архаичные и примитивные, но очень эффективные счетные машины. Принцип их действия базировался на размещении в определенном порядке различных предметов, соответствовавших величинам: один предмет обозначал единицу, другой — десяток, третий — шестьдесят и так далее.

Таким образом можно было совершать сравнительно сложные вычисления, достаточные для практических нужд. Судя по всему, символы первой письменной нотации напоминали очертания этих предметов.

Эта теория подтверждается различными открытиями. С начала раскопок дворца Нузи в 1896 году в 90 километрах от Тигра, вблизи современного иракского города Киркук было найдено 5000 клинописных табличек XV и XIV века до н. э. и 200 более древних — XXIV и XXIII века до н. э. Во дворце также был найден глиняный сосуд яйцевидной формы, внутри которого находился ряд одинаковых фигур сферической формы. На сосуде была сделана надпись, обозначавшая количество голов скота.

Знаменитая табличка Плимптон 322, созданная в период с 1824 по 1784 год до н. э., содержит ряд чисел в шестидесятеричной системе счисления, записанных в четыре столбца.

Ровно столько же глиняных фигурок находилось внутри сосуда. В Сузах, городе, который располагался на территории современного Ирана и считается одним из старейших городов мира, были найдены глиняные сосуды с надписями, внутри которых находились различные диски, конусы, шарики и палочки. Когда значение надписей было расшифровано, стало понятно, что они соответствуют определенным числам.

Вавилонская система исчисления была очень развитой. В этом можно убедиться на примере множества табличек, где записана различная информация, связанная с математикой. На многих из них изображены таблицы с числами. Были найдены таблицы умножения, возведения в квадрат и куб, а также таблицы обратных чисел. В некоторых таблицах обратных чисел отсутствуют обратные числа для 7 и 11, которые в системе счисления по основанию 60 записываются бесконечным числом знаков. В других таблицах приводятся приближенные значения этих чисел, большие или меньшие истинных значений. На некоторых были записаны таблицы квадратных корней и степеней чисел. Считается, что таблицы степеней использовались для расчетов логарифмов. Если в таблице не приводилось число, обратное заданному, оно вычислялось с помощью линейной интерполяции чисел, содержащихся в таблице.

Далее приведена таблица умножения на 9, записанная на глиняной табличке, найденной в Ниппуре, которая в настоящее время хранится в Иенском университете. Числа, зафиксированные на табличке, перевела в современную систему счисления историк математики и науки Кристин Пруст. Эта таблица обладает интересными свойствами.

Например, число (1,3), соответствующее умножению 9·7, понимается как 1·60 + 3 = 63; число (7, 30), которому соответствует 9·50, понимается как 7·60 + 30 = 420 + 30 = 450.

В следующем примере, также адаптированном госпожой Пруст, приведена таблица обратных чисел с еще одной таблички, найденной в Ниппуре. В этой таблице 20 означает 20·60-1 = 20/60 = 1/3.

Для вычисления квадратного корня вавилоняне использовали алгоритмический метод, известный в наше время как метод бисекции. Его авторство приписывается многим философам и математикам, среди которых Архит Тарентский и Герон Александрийский. Этот метод также упоминается как метод Ньютона, однако достоверно известно, что его использовали вавилоняне.

Для данного числа N, из которого мы хотим извлечь квадратный корень, находится два приближенных значения а1 и Ь1 квадрат одного из которых больше N, другого — меньше. Далее рассчитывается значение а2 = (a1 + b1)/2, после чего его квадрат сравнивается с N. Если он больше N, то а2 заменяет прежнее значение, большее N. Если же он меньше N, а2  заменяет меньшее из значений. Этот процесс повторяется до тех пор, пока не будет найдено число, квадрат которого точно или с достаточной точностью равен N.

Вавилоняне также умели решать системы уравнений и уравнения второй степени с вещественными корнями. Эти задачи упоминаются в текстах, датируемых примерно 2000 годом до н. э. «Протоматематики» Вавилонии также умели решать некоторые уравнения третьей степени. Уравнения вида x3 = а или х3  + х2 = с решались с помощью таблиц. Более сложные уравнения, имевшие вид ах3 + Ьх2 = с, сводились к уравнениям первых двух видов.

Анализ вавилонских текстов показывает, что математика была для вавилонян не просто средством решения практических задач. В этом заключается ее фундаментальное отличие от древнеегипетской математики, которая считалась намного более утилитарной. Вавилоняне достигли значительных успехов в арифметике и алгебре, но в отличие от египтян не преуспели в геометрии. Знания геометрии в Вавилонии касались лишь немногих фигур, в частности треугольников и четырехугольников.

* * *

УРАВНЕНИЯ ВТОРОЙ И ТРЕТЬЕЙ СТЕПЕНИ

Уравнения второй степени вида ах2 + Ьх + с = 0 обычно решаются с помощью формулы

Эта формула позволяет получить вещественные решения, когда дискриминант положителен или равен нулю, то есть выражение Ь2  — 4ас больше либо равно нулю.

Для решения уравнений вида ах3 + Ьх2 = с вавилоняне умножали уравнение на (а2/Ь3) и получали уравнение вида (ах/b)3 + (ах/b)2 = са2/Ь3 Оно решалось с помощью таблиц для уравнений вида х3 + х2 = с, после чего рассчитывалось значение х.

* * *

Однако труды вавилонян, посвященные окружностям, сохранились до наших дней. Именно вавилоняне разделили окружность на шесть частей построением окружностей радиуса, равного радиусу исходной окружности. Каждая из этих частей делилась на 60; таким образом, вся окружность делилась на 360 градусов. Так как использовалась шести десятеричная система, то градусы делились на 60 минут, минуты — на 60 секунд. В качестве приближенного значения π использовалось значение π = 3, хотя в табличке, найденной в Сузах, путем сравнения периметра шестиугольника и длины окружности получено значение π = 31/8.

Построение шестиугольника, вписанного в окружность. Сторона шестиугольника равна радиусу окружности.

Вычисления в Древнем Египте

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

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

Египетская система счисления была аддитивной, в отличие от нашей системы счисления, которая, подобно вавилонской, является позиционной. В аддитивной системе счисления, например, число 3204 представляется в виде 1000 + 1000 + 1000 + 100 + 100 + 1 + 1 + 1 + 1. В виде египетских иероглифов оно записывается так:

С помощью этой системы можно было записывать большие числа. Кроме того, упрощались операции сложения и вычитания. При сложении чисел значения «переносились» в старший разряд, при вычитании — «забирались» из старших разрядов. Умножение сводилось к сложению и вычитанию интересным, но непростым способом.

Рассмотрим, как выполнялось умножение, на примере чисел 17 и 53. Нужно взять пару чисел 1 и 53 и удвоить их. Результатом удвоения будут числа 2 и 106. Повторив эту операцию, получим 4 и 212. Нужно удваивать числа до тех пор, пока первое из них не превысит 17. После этого процесс прекращается, а результат, полученный на последнем шаге, игнорируется. Результатом этих действий в нашем примере будут следующие пары чисел.

Теперь нужно определить, как можно получить 17 путем сложения чисел из первого столбца. Единственный возможный способ получить 17 — сложить 1 и 16. Следовательно, для получения результата умножения нужно сложить значения, записанные справа от 1 и 16, то есть 53 и 848. Их сумма равна 901. Таким образом, результат умножения 17 на 53 равен 901.

Можно заметить, что число 17 рассматривается как сумма степеней двойки, а те, в свою очередь, умножаются на 53. Так, разложение числа 17 выглядит следующим образом: 17 = 20 + 24. При сложении в качестве слагаемых выбираются значения (20  + 24)·53, остальные произведения, 21·53, 22·53 и 23·53, не используются, так как не входят в разложение числа 17. Этот алгоритм аналогичен тому, что используется в компьютерах. Результат этого алгоритма верен, поскольку представить любое число в виде суммы степеней двойки можно единственным образом. Следовательно, в нашем примере существует единственное множество значений, сумма которых равна 17. Поэтому значения из правого столбца таблицы, которые мы складываем, также можно выбрать только одним способом. Этот метод умножения известен под названием египетского умножения.

Деление выполнялось как операция, обратная умножению. В качестве примера приведем те же числа. Попробуем разделить 901 на 17. Результат должен равняться 53. Результатом деления является целое число без знаков после запятой.

В качестве исходных берется знаменатель 17 и 1. Далее аналогично прошлому примеру оба эти числа удваиваются. Результатом будет 34 и 2. Далее это действие повторяется, результат будет равен 68 и 4. Эти действия повторяются до тех пор, пока первое значение не станет больше числителя, который в нашем примере равен 901. Когда первое значение становится больше числителя (901), полученная пара чисел игнорируется. Результат алгоритма приведен ниже.

Следующая пара чисел — 1088 и 64 — отбрасывается, так как первое число больше 901. Далее нужно подобрать такие числа из первого столбца, чтобы их сумма равнялась 901. В нашем примере это 544, 272, 68 и 17 (так как 544 + 272 + 68 + 17 = 901). Сумма соответствующих им чисел из правого столбца и будет результатом деления. Результат равен 32 + 16 + 4 + 1 = 53.

Как и в случае с умножением, разложение числа 901 является единственным. Мы представили 901 как сумму степеней двойки, умноженных на 17, при этом сумма этих степеней двойки равна 53. Результатом деления в этом случае является целое число. В случаях когда это невозможно и результат содержит несколько знаков после запятой, в этом алгоритме учитываются дроби. Однако алгоритм работы с дробями, который использовали египтяне, был намного сложнее современного. За некоторыми исключениями, рассматривались только дроби вида 1/n, то есть дроби, числитель которых равен 1. Любопытно, что причиной этому было ограничение, вызванное способом записи дроби: сначала записывался символ для обозначения дроби, затем — символы, соответствующие числу в знаменателе. Информация о числителе не записывалась, поэтому он мог равняться только единице.

Для обозначения дроби египтяне использовали этот символ:

Рядом с ним записывался знаменатель, в нашем примере это 21:

Так египтяне записывали дробь 1/21.

Мы упомянули, что существовали дроби с числителем, отличным от 1. Речь идет о дроби 2/3, которая обозначалась отдельным символом, и о дроби вида n/(n + 1), обратной дроби (1 + 1/n). Иными словами, 1/(1 + 1/n) = 1/((n + 1)/n) = n/(n + 1).

Важность дробей и действий с ними четко прослеживается в папирусе Ахмеса, который начинается с представления дроби 2/n в виде суммы 1/x + 1/y + … + 1/z для всех нечетных n от 5 до 101. Далее приводятся аналогичные представления для дробей вида n/10 при n от 2 до 9.

* * *

ПАПИРУС АХМЕСА

В этом знаменитом египетском папирусе длиной 6 метров приводится 87 разнообразных задач с решениями. Он был написан в период с 2000 по 1800 год до н. э. Его автор Ахмес указывает, что он воспроизводит знания, насчитывающие более двух сотен лет, необходимые для будущих писцов. Таким образом, папирус Ахмса можно считать примитивным учебником по математике. В настоящее время папирус хранится в Британском музее, куда он поступил из коллекции Генри Райнда в 1858 году. (По имени владельца его еще называют папирусом Райнда.) В нем также объясняются действия с дробями.

* * *

Папирус Ахмеса содержит информацию о выполнении действий с дробями, а также позволяет получить представление о типичных задачах, которые решали египтяне, и о способах их решения. Первые задачи папируса Ахмеса — это задачи о делении чисел на 10. При их решении использовалась уже упомянутая таблица чисел вида п/10. Далее приводятся некоторые задачи из арифметики и геометрии, а также задачи, которые можно решить с помощью линейных уравнений вида ах + Ьх = с. Некоторые из задач папируса Ахмеса содержат неизвестные, возведенные в квадрат (в современной нотации), однако, несмотря на это, считается, что египтяне не умели решать уравнения второй и третьей степени.

Большинство задач решаются методом, который сейчас известен как метод ложного положения. Лишь задача 30 решается современным способом — с помощью факторизации и деления. Чтобы объяснить метод ложного положения, рассмотрим в качестве примера задачу 24, которая в наши дни решается с помощью линейного уравнения. Задача звучит так:

«Определите цену кучи, если куча и седьмая часть кучи стоит 19».

В современной нотации условие задачи записывается так: х + 1/7х = 19.

Метод ложного положения заключается в следующем. Мы предполагаем, что неизвестная равна определенному числу, и вычисляем результат для этого значения неизвестной. Так как выбранное нами значение неверно, результат также будет ошибочным, поэтому мы скорректируем значение переменной так, чтобы получить верный результат. Допустим, что цена кучи в нашей задаче равна 7, то есть х = 7. Цена кучи и ее седьмой части будет равна 8. Иными словами, при х = 7х + 1/7x = 8. Далее нужно определить, как следует изменить выбранное нами значение 7, чтобы результат выражения был равен 19, а не 8. Нужно умножить 8 или х на 19/8. Используя только дроби с числителем, равным 1, получим, что 2 + 1/4 + 1/8 = 19/8. Умножив 7 на (2 + 1/4 + 1/8), получим 16 + 1/2 + 1/8. В папирусе также показывается, что это решение верно, так как это значение и его седьмая часть в сумме дают 19.

* * *

ЧИСЛО τ В ЕГИПТЕ

В папирусе Ахмеса приводится древнейшее приближенное значение числа τ, которое несколько больше известного нам: оно равняется 256/81, то есть 3,1604. Возможно, эта оценка является самой древней, но не самой точной. В последующих документах приводятся более точные значения. Из них наиболее близко к истинному 3 + 1/7.

* * *

Все эти расчеты можно было выполнить благодаря изобретению папируса. Ранее использовались таблички из глины, воска и других материалов и выполнять подобные операции на них было сложно и неудобно. Египтяне могли писать на папирусе почти так же, как мы делаем записи на бумаге. Для записи на папирусе было создано иератическое письмо — упрощенное иероглифическое письмо, которое использовали писцы в государственных учреждениях. Позднее появилось демотическое письмо, которое, как следует из названия, использовали простолюдины («демос») в повседневной жизни, а иератическое письмо применялось только для записи религиозных текстов. В ходе упрощения письма форма записи чисел изменилась, и стало возможным появление цифр.

Папирус Эберса (слева), датируемый XVI веком до н. э. Он содержит медицинский текст и является примером иератического письма. В отличие от него Розеттский камень, датируемый II веком до н. э., содержит три типа письма: иероглифическое, демотическое и греческое.

В демотическом письме была решена проблема исходной египетской нотации, в которой каждая степень 10 обозначалась отдельным символом, поэтому для записи, например, числа 9 требовалось девять раз записать символ единицы, для записи числа 99 — девять раз записать символ десятки и девять раз — символ единицы. В демотическом письме были введены отдельные символы для чисел от 1 до 9, для десятков от 10 до 90, аналогично для остальных степеней десяти. Для представления чисел требовалось запоминать соответствующие символы. Может показаться, что запомнить столько символов было непросто, но это не было чем-то непривычным для египетских математиков. Например, для записи сумм и разностей в папирусе Ахмеса используются изображения камней на разных позициях.

Греция

Фундаментом греческой математики были вавилонская и египетская математика. Математические методы, созданные египтянами, попали в Грецию благодаря торговле, достигшей расцвета в период между 700 и 600 годом до н. э. Это был золотой век обмена знаниями, когда многие греческие математики совершали путешествия в Египет, чтобы познать секреты тысячелетней мудрости.

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

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

С другой стороны, влияние вавилонян прослеживается в греческой астрономии. Именно через Древнюю Грецию вавилонская шестидесятеричная система дошла до наших дней. Слова «минута» и «секунда» имеют греческое происхождение, но в современные языки они попали из латыни. Они впервые упоминаются в источнике XIII века, где одна шестидесятая часть обозначалась как «первая меньшая часть», шестидесятая часть от шестидесятой части — «вторая меньшая часть» и так далее. На латыни эти фразы звучат как pars minuta prima, pars minuta secunda и так далее. Так появились знакомые нам слова «минута» и «секунда». Следует заметить, что в действительности эти слова дошли до наших дней несколько более сложным путем. Латинский текст XIII века был переведен не с греческого, а с арабского подстрочника исходного греческого текста. И снова мы видим, что наследие Античной Греции стало известно западной цивилизации благодаря арабам, бережно охранявшим его на протяжении веков.

Греческая система счисления появилась около 500 года до н. э. в Ионии и была схожа с египетской иератической системой. Например, числа от 1 до 9 обозначались отдельными символами; десяткам от 10 до 90 и сотням от 100 до 900 также соответствовали отдельные символы. В качестве символов использовались буквы греческого алфавита и три буквы финикийского алфавита: дигамма (обозначавшая 6), коппа (обозначавшая 90) и сампи (обозначавшая 900).

С помощью греческих символов можно было записать любое число от 1 до 999.

Для записи тысяч использовались те же символы, перед которыми ставилась запятая. Так, выражение «α» обозначало 1000, «β» — 2000 и так далее. Эта система счисления, как и египетская, была аддитивной; таким образом, число ρκε обозначало 125, так как ρκε = ρ + κ + ε = 100 + 20 + 5. В следующей таблице приведены буквы, соответствующие основным числам.

Для представления чисел, кратных 10000, вплоть до 99990000, использовалась буква М: перед ней записывалось число, которое затем умножалось на 10000.

Буква М обозначала 10000 и происходила от слова «мириада» (греч. myriás — μυριασος), означавшего «сто сотен». В альтернативной записи буквы записывались над буквой М. Например,

а также

Для записи еще больших чисел использовались две буквы М, означавшие 10 0002.

В египетской нотации порядок следования цифр не имел значения, однако в греческой нотации цифры записывались слева направо, как при письме. Цифры, записанные слева, имели больший «вес». Благодаря этому стало возможным отказаться от запятых: они не записывались, если значение числа можно было однозначно понять без них. Однако числа записывались буквами, поэтому иногда их было непросто отличить от обычного текста. Для этого греки ставили пометку в конце числа или добавляли горизонтальную черту поверх него. Так, число 871 записывалось как

или как

Эта нотация не способствовала развитию исчисления и записи чисел на бумаге.

Считается, что для решения арифметических задач греки использовали главным образом абак, а математики должны были использовать символы.

Умножение в Древней Греции выполнялось иначе, чем в наши дни. Сегодня мы складываем произведения первого множителя на каждую из цифр второго множителя. Греки, напротив, умножали второй множитель на каждую цифру первого. Так как вместо цифр использовались символы, значение которых зависело от позиции (в записи «πσ» π означало 80, а не 8), результат при промежуточном умножении получался сразу, без дополнительных действий.

Допустим, мы хотим вычислить произведение 24·53 (в греческой нотации это эквивалентно произведению κδ и νγ). Сначала нужно умножить κ, то есть 20, на цифры числа 53, то есть 20·ν и 20·γ (в современной нотации — 20·50 и 20·3). Далее аналогично рассматривается вторая цифра первого множителя: 8, обозначающая 4, умножается на ν, затем 8 умножается на γ (в современной нотации 4·50 и 4·3).

Затем промежуточные результаты складываются. В современной нотации это записывается так:

24·53 = (20 + 4)·(50 + 3) = 20·50 + 20·3 + 4·50 + 4·3 = 1272.

В графическом виде умножение в греческой нотации выглядит так:

Использование 27 символов затрудняло вычисление промежуточных результатов, так как греческая таблица умножения должна была содержать 27·27 = 729 ячеек. Считается, что именно по этой причине решающую роль в развитии вычислений сыграл абак. Греческие абаки представляли собой таблички из нескольких столбцов, в которых располагались камешки или фишки. Каждому столбцу соответствовала степень 10; также имелись отдельные столбцы для дробей.

Этот абак, который представляет собой мраморную табличку, был найден на греческом острове Саламин в 1846 году.

Ученым удалось изучить эти таблички, так как некоторые образцы, например абак с острова Саламин, дошли до наших дней и, кроме того, содержат информацию о значениях, соответствующих столбцам. В этом абаке с острова Саламин каждый столбец означает определенное количество греческих монет. Большие столбцы обозначают (справа налево) 1, 10, 100, 1000 и 10 000 драхм, затем 1, 10, 100, 1000 и 10 000 талантов (один талант равнялся 6000 драхм). Малые столбцы соответствуют дробям. Использовались следующие дробные части драхмы: обол (один обол равнялся 1/6 драхмы), половина обола, четверть обола и халкус (один халкус равнялся 1/8 обола). Камешки, расположенные под линией, обозначают единицу; расположенные над линией — пять единиц. Следовательно, на следующей схеме представлено число 502158 + 2 обола + + 1/2 обола + 1 халкус.

При сложении с помощью абака камешки ставились рядом в соответствии с их позицией. Когда в нижней части накапливалось пять единиц, они заменялись одной единицей в верхней части, а две единицы в верхней части заменялись одной единицей в следующем разряде. При вычислениях с помощью абака следовало помнить, что 6000 драхм равняются одному таланту, а 6 оболов — одной драхме.

Таблица из «Альмагеста» — труда по астрономии, написанного Клавдием Птолемеем во II веке, в котором используются дроби.

Как и вавилонянам, грекам были известны шести десятеричные дроби, о чем упоминает Птолемей в своем «Альмагесте», однако в математических вычислениях греки использовали египетскую систему. В комментариях к трактату Архимеда Евтокий Аскалонский использует

для обозначения 1838 + 1/9 + 1/11, а

для обозначения 2 + 8/11 + 8/11 + 1/99 + 1/121.

Греки и число π

Геометрия в Древней Греции находилась на очень высоком уровне развития, и грекам удалось получить более точную оценку числа π, чем их предшественникам. Архимед доказал, что число π лежит в интервале 3 + 10/71 = 223/71 < π < 3 + 1/7 = 22/7 (что соответствует среднему значению 3,141851), а Птолемей получил приближенное значение, равное 3,141666. Эти значения были получены с помощью двух правильных многоугольников (вписанного и описанного).

Гоавюры, посвященные Архимеду (слева) и Птолемею (справа).

Архимед исходил из того, что шестиугольник, вписанный в окружность единичного радиуса, имеет периметр, равный 6, а описанный шестиугольник — 4·√3. Следовательно, число π лежит в интервале от 3 до 2·√3. Он учитывал, что квадратный корень из 3 удовлетворяет следующему неравенству: 265/153 < √3 < 1351/780. Далее он перешел к правильным многоугольникам с большим числом сторон. Выбрав в качестве исходной фигуры шестиугольник, Архимед последовательно удваивал число его сторон, рассмотрев правильные многоугольники с 12, 24, 28 и 96 сторонами. С помощью правильного 96-угольника он получил приближенное значение 6336/(2017 + 1/4)< Я < 14688/(4673 + 1/2). Так как 3 + 10/71 < 6336/(2017 + 1/4) < π < 14688/(4673 + 1/2) < 3 + 1/7, он выбрал эти два значения в качестве границ интервала, в котором находится π. Птолемей рассматривал многоугольник с 360 сторонами.

Греки и простые числа

Простые числа — это натуральные числа, которые делятся только на единицу и сами на себя. Единица по определению не считается простым числом. Любое натуральное число можно представить в виде произведения простых чисел единственным образом (без учета перестановок множителей). Так, например:

120 = 5·3·2·2·2 = 2·5·2·2·3.

* * *

ПРОСТЫЕ ЧИСЛА, МЕНЬШИЕ 1000

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

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.

* * *

Греки изучили простые числа подробнейшим образом: они дали им определение и доказали их важнейшие свойства. Считается, что они были известны древним египтянам, однако не сохранилось никаких результатов, связанных с простыми числами, которые были бы получены предшественниками древних греков.

В 300 г. до н. э. Евклид, который работал в Александрии во времена правления Птолемея I (323–283 гг. до н. э.), в эпоху слияния египетского и греческого, обнаружил самое удивительное и важное свойство простых чисел. Он изложил его в своем трактате «Начала геометрии» — одном из важнейших трудов в истории математики. В нем заложены основы евклидовой геометрии, которая использовалась во всем мире на протяжении следующих двух тысяч лет. В предложении 20 книги IX «Начал» доказывается, что простых чисел бесконечно много.

Евклид рассматривает множество простых чисел S = {р1, р2…, рn} и показывает, что число N = p1·р2·… ·рn + 1 не делится на р1, поскольку при делении на p1  остаток равен 1. Аналогично N не делится на р2 …., рn, так как при делении N на р2…,рn остаток будет равен 1. Следовательно, N либо простое, либо является произведением простых чисел, не содержащихся в S. Таким образом, множество S не содержит в себе все простые числа. Так как S было выбрано произвольно, конечного перечня простых чисел не существует. Как следствие, перечень простых чисел бесконечен.

Фрагмент «Афинской школы» Рафаэля, на котором изображен автор знаменитых «Начал геометрии» Евклид.

Рим

Математика и математическая нотация в Древнем Риме не были столь развитыми, как в Греции и Вавилоне. Центр империи, столь плодородной в других областях, не подарил миру ни одного выдающегося математика. Во времена Рима важные события в математике происходили не в столице, а на периферии, в районах, где ощущалось влияние Греции и продолжались традиции греческой математики. Считается, что римская математика принадлежит к совершенно обособленной традиции и не связана ни с греческой, ни с вавилонской, а имеет этрусское происхождение. Основными авторами этого периода, продолжавшими греческие традиции, были Клавдий Птолемей, автор уже упомянутого «Альмагеста», Диофант и Папп Александрийский.

Диофант был автором книги под названием «Арифметика», Папп написал восемь книг с комментариями к трудам классических авторов.

Сам Цицерон признавал ограниченность римской математики в своих «Тускуланских беседах». Он пишет:

«Далее, выше всего чтилась у греков геометрия — и вот блеск их математики таков, что ничем его не затмить; у нас же развитие этой науки было ограничено надобностями денежных расчетов и земельных межеваний» («Тускуланские беседы», I, 5).

Пон-дю-Гар. Фотография Эдуарда Бальдю, середина XIX века. Этот акведук, который также служил мостом для экипажей, был построен римскими инженерами, которые в своих работах использовали математические знания Античности.

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

Римская нотация очень популярна, так как она широко используется и поныне. Римские цифры приведены в таблице ниже.

Позднее, после изобретения книгопечатания, символ |) был заменен на D. (|) — на М. Также были созданы обозначения для больших чисел. Черта, проведенная над числом, означала умножение на 1000; вертикальные черты с двух сторон — умножение на 100. Например, |LV | означало 5500. Кроме того, была введена запись меньших цифр слева, равносильная вычитанию. Например, ХС записывалось вместо LXXXX, а IV — вместо IIII.

* * *

МАРК ВИТРУВИЙ

Знаменитый архитектор и писатель Витрувий (80–15 гг. до н. э.) служил в легионах Юлия Цезаря и подчинялся ему лично. Он оставил потомкам труд «06 архитектуре». В десяти книгах этого труда излагаются различные вопросы этой дисциплины, начиная от механизмов и материалов и заканчивая элементами урбанистики и пейзажистики.

Издание «Об архитектуре» Витрувия 1561 года.

* * *

Выполнять арифметические действия с римскими цифрами было непросто. Вероятно, вычисления производились с помощью абаков или табличек, а римские цифры использовались только для записи исходных значений и результатов. Римские таблички для вычислений напоминали греческие. На табличках были нанесены линии; камешки, расположенные на линиях, соответствовали единицам, а те, что располагались между линиями, — 5 единицам. Таблички делились на две части. В правой части записывалось число, которое требовалось прибавить, в левой части — результат.

На иллюстрации, приведенной ниже, слева записано число 2907, справа — 43. Результат получался перемещением всех камушков в левую часть и последующим сдвигом (5 камней на линии были эквивалентны одному камню между линиями, два камня между линиями — одному камню на линии выше). В нашем примере результат сложения равен 2950.

Помимо табличек, римляне также использовали разновидность абака — металлические или деревянные таблички с бороздками, в которых располагались небольшие камни, обозначавшие числа. Может показаться парадоксальным, но эти камушки сыграли большую роль в математике: латинское слово «камень» звучало как calx, а от его уменьшительной формы, calculus, означавшей «небольшой камень», или «камушек», в частности, происходит современное слово «калькулятор».

Математика в Александрии

У греческих математиков в Римской империи не нашлось достойных последователей. Великие открытия, совершенные в течение этого длительного периода продолжительностью почти в восемь столетий, были заслугами математиков Древней Греции. В то время одним из важнейших научных центров была Александрия, где располагались музей и библиотека. Некоторые известные греческие математики, жившие в эпоху заката Римской империи, работали именно в Александрии.

Уже упомянутый Папп Александрийский, живший в начале IV века, попытался обновить греческую математику и создал сборник комментариев и толкований классических текстов. В его трудах приведены более подробные доказательства, которые помогают читателю понять труды древних. К сожалению, его идея окончилась неудачей: за ним последовали лишь немногие известные математики.

* * *

ГИПАТИЯ АЛЕКСАНДРИЙСКАЯ

Гипатия (ок. 370–415) — дочь математика и философа Теона Александрийского, от которого она унаследовала талант и любовь к наукам. Она была язычницей в то время, когда официальной религией Римской империи уже было христианство, а язычество преследовалось. Несмотря на это, Гипатию не затронули религиозные противоречия, и среди ее учеников был даже будущий епископ Синезий. Тем не менее в 415 году Гипатия оказалась вовлечена в политическое противостояние между христианским патриархом Кириллом и римским префектом Орестом, который был ее другом и учеником. Чтобы навредить Оресту, кто-то пустил слух, что Гипатия — ведьма, и она была зверски растерзана толпой во время Великого поста.

На этом фрагменте «Афинской школы» Рафаэля изображена Гипатия Александрийская в белой тунике.

* * *

Одним из немногих блестящих математиков, живших позднее Паппа, была знаменитая Гипатия, среди трудов которой выделяются комментарии к Аполлонию Пергскому («О конических сечениях») и к «Арифметике» Диофанта. Она также помогла отцу при написании комментариев к «Альмагесту» Птолемея. После убийства Гипатии в 415 году, отдавшей жизнь ради науки, и разрушения Александрийского музея и библиотеки в IV–VII веках (точное время неизвестно) наследие греческих математиков было предано огню и похоронено под руинами, откуда его бережно извлекли арабы.

Китай

Математика сыграла фундаментальную роль в истории Китая, полной научных и технических открытий, часто опережавших свое время. Со времен династии Хань (206 г. до н. э. — 220 г. н. э.) условием получения государственной должности была успешная сдача непростого экзамена, а не семейные связи, как можно было бы ожидать.

В таких экзаменах особое внимание уделялось классической китайской литературе, а также, что примечательно, математике. Может показаться невероятным, но эти экзамены сохранились до наших дней. Разумеется, их целью была не оценка творческих способностей в математике. Как правило, при подготовке к экзамену требовалось заучить определенные задачи и их решения. Логично, что в Китае разделяли типично восточные взгляды на науку, свойственные вавилонянам и египтянам, которые рассматривали науку с чисто практической точки зрения. Несмотря на это, ничто не могло помешать представителям столь богатой культуры совершить собственные математические открытия в поиске новых, более эффективных методов решения всё более и более сложных задач.

Важнейшим математическим трудом Древнего Китая является «Математика в девяти книгах». Jiu zhang suanshu (так звучит название этой книги на языке оригинала) — это классический труд, который использовали многие поколения китайских математиков вкупе с комментариями и аннотациями Лю Хуэя (III в. н. э.).

В 1983 году в гробнице 186 года до н. э. было найдено 190 бамбуковых пластинок с математическими текстами. Каждая пластинка имела 30 сантиметров в длину и 6–7 миллиметров в толщину. Всего на них было записано примерно 7000 иероглифов. Пластинки изначально были скреплены между собой по порядку и свернуты, однако на раскопках гробницы они были найдены в беспорядке, поскольку соединявшие их нити истлели от времени. Ученым пришлось немало поломать головы, чтобы восстановить исходный порядок расположения пластин.

Репродукция XVIII века одной из задач китайского математика Лю Хуэя, в которой требуется измерить высоту берега острова.

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

* * *

ЗАДАЧА ИЗ «МАТЕМАТИКИ В ДЕВЯТИ КНИГАХ»

Следующая задача, приведенная в свитках 34 и 35 «Математики в девяти книгах», может служить примером того, какие вопросы рассматривались в этой книге. Она звучит так: «Лиса, лесная кошка и собака должны заплатить на таможне 111 монет. Собака говорит кошке, а кошка говорит лисе: Твоя шкура вдвое дороже моей, ты должна заплатить в два раза больше”. Сколько должен заплатить каждый?»

* * *

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

Числа и система счисления в Китае

Древнейшая форма вычислений, которая бытовала в Древнем Китае, восходит к IV веку до н. э. Для вычислений использовались палочки, известные как суань  или чоу . Со временем на смену этим палочкам пришел абак. Эти палочки, которые располагались горизонтально и вертикально, обозначали цифры от 1 до 9.

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

Во второй системе за основу было взято горизонтальное положение палочек, как показано далее. Здесь тоже представлены числа от 1 до 9.

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

Как вы можете видеть, в записи чисел участвовали обе системы одновременно: вертикально расположенные палочки обозначали единицы, сотни и так далее; палочки, расположенные горизонтально, — десятки, тысячи и следующие разряды. Если одна из цифр равнялась нулю, соответствующая позиция оставалась пустой, как вы можете видеть на примере записи числа 4508. Аналогичным образом записывались отрицательные числа. Положительные и отрицательные числа различались цветом палочек: для записи положительных чисел использовались красные палочки, для записи отрицательных — черные.

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

Система вычислений с помощью палочек также появилась в Корее и Японии (точный период неизвестен). Известно, что эта система применялась в Японии в период правления императрицы Суйко (593–628) под названием санги.

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

Учитель объясняет ученикам китайской школы округа Чжэньцзян, как пользоваться абаком. 1938 год.

Китайский абак появился в Японии примерно в XVI веке и был известен как соробан. Он появился благодаря торговцам, однако его распространение было непростым. Лишь спустя много лет он был введен в школах и начал использоваться для решения сложных математических задач. В торговле соробан быстро заменил ранее применявшиеся устройства, однако они по-прежнему использовались в высшей математике.

Для обозначения цифр и в Китае, и в Японии (системы счисления в этих странах очень похожи) использовались девять идеограмм.

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

При записи чисел использовались символы от 1 до 9 вместе с символами десятков, сотен и так далее. Например, число 10563 записывалось следующим образом:

что расшифровывается так:

Следует упомянуть, что в отличие от системы, используемой в большинстве европейских языков, в основе которой лежит тысяча (103), в китайской системе в основе кратных величин лежит 104. Следовательно, 132000 записывается как 13·(104) + 2000.

В виде идеограмм это число будет представлено так:

Число π в Китае

Китайцы разработали алгоритмы для вычисления числа π. Великий математик Лю Хуэй, живший около 300 года во времена царства Вэй, возникшего после распада империи Хань, первым создал метод вычисления числа π. Живший до него ученый и изобретатель Чжан Хэн (78—139), который создал прибор для определения землетрясений за 1700 лет до появления первого сейсмографа, получил приближенное значение π, равное 3,1724. Также использовались значения 3,162 (корень из 10) и 3,156. В III веке астроном Вань Фань, живший в царстве У, использовал последнее значение, равное дроби 142/45.

Первый метод, использованный Лю Хуэем для нахождения приближенного значения π, заключался в бисекции многоугольников. С помощью многоугольника с 96 сторонами он вычислил, что π лежит в интервале между 3,141024 и 3,142708. Он использовал приближенное значение, равное 157/50, так как считал значение 3,14 достаточно точным.

Китайские марки, посвященные ученым Лю Хуэю (слева) и Чжану Хэну (справа).

Лю Хуэй использовал шестиугольник со стороной L, вписанный в окружность. Далее число сторон многоугольника последовательно удваивалось. Иными словами, сначала рассматривался шестиугольник, затем 12-угольник, далее — 24-угольник (24 = 12·2), 48-угольник (48 = 24·2) и так далее. На каждом шаге Лю Хуэй вычислял площадь многоугольника с N сторонами и длину стороны многоугольника с числом сторон, равным 2N.

Будем обозначать за l длину стороны многоугольника с 2N сторонами. Используем теорему Пифагора: для данного прямоугольного треугольника с гипотенузой h и двумя катетами длиной с1 и с2 выполняется равенство h2 = с12 + с22.

Вычисление длины стороны l по известному значению L, где L — длина стороны шестиугольника, I — длина стороны 12-угольника,

О — центр окружности, А и В — две вершины шестиугольника, С — новая вершина, Р — точка на стороне шестиугольника, равноудаленная от А и В. Радиус окружности равен r, расстояние от центра до Р равно R.

На рисунке обозначены центр окружности О и сторона шестиугольника (длиной L). Ее концы обозначены А и В. Точки ОАВ определяют треугольник. Далее вычисления выполняются следующим образом.

Шаг 0. Будем рассматривать многоугольник с N = 6 сторонами, длина его стороны L известна.

Шаг 1. Разделим сторону АВ на две равные части. Обозначим середину стороны АВ точкой Р.

Шаг 2. Вычислим длину отрезка ОР и обозначим ее длину за R. Для этого применим теорему Пифагора. Нам известно, что гипотенуза треугольника ОАР равна r, один из катетов равен L/2, длина другого, которую мы хотим вычислить, равна R. По теореме Пифагора г2 = R2 + (L/2)2. Отсюда имеем R2 = r2 — (L/2)2, следовательно

Шаг 3. Рассмотрим радиус окружности, который проходит через точку Р. Точка пересечения этого радиуса и окружности будет вершиной многоугольника с 2N сторонами. Обозначим эту точку С. Зная R, мы можем вычислить длину отрезка PC. Обозначим ее за р. Так как длина ОС равна r, длина PC равна

Шаг 4. Длину отрезка АС можно определить по теореме Пифагора. Как мы уже говорили, будем обозначать длину этого отрезка за l. В рассматриваемом прямоугольном треугольнике гипотенуза равна l, катеты — L/2 и р. Следовательно,

Шаг 5. Выразив l из последнего равенства, получим длину многоугольника с 2N сторонами:

Шаг 6. Площадь многоугольника с N сторонами можно вычислить на основе площади треугольника ОАВ. Площадь многоугольника будет в N раз больше площади этого треугольника. Площадь треугольника ОАВ, очевидно, равна половине произведения его основания на высоту. Длина основания АВ равна L, высота равна R (это значение мы уже вычислили). Следовательно, площадь многоугольника равна

N·площадь треугольника ОАВ = N·(L·R)/2.

Шаг 7. Далее нужно вернуться к шагу 2 и принять N = 2N, L = l. Чтобы определить значение π, нужно учесть, что площадь круга равна π·r2. Следовательно, для r = 10 площадь круга равна π·100.

Если начать с r = 10 (в этом случае L = 10), с помощью вышеприведенного алгоритма мы получим значения площадей, представленные в таблице ниже. В этой таблице используется современная нотация, Лю Хуэй в своих расчетах применял дроби. Он заметил, что для данного многоугольника с 2N сторонами длиной l, построенного на основе многоугольника с N сторонами длиной L, площадь круга (обозначим ее за С) удовлетворяет следующему неравенству:

площадь (2N) < С < площадь (2N) + избыток.

Избыток в этом неравенстве соответствует 2N треугольникам площадью р·(L/2)/2. Напомним, что р = r — R. Получим значение избытка, равное 2·N·(р·(L/2))/2. Эти значения также приведены в таблице. Разница между площадью 96-угольника и 192-угольника очень мала, поэтому Лю Хуэй счел π = 3,14 достаточно точным.

Лю Хуэй заметил, что между последовательными избытками наблюдается определенное соотношение. В частности, он установил, что отношение между данным и следующим избытком примерно равно 1/4 = 0,25. Эти отношения представлены в таблице ниже. Используя это отношение, он вычислил приближенное значение площади 3072-угольника и с его помощью получил более точную оценку числа π.

В качестве примера рассмотрим, как Лю Хуэй определил площадь 384-угольника на основе последнего значения площади, вычисленного им напрямую, — площади 192-угольника. Площадь 192-угольника равна 314,10318, избыток площади этого многоугольника по отношению к предыдущему равен 0,16816857. Далее Лю Хуэй вычислил разницу площадей 192-угольника и 384-угольника. Она составила 0,16816857·(1/4) = 0,042042144. Следовательно, площадь 384-угольника равна:

314,10318 + 0,16816857·0,25 = 314,14523.

Реальный избыток площади равен 0,042062752, площадь многоугольника равна 314,14526.

С помощью этого способа Лю Хуэй вычислил площадь 3072-угольника и получил приближенное значение π, равное 3927/1250 = 3,14159.

В 480 году этот метод был пересмотрен математиком и астрономом Цзу Чунчжи (429–500), жившим во времена династии Ци. Использовав многоугольник с 12288 = 3·212 сторонами, он определил, что π заключено между следующими значениями: 3,1415926 < π < 3,1415927. Он представил результат так:

π ~= 355/113. В течение 900 лет эта оценка оставалась наиболее точной.

Индийская и арабская математика. Позиционная система счисления

История науки гласит, что индийская математика возникла в VII веке, когда в этой стране в качестве всеобщего языка уже использовался санскрит. Индия не была изолированной от Европы: индийцы поддерживали тесные контакты с греками, позднее с римлянами. Не следует забывать, что граница империи Александра Македонского проходила по долине реки Инд.

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

Индийцы подробно изучили тригонометрию, особенно применительно к астрономическим расчетам и решениям неопределенных уравнений, а также алгебру и комбинаторику. По сути, понятие синуса и само слово «синус» впервые упоминаются в трактате по астрономии V века «Пайтамаха-сиддханта».

* * *

СИНУС

Как случилось, что для обозначения тригонометрической функции стало использоваться слово «синус»? Эта история берет начало в индийском трактате по астрономии под названием «Пайтамаха-сиддханта», в котором приводится таблица джайя-ардха — «измерение струн», использовавшаяся в астрономических расчетах. Этот термин вновь упоминается в труде «Ариабхатия» индийского математика Ариабхаты, который обозначал его как «джайя», или «джива». Арабы перевели это слово как «джиба», но так как в арабском отсутствуют отдельные буквы для обозначения гласных, то это слово записывалось как джб. При более позднем прочтении случайно или умышленно джб было прочитано как джаиб, что означало «грудь» или «пазуха», а переводчики на латынь использовали слово «синус», означавшее «пазуха», «складка на тоге», а также «залив». Этот термин используется не только в романских языках: даже английское слово sine имеет латинское происхождение.

* * *

Нет сомнений, что важнейшим вкладом индийских математиков в науку была созданная ими система счисления, которую мы называем арабской. В действительности арабы заимствовали ее у индийцев. Индийские цифры произошли от системы записи, которая использовалась во времена короля Ашоки (272–231 гг. до н. э.) для записи текстов на древнем языке пракрите. Тем не менее по пути на Запад индийские цифры неоднократно видоизменялись, поэтому современные цифры не похожи на придуманные индийцами. Современные цифры — одна из версий древних цифр на пракрите, которые попали в Северную Африку, претерпев некоторые изменения, и стали известны в Европе в Средние века.

Некоторые индийские цифры, описанные математиком Ариабхатой.

(Источник: Джордж Ифра, «Всеобщая история чисел».)

Позиционная система счисления также имеет индийское происхождение. Изначально индийцы записывали числа с помощью символов, обозначавших цифры от 1 до 9; десятки от 10 до 90 обозначались другими цифрами. Числа, кратные 100, 1000 и так далее обозначались символами, соответствовавшими единицам, рядом с которыми записывались символы, обозначавшие 100, 1000 и далее. Позднее эта система записи упростилась, и впервые в истории возникла позиционная система счисления, в которой использовались только символы, соответствующие цифрам от 0 до 9. Когда именно произошло это изменение, точно неизвестно, но большинство источников указывает в качестве наиболее вероятной даты 600 год. Так, в сирийском тексте 662 года уже используются индийские цифры.

Согласно одной из теорий, эта система счисления зародилась на границе с Китаем, так как в этом регионе применялся абак, и возникла необходимость в упрощенной записи расчетов, произведенных с помощью абака. Рождение позиционной системы счисления, возможно, связано с использованием точки для обозначения пустого разряда на абаке. Документальное подтверждение этому содержится в тексте VII века, найденном на северо-западе Индии в деревне Бакшали в 1881 году. Когда на смену этой точке пришел ноль, произошла революция. Ноль впервые упоминается вместе с остальными цифрами в 628 году, когда Брахмагупта в своей книге «Исправленный трактат Брахмы» определил его как результат вычитания числа из себя самого.

Как бы то ни было, в 870 году позиционная система счисления уже повсеместно применялась в Индии. Из Индии она попала в Багдад, откуда позднее распространилась по всем территориям, где прослеживалось влияние мусульманской культуры. В Китае позиционная система счисления с особыми символами стала использоваться начиная с эпохи династии Мин (1368–1644). В книгах по математике китайские символы были заменены арабскими цифрами лишь в начале XX века.

Древнейшая арабская книга, дошедшая до наших дней, где употребляются арабские цифры и позиционная система счисления, — это трактат «О началах индийской арифметики» Кушьяра ибн Лаббана. Эта работа выделяется не только тем, что в ней впервые использованы арабские цифры, но и оригинальностью содержания. В этой книге наряду с прочими цифрами употребляется ноль, называемый «сифр».

* * *

НОЛЬ И ЦИФРА

Слова «ноль» и «цифра» имеют очень похожее происхождение. Слово «цифра» происходит от арабского «сифр» — видоизмененного индийского «сунья». Исходное значение этого слова — «пустой». Фибоначчи в своей «Книге абака» (Liber Abaci), которая способствовала популяризации арабских цифр в Европе, упоминал слово zephyrum, которое на латыни и греческом означало «западный ветер», возможно, потому, что это слово было схоже с арабским «сафира», означавшее «быть пустым», которое, очевидно, было связано со словом «сифр» — «пустой».

КУШЬЯРИБН ЛАББАН

Персидский астроном и математик Кушьяр ибн Лаббан (971-1029) родился в Гиляне, к югу от Каспийского моря. Среди его трудов особое место занимает трактат «О началах индийской арифметики», однако он также был автором множества книг и собраний таблиц, которые передавались мусульманскими учеными из поколения в поколение. Он был учителем знаменитого математика ан-Насави. В своем трактате по арифметике он вводит арабские цифры и объясняет, как с их помощью выполняются основные действия: сложение, вычитание, деление на два, умножение, деление, вычисление квадратных и кубических корней.

* * *

До того времени многие арабские тексты представляли собой переводы с греческого, однако в X–XI веках эта тенденция радикально изменилась. На рубеже тысячелетий, когда жил Кушьяр ибн Лаббан, в мусульманском мире стали в изобилии появляться математические тексты, содержавшие новые важные результаты. По сути, именно мусульмане дополнили дробями позиционную систему счисления, которая до этого использовалась только для записи целых чисел.

Вычисление числа π в Индии

Индийцы также не устояли перед тайной числа π. Мадхава из Сангамаграма (1350–1425), основатель математической и астрономической школы в Керале, открыл, помимо прочего, разложение тригонометрических функций синуса и косинуса в бесконечный ряд и определил число π с помощью разложения в ряд для функции арктангенса.

Он выразил π следующим образом:

π/ 4 = 1–1/3 + 1/5 — 1/7 + … + (-1)n/(2n+1) + …

Кроме того, он дал оценку ошибке при вычислении числа π через n членов этого ряда. Эти расчеты требовали обширных знаний в области рядов. Позднее разложение арктангенса в ряд было повторно открыто Джеймсом Грегори и использовано Готфридом Лейбницем для вычисления π. По этой причине этот ряд известен как ряд Лейбница и ряд Грегори — Лейбница. Лишь сравнительно недавно он получил название ряд Мадхавы — Лейбница в честь истинного первооткрывателя.

Разложение арктангенса в ряд выглядит следующим образом:

arctgx = х — (х3)/3 + (х5)/5 — (х7)/7 + …

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

Глава 2 Средневековая Европа

В начале Средневековья образование в Европе держалось на трудах и авторитете поздних римских авторов, в частности Боэция. Образование в средневековых университетах следовало модели, введенной в V веке философом Марцианом Капеллой, автором трактата De Nuptiis Philologiae et Mercurio («О браке Филологии и Меркурия»), также известного как De septem disciplinis («О семи дисциплинах»), в котором он впервые разделил науки на тривиум и квадривиум.

Культурное наследие римлян ощущалось и в том, как производились вычисления, так как по-прежнему использовались римские цифры. Арабские цифры вводились медленно, этот процесс сопровождался горячими спорами и диспутами и длился в течение всего Средневековья. Тем не менее в Средние века также были совершены важные открытия, сыгравшие определяющую роль в развитии науки последующих эпох. Так, следует упомянуть логическую систему Раймунда Луллия, которая оказала большое влияние на работы Лейбница XVII века.

Боэций и ритмомахия

Ритмомахия — игра, напоминавшая шахматы, которая была широко известна в Средние века. Она была придумана в середине XI века в монастырях на юге Германии и достигла наивысшей популярности в XVI веке. Затем наступил период упадка, когда игра была полностью забыта. Ритмомахия была лишь игрой, однако она представляет особый интерес для исследователей, поскольку периоды роста ее популярности соответствуют этапам расцвета математики.

Основным математическим трудом Средневековья была «Арифметика» Боэция, носившая латинское название De Institutione Arithmeticae. Структура «Арифметики» очень отличалась от современных математических работ. В некотором роде ее можно считать возвратом к наследию Древней Греции. Боэций изложил в ней свои идеи об отношениях между числами, в особенности о пропорциях, а также определил множество понятий (в этом его работа схожа с «Началами» Евклида). Однако он не ввел понятия доказательств и предложений, известные еще в далекие времена Древней Греции. Ритмомахия стала своеобразным спасательным кругом: она использовалась для того, чтобы обучать студентов понятиям и отношениям из книг Боэция.

* * *

ТРИВИУМ И КВАДРИВИУМ

Понятие «тривиум» появилось в VIII–IX веках, после того как широкое распространение получил его «старший брат» квадривиум. Тривиум состоял из грамматики, логики и риторики и являлся введением в свободные искусства и квадривиум, который считался более сложным. Этот предрассудок отчасти сохранился до наших дней, так как словом «тривиальный» мы называем нечто простое и понятное.

Квадривиум состоял из арифметики, геометрии, астрономии и музыки, которые вкупе с тривиумом образовывали семь свободных искусств. В V–VI веках Боэций привел их в систему, однако само понятие свободных искусств упоминается уже в пифагорейских текстах.

Иллюстрация из книги «Сад наслаждений» Гэррады Ландсбергской, посвященная семи свободным искусствам. «Сад наслаждений» был написан в образовательных целях в конце XII века.

БОЭЦИЙ (480–524)

Аниций Манлий Торкват Северин Боэций был христианским философом из знатной семьи, к которой принадлежали несколько императоров. Наиболее известной его работой является De Consolatione Philosophiae («Утешение философией»»), написанная во время тюремного заключения. Боэций рассуждает о неравенстве в мире, следуя за Платоном. Он перевел множество греческих трудов на латынь, чтобы сделать греко-латинскую культуру доступной будущим поколениям. Крах западной Римской империи наступил за четыре года до его рождения, когда последний император Ромул Август был смещен Одоакром, предводителем германского племени.

Многие переводы Боэция были не дословными и содержали многочисленные комментарии. Так, De Institutione Arithmeticae Libri II, которая задумывалась как перевод «Введения в арифметику»» Никомаха Герасского, изобилует материалом, принадлежащим самому Боэцию. Переводы Боэция широко использовались в средневековой Европе.

Боэций в заключении. Миниатюра из «Утешения философией», издание XIV века.

* * *

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

В математике Боэция числа могут быть равными (aequalis) или неравными (inaequalis). Равенство нельзя разделить на категории, так как это понятие неделимо. Однако можно классифицировать различные виды неравенства. К первой категории (maioris) относились случаи, когда некое число было больше данного, ко второй (minoris) — случаи, когда некое число было меньше данного. Эти категории делились на пять подкатегорий в зависимости от типа отношения между числами. Первая категория содержала кратные (multiplex), сверхчастичные (superparticularis), сверхчастные (superpartiens), кратно-сверхчастные (multiplex superparticularis) и кратно-сверхчастичные (multiplex superpartiens) числа. Вторая категория делилась на подкратные (submultiplex), подсверхчастичные (subsuperparticularis), подсверхчастные (subsuperpartiens), подкратно-сверхчастные (submultiplex superparticularis) и подкратно-сверхчастичные (submultiplex superpartiens).

Как можно убедиться, игра, подобная ритмомахии, значительно помогала прояснить систему Боэция. Для этого позднеримского автора кратным числом было такое, в котором первое число укладывалось n раз. Таким образом, вводились двойные, тройные, четверные числа и так далее. Например, 8 — четверное число для 2.

Число называлось сверхчастичным, если содержало другое число и его часть. Например, 9 — сверхчастичное число для 6, так как 9 = 6 + (1/2)·6. Сверхчастное число содержит другое число и несколько его частей. Например, 9 — сверхчастное для 7, так как 9 = 7 + (2/7)·7. Кратно-сверхчастичные числа содержат другое число несколько раз и одну его часть, кратно-сверхчастные содержат другое число несколько раз и несколько его частей. Например, 15 — кратно-сверхчастичное для 6, так как оно равняется 6 + 6 + (1/2)·6, а 16 — кратно-сверхчастное для 7, так как равняется 7 + 7 + (2/7)·7.

Боэций в своей книге также определял три типа средних величин. Первая из них — среднее арифметическое, определяемое как m = (а + Ь)/2. Его основное свойство заключается в том, что интервалы между ним и данными числами одинаковы. Вторая — среднее геометрическое, определяемое как m = √(а·b). Его основное свойство заключается в том, что а относится к m точно так же, как m относится к Ь. Иными словами, а/m = m/b. Третья средняя величина — среднее гармоническое: m = 1/((1/а + 1/Ь)/2), или, что аналогично, m = 2аЬ/(а + Ь).

Как ритмомахия помогала разобраться в этом нагромождении отношений между числами? Очевидно, путем их использования в увлекательной игре. Игра велась на доске шириной 8 и длиной 16 клеток (длина доски могла отличаться). Каждому игроку выдавались 24 фишки с числами, которые были кратными, сверхчастными и сверхчастичными для данных чисел. Игроки использовали математические операции, чтобы снимать с доски фишки противника. Например, если фишка с номером 4 располагалась в 9 клетках от фишки с номером 36, то фишка с номером 36 оказывалась взятой (так как 36 = 4·9). Если фишки с номерами 4 и 8 располагались по бокам от фишки с номером 12, последняя оказывалась взятой (так как 12 = 4 + 8).

Кроме того, в условиях окончания игры фигурировали три средние величины, введенные Боэцием. Например, если одному из игроков удавалось расположить подряд фишки с номерами 2, 4, 6, при этом между ними располагалась фишка противника, это означало конец партии. Почему? Потому что 4 — среднее арифметическое 2 и 6.

* * *

СРЕДНИЕ ВЕЛИЧИНЫ В АРИФМЕТИКЕ БОЭЦИЯ

«Древним было хорошо известно, что существуют три средние величины: арифметическая, геометрическая и гармоническая. Они же рассматривались в науке Пифагора, Платона и Аристотеля.

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

Поскольку здесь всегда рассматриваются равные пропорции… например 1, 2, 4, 8, 16, 32, 64, или тройная пропорция 1, 3, 9, 27, 81, равно как можно установить четверное, пятерное или любое другое отношение. <…> Среди других средних гармоническая не строится ни с помощью разностей, ни с помощью равных пропорций. Вместо этого средняя гармоническая есть та, в которой составляется наибольшее с наименьшим (частное) и сравнивается (или приравнивается) разность наибольшего со средним и разница среднего с наименьшим. Например, 4, 5, 6 или 2, 3, 6. 6 превосходит 4 на свою третью часть (то есть на 2), 4 превосходит 3 на свою четвертую часть (на 1), 6 превосходит 3 на свою половину (на 3), 3 превосходит 2 на свою третью часть (на единицу)».

* * *

Гравюра 1554 года, на которой изображена доска для ритмомахии.

* * *

ОБНОВЛЕННЫЕ ОПРЕДЕЛЕНИЯ БОЭЦИЯ

Определения, данные Боэцием среднему арифметическому, среднему геометрическому и среднему гармоническому, можно выразить в современной нотации. Рассмотрим три величины: а, b и с. Предположим, что а — наибольшая величина, b — средняя, с — меньшая, то есть выполняется неравенство а > b > с. Можно предположить, что b — среднее арифметическое, среднее геометрическое или среднее гармоническое двух других величин. Среднее арифметическое обладает следующим свойством: разность между соседними членами неизменна, то есть а — Ь = Ь — с. Это выполняется в случае, когда Ь = (а + с)/2, что нетрудно вывести из предыдущего равенства.

Среднее геометрическое обладает следующим свойством: соотношение соседних членов неизменно, то есть а/b = Ь/с. Это равенство подразумевает, что ас = bb, следовательно, b = √(а·с).

Среднее гармоническое, согласно Боэцию, обладает следующим свойством: соотношение между наибольшей и наименьшей величиной равно соотношению разности большей и средней величины и разности средней и меньшей величины. На языке математики это определение выглядит так: а/с = (а — b)/(b — с). Из этого равенства можно получить следующее равенство: а(Ь — с) = с(а — Ь), откуда следует ab — ас = са — сЬ, или, что аналогично, ab + сЬ = 2ас. Выразим b из последнего равенства и получим b = 2ас/(а + с). Эта формула позволяет получить среднее гармоническое а и с, хотя чаще используется следующее выражение: b = 2/(1/а +1/с). Это выражение можно получить из предыдущего делением числителя и знаменателя на ас.

* * *

Раймунд Луллий

В своем труде Ars Magna et Ultima («Великое искусство») Раймунд Луллий представил свою логическую систему доказательства истинности. Целью ее создания было объективно доказать мусульманам превосходство христианской религии. Иными словами, он создал логику для доказательства своих рассуждений. Одним из его открытий являются так называемые круги: на этих кругах были записаны понятия, при вращении кругов образовывались различные комбинации, то есть высказывания, которые Луллий считал истинными.

Пример круга из «Великого искусства» Раймунда Луллия.

Новизна логики Луллия состояла в ее направленности на изучение свойств понятий. Следовательно, ее можно считать синтетической логикой, в то время как в ту эпоху доминировала аналитическая логика. Эта новая точка зрения заинтересовала таких мыслителей, как Джордано Бруно (1548–1600) и Готфрид Вильгельм Лейбниц (1646–1716), которые позднее использовали философские идеи Луллия. Лейбниц применил их в своем выдающемся трактате «Рассуждения о комбинаторном искусстве», опубликованном в 1666 году. По сути, логика Луллия сохранилась до наших дней, так как именно на ней основаны логические системы, лежащие в основе многочисленных современных вычислительных машин.

Миниатюра из книги «Великое искусство» Раймунда Луллия.

* * *

АНАЛИТИЧЕСКАЯ И СИНТЕТИЧЕСКАЯ ЛОГИКА

Философ Иммануил Кант (1724–1804) объяснил различие между синтетической и аналитической логикой в своей книге «Критика чистого разума». Его суть в том, что в аналитической логике предикат входит в содержание субъекта, а в синтетической логике не входит. Например, высказывание «у каждого треугольника три стороны» является аналитическим, поскольку наличие трех сторон является неотъемлемым свойством треугольника, заключенном в самом его определении. В противном случае высказывание является синтетическим. Например, таким высказыванием будет «некоторые преподаватели ставят много неудовлетворительных оценок на экзаменах».

В 1951 году американский философ Уиллард Ван Орман Куайн (1908–2000), учитель Ноама Хомского, взял на себя смелость заново поднять вопрос о различии между аналитической и синтетической логикой.

* * *

Раймунд Луллий был автором и других понятий, лежащих в основе современной науки. Он также разработал систему проведения выборов, которая изначально предназначалась для распределения церковных должностей. Эта система была впервые описана в романе «Бланкерна» на примере выборов настоятельницы монастыря, а затем изложена в более формальном виде в книгах Ars Electionis и Artifitium Electionis Personarum. Его идеи оказали огромное влияние на философа и богослова Николая Кузанского (1401–1464), который считается основателем немецкой философии. По сути, системы, предложенные Луллием и Николаем Кузанским, стали основой современных избирательных систем: система Луллия удовлетворяет критериям системы Кондорсе, созданной в 1785 году, а на системе Кузанского строится правило Борда, впервые изложенное в 1770 году. Цель всех этих систем голосования — определить кандидата, которому отдает предпочтение группа людей, зная предпочтения отдельных избирателей.

Появление арабских цифр

Система счисления, которую мы используем сегодня, попала в Европу из Индии через северную Африку усилиями мусульман. Это объясняет, почему эти цифры называются арабскими. Эту систему счисления определил и развил персидский мудрец Мухаммед ибн Муса аль-Хорезми.

Герберт Орильякский, который был избран папой римским под именем Сильвестра II, сыграл в этом процессе решающую роль, так как именно он способствовал повторному распространению абака в Европе и использованию арабских цифр. Абак Герберта Орильякского был обновленным вариантом римского абака. В нем использовались девять символов для обозначения цифр, нулю соответствовал пустой столбец. В Европе он стал использоваться повсеместно в XI веке, однако абак с арабскими цифрами не заменил абак с римскими цифрами: он рассматривался как средство для вычислений, а римские цифры считались единственно возможной формой записи результатов.

Вне всяких сомнений, решающую роль в распространении арабских цифр сыграл Мухаммед ибн Муса аль-Хорезми. Его основной труд — «Ал-китаб ал мухтасар фи хисаб ал-джабр ва-л-му кабала» («Книга о восполнении и противопоставлении»). Этот труд предшествовал трактату «О началах индийской арифметики» Кушьяра ибн Лаббана, и его важность намного выше. К сожалению, не сохранилось ни одного арабского издания книги ибн Лаббана, которая известна нам лишь благодаря более поздним переводам на латынь, выполненным в XII и XIII веке. О важности труда аль-Хорезми можно судить уже по его названию: от слов «ал-джабр» произошло слово «алгебра», от имени автора — понятие «алгоритм».

Помимо трактата по алгебре он также создал труд по арифметике под названием «Китаб аль-джама валь-тафрик» («Книга об индийской арифметике»), в котором подробно описал индийскую позиционную систему счисления по основанию 10 и методы выполнения основных арифметических операций. По одной из версий, аль-Хорезми первым использовал ноль для обозначения пустого разряда. Переводы его труда на латынь распространились по всей Европе и на протяжении нескольких веков широко использовались в университетах под названием Algoritmi de Numero Indorum.

* * *

ГЕРБЕРТ ОРИЛЬЯКСКИЙ (946-1003)

Будущий папа римский Сильвестр II оставил монастырь Святого Герольда в Орильяке и последовал за графом Барселоны Боррелем II в монастырь Святой Марии в Риполь, где три года изучал математику. Он также совершил путешествия в Кордобу и Севилью, где обучался математике и астрономии у арабов, и убедился в превосходстве применяемой ими системы счисления.

Герберт Орильякский был автором множества трудов по математике и астрономии, посвященных прежде всего квадривиуму, то есть предназначенных для студентов, а не ученых мужей. Его работы включены в том 139 «Латинской патрологии» (Patrologia Latina) — собрания сочинений латиноязычных христианских авторов от Тертуллиана (160–220) до Иннокентия III (1160–1216). Помимо введения абака Герберт Орильякский также воссоздал армиллярную сферу, чтобы помочь изучающим астрономию.

Статуя папы Сильвестра II во французской префектуре Орильяк.

МУХАММЕД ИБН МУСА АЛЬ-ХОРЕЗМИ (ОК. 783 — ОК. 850)

О жизни Мухаммеда ибн Мусы аль-Хорезми достоверно известно немногое, ведутся споры даже о точном месте его рождения. Математик, астроном и географ аль-Хорезми считается создателем алгебры и современной системы счисления. Он учился, а затем работал в Доме мудрости в Багдаде — научном учреждении, по масштабу сопоставимом с Александрийской библиотекой. В Доме мудрости составлялись и переводились на арабский язык важнейшие научные и философские труды греков и индийцев. Там же располагалась современная обсерватория. Аль-Хорезми был автором множества трудов, многие из которых сыграли фундаментальную роль в развитии науки, а также написал трактат по политической истории. Благодаря широте своих знаний он считается одним из величайших мудрецов древности.

Марка СССР, посвященная Мухаммеду ибн Мусе аль-Хорезми, выпущенная в 1983 году.

* * *

Распространение арабских цифр

Введение арабских цифр в Европе было медленным и непростым и, разумеется, сопровождалось полемикой. Во Флоренции их использование было запрещено, так как арабские цифры якобы позволяли легко фальсифицировать бухгалтерский баланс. В течение нескольких веков не утихали споры между «абацистами» и «алгоритмистами». В итоге последние одержали победу, но это произошло лишь в середине XVI века.

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

В итоге как всегда всё решили деньги. В Италии чаша весов стала склоняться в сторону алгоритмистов, и мало-помалу становилось понятно, что арабские цифры намного удобнее для торговли, так как они значительно упрощали расчеты на бумаге.

Энтузиазм итальянцев по отношению к арабским цифрам постепенно охватил остальные страны Европы: новые методы вычислений в 1200 году были введены в Германии, примерно в 1275 году — во Франции, а в 1300 году достигли берегов Англии. Человеком, который способствовал распространению арабских цифр и произвел революцию в математике, был Леонардо Пизанский, намного более известный как Фибоначчи. В «Книге абака» Фибоначчи продемонстрировал возможности применения арифметики в торговле и представил арабские цифры, а также алгоритмы вычислений с ними. В предисловии прямо говорилось, что целью автора было показать полезность арабских цифр и способствовать их всеобщему применению в Италии.

«Книга абака» была первой написанной в Европе книгой, где использовались арабские цифры. «Книга абака» стала первым среди математических трудов, которые приобрели особую популярность в период с XIV до середины XVI века. В них шла речь об использовании арифметики в торговле и о решении соответствующих задач. Популярность этой арифметики связывают с распространением школ абака, особенно в Италии. В 1340 году во Флоренции насчитывалось шесть школ абака, в которых обучалось 1200 учеников (весьма значительное количество, если учесть, что все население города в то время составляло 100 000 человек). В этих школах, в частности в школе Галигаи во Флоренции, о которой упоминается во множестве документов, дети 10–11 лет обучались основам арифметики в течение двух-трех лет. Как правило, ученики поступали в школы абака, окончив грамматические школы, где их обучали чтению и письму, начиная с пяти-семи лет. Выпускники школ абака в возрасте 13–14 лет становились подмастерьями в мастерских, банках и так далее. Лишь немногие не спешили начинать работать и занимались изучением классических трудов.

* * *

ЛЕОНАРДО ПИЗАНСКИЙ (1170–1250)

Леонардо Пизанский, Фибоначчи, был сыном Гильермо Боначчи — итальянского торговца из алжирского города Беджая. Его имя, по одной из версий, означало figlio di Bonacci — «сын Боначчи». Леонардо вместе с отцом обучился арабской системе счисления и арифметическим действиям. Позднее, желая расширить знания, он совершил путешествие в Египет, Сирию и Византию, где подробно изучил арабскую математику. В своих трудах он излагает все, что узнал в этих путешествиях. Помимо важной «Книги абака» он также написал «Книгу квадратов» (Liber Quadratorum, 1225), посвященную алгебре, «Практику геометрии» (Practice Geometriae, 1223) и многие другие.

* * *

Школы абака и использование арифметики в торговле оказали заметное влияние на развитие математики той эпохи. К авторам книг и преподавателям школ часто обращались для решения практических задач. Так, Джованни ди Бартоло, преподаватель академии абака во Флоренции, помог выполнить расчеты для постройки купола собора в 1420 году. Тем не менее практическая математика развивалась независимо от теоретической, которую изучали в университетах. Преподаватели школ абака и университетские преподаватели практически не пересекались.

Большинство университетов следовало классическим традициям: в них изучали арифметику Боэция и римские цифры.

Страница из «Книги абака» Фибоначчи.

Распространение арабских цифр также было связано с деятельностью других учреждений, имевших отношение к торговле. Стали появляться учебники по средневековой торговле, в которых излагались правила арифметики, как в итальянском трактате Pratice della mercatura. Наиболее известными из них были Libro di divisamenti di apesi e di misure di mercantie Франческо Бальдуччи Пеголотти, опубликованный в первой половине XIV века, а также труды Антонио да Уццано (1442) и Джорджио Чиарини (1438).

Книги по арифметике торговли были очень популярны, но стоили дорого и были недоступны студентам. В школах абака обычно имелось несколько экземпляров подобных книг. Считается, что они использовались в качестве справочников в торговых домах и служили в некотором роде сводами законов и правил торговли. Первой в истории печатной книгой по математике был учебник по арифметике в торговле, изданный в итальянском городе Тревизо в 1478 году. Второе место в этом списке занимает Summa de Tart d’aritmetica Франсеска Сен-Клемана, опубликованная в Барселоне на каталанском языке в 1482 году. Эта книга была первым учебником по математике, отпечатанным на Пиренейском полуострове. Rechenbuch Ульриха Вагнера, опубликованный в Бамберге (Бавария) в 1483 году, занимает третье место.

* * *

МАТЕМАТИКА ПЕРЕХОДНОГО ПЕРИОДА

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

• Теоретические трактаты, авторы которых следовали по пути Боэция.

• Учебники по арифметике, где описывались приемы вычислений с помощью абака.

• Книги, где описывались алгоритмы действий с арабскими цифрами и способы вычислений на бумаге. Основывались на работах аль-Хорезми.

• Работы, в которых описывались системы счисления для составления церковных календарей.

КНИГОПЕЧАТАНИЕ

Изобретателем книгопечатания подвижными литерами считается Иоганн Гутенберг (1398–1468), который примерно в 1450 году в немецком городе Майнц создал машину для книгопечатания.

Первые книги были напечатаны в 1449–1450 годах, а в 1454–1455 годах он завершил печать знаменитой 42-строчной Библии (имеется в виду число строк на странице). Общее число страниц составляло 1282, книга делилась на несколько томов (как правило, на два). До настоящего времени сохранились 48 копий Библии Гутенберга. Их стоимость на момент печати равнялась зарплате среднего служащего за три года. Хотя книгопечатание подвижными литерами имело огромное значение (благодаря ему стало возможным издание книг в больших объемах, что привело к одной из величайших культурных революций в истории человечества), Иоганн Гутенберг умер в полной нищете.

Страница Библии Гутенберга.

* * *

Гравюра из «Жемчужины философии» (1508) Грегора Рейша, на которой изображены Боэций и Пифагор, состязающиеся в вычислениях. За ними сверху наблюдает Арифметика. Обратите внимание: Боэций (слева) использует арабские цифры, Пифагор производит расчеты с помощью абака.

Доказательством важности математических текстов по арифметике в торговле служит тот факт, что важнейший труд Евклида «Начала» был отпечатан лишь в 1482 году на латинском языке под названием Elementa Geometriae. «Арифметика» Боэция была отпечатана в 1488 году. Первой печатной книгой по алгебре стала «Сумма арифметики, геометрии, дробей, пропорций и пропорциональности» (La primera algebra impresa fue la Summa de Arithmetica, Geometrica, Geometria, Proportion! et Proportionalita) Луки Пачоли, опубликованная в Венеции в 1494 году.

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

Портрет математика Луки Пачоли кисти Якопо де Варбари, выполненный около 1496 года.

* * *

ЗАДАЧА ПО АРИФМЕТИКЕ В ТОРГОВЛЕ

Манускрипт под номером 102 (A. III 27), хранящийся в муниципальной библиотеке итальянского города Сиены, — один из четырех манускриптов, посвященных арифметике, опубликованных до 1500 года, которые сохранились до наших дней. В нем упоминается следующая задача: «Если хочешь знать о человеке, сколько денег в его кармане, поступай так: предположи, что у него 4, скажи ему удвоить их число, и получишь 8, затем добавить 5 и получишь 13, затем умножить всё на 5 и получишь 65, добавить 10 и получишь 75, затем умножить на 10 и получишь 750. Теперь вычти 350 и получишь 400, что соответствует 4, и каждая сотня соответствует числу, посему 400 будет 4».

* * *

Простые и десятичные дроби

Когда арабские цифры попали на Запад, изначально с их помощью записывались только целые числа. Дробные числа по-прежнему записывались в шестидесятеричной системе счисления, как в древней Вавилонии. Кушьяр ибн Лаббан в своей книге «О началах индийской арифметики» обозначает дробные числа как градусы: 1/60 он называет минутой (daqa’iq), 1/(602) — секундой (thawani), 1/(603) — терцией (thawalith), 1/(604) — квартой (rawabf) и так далее. Уже тогда они обозначались теми же символами, которые используются и сейчас: градусы обозначались знаком °, минуты — ', секунды — ", терции — "' так далее.

Лишь в XVI веке Симон Стевин написал трактат, в котором подчеркивалась важность десятичной нотации, в том числе для записи дробей. Он обратился к властям и начал кампанию по распространению этой системы. До Стевина десятичная нотация уже применялась для записи дробей, однако использовалась не повсеместно. Персидский математик и астроном Гияс ад-Дин ал-Каши (1380–1429), один из руководителей Самаркандской обсерватории, использовал эту нотацию за 100 лет до Стевина в своих трудах по тригонометрии и при вычислении числа 71. Ал-Каши также был известен так называемый треугольник Паскаля (таблица Тартальи).

* * *

СИМОН СТЕВИН

Фламандский математик, инженер, физик и семиолог Симон Стевин (1548–1620) в 1585 году опубликовал книгу DeThiende («Десятая»). В этой книге объяснялась десятичная нотация и способы вычисления расчетов в этой нотации. Стевин первым признал существование отрицательных чисел, полученных им при решении задач. Он также создал алгоритм нахождения наибольшего общего делителя двух многочленов. Он писал все труды на голландском языке, чтобы их могли понять ремесленники. Его книги были написаны очень просто и пользовались большой популярностью, что способствовало распространению десятичной системы счисления.

* * *

Число π

Как мы уже упоминали, персидский математик ал-Каши занимался вычислением числа π. В то время как Цзу Чунчжи вычислил значение π, использовав правильный многоугольник с 12288 = 3·212 сторонами, ал-Каши использовал многоугольник с числом сторон, равным 805306368 = 3·228, и верно вычислил 14 знаков π. Это произошло в 1430 году.

Математики ал-Каши и Людольф ван Цейлен вычислили новые, ранее неизвестные знаки числа π.

Профессор Лейденского университета Людольф ван Цейлен последовал путем ал-Каши и в 1596 году вычислил 20 верных знаков Я, использовав многоугольник с 515396075520 = 60·233 сторонами. Позднее, в 1615 году, он вычислил 35 верных знаков, использовав многоугольник с числом сторон, равным 4611686018427387904 = 262.

Метод вычисления числа Я с помощью многоугольников позволял получить точные результаты, однако многие математики считали, что существуют более эффективные алгоритмы. Они рассматривали возможность вычисления π как суммы или произведения бесконечного числа членов. Первым европейским математиком, который нашел подобное выражение, был Франсуа Виет, один из создателей современной алгебры. Тем не менее ему был неизвестен ряд, полученный Мадхавой из Сангамаграма, о котором мы упоминали в предыдущей главе. Выражение, полученное Виетом, представляло собой произведение бесконечного числа членов, в котором использовался квадратный корень из 2. Это выражение было не слишком удобно, однако оно открыло новый путь к вычислению множества знаков π.

Впервые в истории математики число π было выражено в виде произведения бесконечного числа членов. Это произведение выглядело следующим образом:

* * *

ФРАНСУА ВИЕТ (1540–1603)

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

Глава 3 Первые механические вычислительные машины

Появление арабских цифр ознаменовало прогресс в вычислениях и новый виток эволюции науки. В XVII веке в ходе длительного процесса значительно изменились представления о Вселенной, а также метод и сама концепция западной науки. Этот период, который часто именуется революцией в науке, открыл путь к эпохе Просвещения, начавшейся в XVIII веке. Развитие человеческой мысли происходило очень быстрыми темпами. Появлялись новые методы исчисления, которые требовали новых, более мощных, сложных и точных инструментов. Расчеты, выполняемые вручную, неизбежно становятся источником ошибок. Чтобы избежать этого, ученые стремились свести к минимуму участие человека в расчетах, что стимулировало создание механических вычислительных машин. В период, охватывающий XVII, XVIII и XIX века, были сконструированы первые механические вычислительные машины.

XVII век

В 1617 году шотландский математик Джон Непер создал одну из первых вычислительных машин — абак, известный под названием «палочки Непера». Эта машина была столь эффективной, что в некоторых регионах она использовалась вплоть до начала XX века.

* * *

ДЖОН НЕПЕР (1550–1617)

Математик Джон Непер создал теорию логарифмов, которые он называл искусственными числами. В его честь были названы неперовы (натуральные) логарифмы. Он очень интересовался богословием: применив математические методы для толкования «Откровений» святого Иоанна Богослова, он вычислил, что конец света наступит в период с 1688 по 1700 год.

* * *

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

Современная реконструкция палочек Непера.

Чтобы продемонстрировать пример использования этого устройства, рассмотрим умножение числа 35672. Мы выбрали это число, чтобы показать применение всех строк таблицы. Нужно последовательно расположить палочки, соответствующие пяти цифрам этого числа, то есть сначала — палочку под номером 3, затем под номером 5, далее — 6, 7 и 2. Простое наблюдение за положением палочек позволяет увидеть, что в каждом ряду будут записаны результаты умножения 35 672 на все числа от 1 до 9.

Следовательно, чтобы умножить 35 672 на 4, нужно взять числа из четвертого ряда:

1/2 2/0 2/4 2/8 0/8.

Далее нужно сложить соседние числа пар, разделенные наклонной чертой:

1/2 + 2/0 + 2/4 + 2/8 + 0/8.

Получим:

1/4/2/6/8/8.

Таким образом, результат умножения 35672 на 4 равен 142688. Вы можете проверить его правильность вручную или на калькуляторе.

35 672·4 = 142 688.

Умножение 35 672 на 4 с помощью палочек Непера.

Умножение многозначных чисел выполняется аналогично современному способу: каждая цифра второго числа последовательно умножается на первое число, после чего полученные результаты складываются. Промежуточные результаты умножения получаются по уже описанной нами схеме. Следует отметить, что все необходимые промежуточные результаты находятся в одной и той же таблице. Например, чтобы умножить 35 672 на 436, нужно выполнить расчеты по описанной нами схеме в рядах 4, 3 и 6. Мы получим несколько чисел, которые нужно записать друг под другом так, чтобы диагональные линии оказались расположены в ряд.

При таком расположении чисел умножение 35 672 на 436 сводится к сложению промежуточных результатов, как показано ниже. Сначала записаны промежуточные результаты умножения, затем суммы пар чисел, разделенных диагональными чертами и, наконец, результат, полученный переносом значений в старший разряд там, где это необходимо.

Выполните эти действия на калькуляторе и убедитесь, что результат абсолютно верен:

35 672·436 = 15 552 992.

Заметьте, что числа в строках соответствуют промежуточным результатам, получаемым при известном нам способе умножения столбиком. Эти промежуточные результаты равны:

Однако палочки Непера использовались не только для умножения. Для деления одного большого числа на другое достаточно расположить палочки на столбцах, соответствующих цифрам делителя. В строках таблицы будут записаны числа, кратные делителю, которые помогут быстрее получить результат деления.

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

log(a·b) = log (а) + log(b)

log(a/b) = log(a) — log(b)

log(ab) = b·log(a).

Следовательно, для вычисления произведения а·Ь достаточно вычислить e log(a) + log(b)

На основе логарифмов была создана логарифмическая линейка — еще одно важнейшее вычислительное устройство. Ее автором был британский математик Уильям Отред (1574–1660), который впервые стал обозначать умножение знаком X, функции синуса и косинуса — sin и cos соответственно. Этот математик использовал устройство, разработанное Эдмундом Гантером, в котором применялась одна логарифмическая шкала (в логарифмической линейке используются две шкалы). Позднее, в 1859 году, француз Амадей Манхейм представил ряд улучшений, и логарифмическая линейка обрела современный вид.

Портрет Уильяма Отреда, который считается изобретателем логарифмической линейки.

Логарифмические линейки не использовались для сложения и вычитания. Они были более удобны для умножения и деления и применялись преимущественно для выполнения именно этих операций. Более поздние версии позволяли вычислять значения корней, тригонометрических функций, степеней и логарифмов. Однако следует заметить, что точность логарифмической линейки была ограниченной: как правило, использовались три значащие цифры. Однако с помощью более точных линеек, имевших больший размер, достигалась более высокая точность. Требовалось обращать внимание на порядки величин, так как при использовании логарифмической линейки они не учитывались. Логарифмические линейки применялись в качестве средства научных расчетов до 1970-х годов, пока их не вытеснили карманные электронные калькуляторы.

Модель логарифмической линейки 1960-х годов. Этим вычислительным устройствам вскоре пришли на смену калькуляторы.

Первые калькуляторы

Первый электронный карманный калькулятор появился в 1972 году. Это была знаменитая модель Hewlett-Packard НР-35. Пока что мы рассказывали об эволюции исчисления и средствах его автоматизации, то есть о развитии теоретической базы, на основе которой в итоге был создан карманный калькулятор и впоследствии множество других устройств, без которых мы не можем сегодня представить нашу жизнь.

Однако эта теория принесла первые плоды не в XX веке, а намного раньше. Первый калькулятор в истории был создан еще в XVII веке. Его изобретение стало логичным продолжением развития механических вычислительных устройств, о которых мы только что рассказали. Это устройство, получившее название «часы для счета», создал Вильгельм Шиккард (1592–1635) в Тюбингене в 1623 году.

Немецкая марка с изображением «часов для счета» Вильгельма Шиккарда.

С помощью первого в мире калькулятора можно было выполнять четыре основных арифметических действия. Сложение и вычитание выполнялись полностью механически, в отличие от умножения и деления: в этом случае оператору приходилось выполнять промежуточные действия самому. Детали машины напоминали палочки Непера, перенос значений в старший разряд осуществлялся механически при помощи зубчатых колес: когда колесо, соответствовавшее единицам, совершало полный оборот, колесо, обозначавшее десятки, сдвигалось на одно деление. Подобные механизмы использовались в Европе как минимум с XVI века при создании шагомеров, служивших для измерения пройденного пути. Древнейший из известных нам шагомеров был создан французом Жаном Фернелем в 1525 году.

Калькулятор Шиккарда не оказал большого влияния на вычисления: его изобретатель стал жертвой одной из эпидемий, бушевавших в Европе в те годы. Изобретение затерялось и было вновь найдено лишь в XX веке. О нем стало известно из переписки Шиккарда с Иоганном Кеплером, с которым тот сотрудничал. В своих письмах он приводит многочисленные эскизы своего изобретения. Благодаря им стало возможным воссоздать машину и убедиться, что она действительно работала. В одном из писем Кеплер подтверждает, что попросил экземпляр калькулятора у своего друга и коллеги Шиккарда.

«Паскалина», калькулятор, изобретенный Блезом Паскалем, стал первой широко известной вычислительной машиной. Этот гениальный философ и математик представил свое изобретение публике в 1642 году, когда ему было всего 19 лет. Созданная Паскалем машина была схожа с изобретением Вильгельма Шиккарда: когда колесо, соответствовавшее меньшему разряду, совершало полный оборот, колесо, соответствовавшее следующему разряду, поворачивалось на одно деление. К сожалению, подобное устройство было источником различных проблем, поскольку зубчатые колеса не всегда сцеплялись правильно.

«Паскалина», изобретенная Блезом Паскалем.

Было доказано, что Паскаль создал свою машину независимо от Вильгельма Шиккарда. «Паскалина» была проще, и с ее помощью можно было выполнять только сложение и вычитание. Первая версия работала с пятизначными числами (машина Шиккарда с шестизначными), в последующих версиях число разрядов было увеличено. Некоторые калькуляторы поступили в продажу, но их высокая цена отпугнула покупателей и не принесла семье Паскаля существенной прибыли. «Паскалина» стала всего лишь игрушкой, символом статуса для зажиточных людей Франции и других стран Европы. Паскаль в течение 10 лет улучшал свое изобретение и создал 50 различных версий.

Несмотря на ограничения и сбои в работе, эти машины имели огромное значение. С их появлением всю Европу охватила жажда изобретательства, математики и инженеры один за другим принялись создавать новые и новые механические калькуляторы. Некоторые из них были более совершенными, чем «Паскалина», другие были еще проще. Англичанин Сэмюэль Морленд (1625–1695), например, создал вычислительную машину, адаптированную к британской денежной системе с пенни, шиллингами и фунтами, которая отличалась от десятичной. В отличие от «Паскалины», его калькулятор не мог переносить значения в старший разряд автоматически. В нем присутствовали отдельные колеса для значении, перенесенных в каждый разряд, которые требовалось учитывать вручную. Машина Морленда была примечательна своими размерами: она свободно помещалась в карман.

* * *

БЛЕЗ ПАСКАЛЬ (1623–1662)

Французский математик, физик, философ и богослов Блез Паскаль вместе с Чарльзом Бэббиджем считается отцом современных компьютеров. Паскаль был вундеркиндом: уже в И лет он написал небольшой трактат о звуках вибрирующих тел и самостоятельно доказал, что сумма углов треугольника равна сумме двух прямых углов. В 12 лет он изучил труды Евклида и начал посещать собрания, на которых присутствовали лучшие математики и другие ученые Европы: Роберваль, Дезарг, сам Декарт. Паскаль создал свои фундаментальные труды по проективной геометрии, когда ему было всего 16 лет. Прочитав рукопись, Декарт не мог поверить, что ее автор — подросток. Паскаль был математиком и физиком первой величины, а его открытия ярко сияют на звездном небе современной науки.

* * *

В книге The Description and Use of two Arithmetick Instruments, изданной в Лондоне в 1673 году, описывается вычислительная машина, изобретенная Сэмюэлем Морлендом.

Калькулятор, созданный Готфридом Лейбницем, был намного более совершенным по сравнению с машиной Паскаля, так как с его помощью можно было автоматически выполнять умножение. До этого умножение с помощью калькуляторов было трудоемким и требовало выполнения промежуточных вычислений вручную. Однако вновь возникала извечная проблема: машины становились все сложнее и сложнее и в итоге переставали работать вовсе. Точность деталей была недостаточной, чтобы обеспечить требуемую надежность. Но несмотря на это, усовершенствования, представленные Лейбницем, оказали большое влияние на последующие изобретения. Среди них выделяются два нововведения: зубчатый механизм Лейбница (цилиндр, удерживавший зубчатые колеса на определенных расстояниях друг от друга) и передвижная каретка. Улучшения, необходимые для того, чтобы эти изобретения стали по-настоящему надежными, внес француз Шарль Ксавье Тома де Кольмар в 1822 году, когда изобрел и начал серийный выпуск арифмометра.

Однако вклад Лейбница не ограничивался одним лишь созданием неточного вычислительного калькулятора. Намного более важным был его труд о двоичной системе счисления, лежащей в основе современной информатики. Эту систему счисления до него изучал англичанин Томас Хэрриот (1560–1621), однако результаты его работы не были опубликованы. В следующей таблице приведена запись чисел от 0 до 15 в двоичной системе.

Устройство арифмометра Шарля Ксавье Тома де Кольмара (вверху) и калькулятора, изобретенного Гэтфридом Лейбницем.

Лейбниц внес важный вклад не только в развитие систем счисления. Этот немецкий философ также является автором значимых трудов по логике. Его работы в этой области были опубликованы посмертно, так как, по всей видимости, Лейбниц был не вполне доволен ими. Заглавие одной из его работ, Post tot logicas nondum Logica qualem desidero scripta est, можно перевести как «После стольких логик та логика, что я сочинил, еще не была написана». Он работал над созданием логического исчисления, которое можно было бы применять к любым научным высказываниям.

В одной из своих работ Лейбниц писал:

«Если нам это удастся, то, когда возникнет противоречие, необходимости в споре между двумя философами будет не более чем между двумя математиками. Будет достаточно взять перья и абак и сказать друг другу: произведем вычисления».

* * *

ГОТФРИД ВИЛЬГЕЛЬМ ЛЕЙБНИЦ (1646–1716)

Немецкий мыслитель Готфрид Вильгельм Лейбниц вместе с Декартом и Спинозой входит в тройку великих рационалистов XVII века. Он был математиком, логиком, философом, геологом, историком и экспертом в юриспруденции. Он также внес огромный вклад в технологию и предвосхитил появление многих понятий в биологии, медицине, психологии и даже информатике. Независимо от Ньютона он создал анализ бесконечно малых. Введенные им обозначения используются и сейчас.

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

* * *

В этой работе прослеживается влияние Раймунда Луллия: при написании «Рассуждения о комбинаторном искусстве» (Dissertatio de Arte Combinatoria) Лейбниц вдохновлялся его «Великим искусством». Для Лейбница даже приближение к божественному знанию должно было достигаться исключительно путем комбинирования основных понятий. Эти основные понятия, которым невозможно дать определение, должны были выражаться на языке математики. На их основе с помощью четких дедуктивных правил должны были выводиться различные истинные высказывания.

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

Новые выражения для вычисления числа π

В течение XVII века различные исследователи предпринимали попытки вычислить значение π с помощью бесконечных рядов, следуя путем, который наметил Франсуа Виет. Одним из них был англичанин Джон Валлис (1616–1703) из Оксфордского университета. В своей книге «Арифметика бесконечного», опубликованной в 1633 году, Валлис описал различные выражения для вычисления интегралов и, взяв их за основу, получил следующее выражение для числа π:

Математик и философ Уильям Броункер (1620–1684), основатель и первый президент Лондонского королевского общества, путем преобразования этого выражения в 1658 году получил следующую формулу:

Следующее выражение, известное в Европе, было открыто за ее пределами. Речь идет о формуле Мадхавы из Сангамаграма. Лейбниц повторно открыл ее в 1671 году, использовав разложение в ряд для функции арктангенса, полученное Джеймсом Грегори. Она выглядит так:

π/4 = 1–1/3 + 1/5 — 1/7 + … + (-1)n/(2n + 1) + …

и выводится из следующего разложения в ряд для арктангенса:

arctgx = х — (x3)/3 + (х5)/5 — (х7)/7 + …

XVIII век

XVIII век остался в истории веком Просвещения. Целью этой книги ни в коей мере не является критика Просвещения, однако нет сомнений в том, что в XVIII веке не было сделано значимых открытий в области исчисления и счета. Возможно, в XVII веке был совершен столь крупный прорыв в науке, что в последующем столетии ученые занимались исключительно изучением уже открытого ранее. Как бы то ни было, вычисления, логика и расчеты числа 71 в этот период следовали по пути, очерченному в XVII веке.

Вычисление числа π в XVIII веке

В XVIII веке было предложено несколько новых выражений для вычисления числа π. Первое из них получил астроном Джон Мэчин (1680–1751). Оно использовалось для вычисления π в течение нескольких веков, в том числе при компьютерных вычислениях. Использовав формулу Грегори, Лейбница и Мадхавы, Мэчин обнаружил, что угол, арктангенс которого равен 1/5, можно выразить так:

α = arctg(1/5) = (1/5) — ((1/5)3)/3 + ((1/5)5)/5 — ((1/5)7)/7 +…

На основе арктангенса угла (4α — π/4) он составил ряд, позволяющий вычислить число π, в котором используется функция, обратная котангенсу. В отличие от предыдущих, этот ряд сходился быстрее. С его помощью этому английскому математику удалось верно вычислить 100 знаков числа π. Этот ряд соответствовал следующему выражению:

π/4 = 4·arctg(1/5) — arctg(1/239).

Это выражение можно представить в виде следующего ряда:

Леонард Эйлер также внес вклад в исследование рядов, позволяющих вычислить число π. С помощью одной из своих формул ему удалось вычислить 20 знаков π менее чем за полчаса.

* * *

ЛЕОНАРД ЭЙЛЕР (1707–1783)

Швейцарский математик и физик Леонард Эйлер прожил большую часть жизни в России и Германии. Он считается ведущим математиком XVIII века и одним из крупнейших математиков всех времен. Он совершил важнейшие открытия в области анализа бесконечно малых и теории графов, а также ввел множество терминов и обозначений современной математики, особенно в области анализа, в частности обозначение функции. Он также совершил важные открытия в механике, гидродинамике, оптике и астрономии. Он был невероятно плодовитым ученым: полное собрание его сочинений насчитывает от 60 до 80 томов.

ЗНАК π

Обозначение числа к греческой буквой пи ввел Леонард Эйлер в своей книге «Введение в анализ бесконечных», изданной в 1748 году. Он использовал первую букву греческого слова periphereia — «окружность». Эйлер ввел и другие популярные обозначения, которые используются в современной математике. Он стал обозначать основание натурального логарифма буквой е, квадратный корень из минус единицы — буквой i, сумму ряда — знаком Σ, конечную разность — знаком Δ.

Логика

В XVIII веке не было совершено значимых открытий в логике, однако нет никаких сомнений, что Кант, который хоть не внес прямого вклада в эту дисциплину, тем не менее способствовал ее дальнейшему развитию. По сути, на основе идей Канта позднее сформировался логический позитивизм, а также аналитическая философия. Позднее Фреге, Гильберт, Рассел и Гёдель внесли огромный вклад в логику.

Немецкий философ Иммануил Кант (1724–1804) заложил фундамент трех основных свойств современной логики: различие между понятием и объектом, первенство высказывания как основной единицы логического анализа и понятие логики как средства изучения структуры логических систем, а не только подтверждения отдельных умозаключений.

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

* * *

РАЗЛИЧИЕ МЕЖДУ ПОНЯТИЕМ И ОБЪЕКТОМ

Готлоб Фреге (1848–1925) установил, что любое предложение или высказывание содержит выражение, обозначающее объект, и предикат, обозначающий понятие. Например, в высказывании «Сократ является философом», «Сократ» — это объект, понятие «являться философом» — предикат. Эта точка зрения существенно отличалась от принятой ранее, согласно которой высказывание рассматривалось как два термина, соединенных глаголом «являться». Новый взгляд на отношение «понятие — объект» стало основным для понимания теории множеств и отношения принадлежности элемента ко множеству.

XIX век: некоторые приемы вычислений

Первым коммерчески успешным калькулятором был арифмометр, созданный французом Шарлем Ксавье Тома де Кольмаром (1785–1870). Он успешно продавался не только во Франции, но и в других странах. Конкуренты не дремали, и через несколько лет было создано несколько альтернативных моделей. Наиболее заметными были калькулятор «Арифморель» еще одного француза Тимолеона Мореля (1842), калькулятор с зубчатыми колесами, созданный американцем Фрэнком Болдуином (1872), который независимо от него также был разработан шведом Вильгодтом Однером (1874), жившим в Санкт-Петербурге, а также круговой калькулятор англичанина Джозефа Эдмондсона (1885). Все эти машины использовались даже в первые годы XX века.

Устройство «Арифмореля» — калькулятора, созданного Тимолеоном Морелем.

Начиная с машины Мореля в калькуляторах помимо основных арифметических операций появилась возможность вычисления квадратных корней. Квадратные корни вычислялись на основании следующего разложения в ряд для функции х2:

1 + 3 + 5 + … + (2х — 1) = х2.

Для данного числа n, которое является полным квадратом, квадратный корень из n можно получить последовательным вычитанием из него чисел 1, 3, 5, пока результат вычитания не станет равен нулю. Число выполненных операций вычитания будет равно квадратному корню исходного числа. Допустим, мы хотим вычислить квадратный корень из 100. Нужно последовательно вычесть из него 1, 3, 5, 7, 9, 11, 13, 15, 17, 19. Так как мы вычли из 100 десять чисел, квадратный корень из 100 равен 10.

Если n не является полным квадратом, результатом последнего вычитания будет отрицательное число. Число выполненных операций вычитания будет приближенно равно истинному значению квадратного корня. Чтобы получить искомое значение с точностью до нескольких десятичных знаков, вышеуказанный процесс нужно повторить. При этом для каждого нового десятичного знака исходное число следует умножить на 100 в следующей степени. Например, умножим 2 на 100, чтобы вычислить квадратный корень из 200 и получить один знак после запятой. Имеем:

1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19 + 21 + 23 + 25 + 27 =

= 196 < 200 < 225 =

= 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19 + 21 + 23 + 25 + 27 + 29.

Заметим, что в верхнем ряду складывается 14 слагаемых, в нижнем — 15.

Следовательно, квадратный корень из 200 находится между 14 и 15, корень из 2 — между 1,4 и 1,5.

В XIX веке были совершены открытия, которые подготовили почву для развития современных информационных технологий. В 1835 году американский физик Джозеф Генри, известный работами по электромагнетизму, изобрел электромеханическое реле.

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

С массовым внедрением промышленных решений автоматические вычисления стали идти параллельным курсом с автоматизацией текстильной промышленности.

Француз Базиль Бушон уже в 1725 году создал перфорированную ленту для программирования ткацкого станка, на которой содержалась информация об узорах на ткани. Лента помещалась в станок, и постепенно получалась ткань с заданным узором. Несколько лет спустя, в 1728 году, помощник Бутона Жан-Батист Фалькон усовершенствовал его систему и заменил ленту перфорированными картами. В 1803 году Жозеф Мари Жаккар (1752–1834) создал знаменитый автоматический станок Жаккара на основе системы инженера Жака де Вокансона, в которой использовались карты и вращающийся барабан. Автоматический станок Вокансона, созданный в 1740 году, работал под управлением одного оператора. Система, в которой использовались перфокарты, наиболее эффективная на тот момент, непрерывно развивалась и позднее стала применяться в компьютерах XX века. Статистик Герман Холлерит (1860–1929) использовал перфокарты для кодирования результатов переписи населения США 1890 года. Холлерит был первым, кому удалось обработать информацию автоматически, поэтому он считается создателем информатики (это слово образовано слиянием слов «информация» и «автоматика»).

Перфокарты в станке Жаккара, представленном в Музее науки и промышленности в Манчестере.

Чарльз Бэббидж

Английский философ, математик, изобретатель и инженер Чарльз Бэббидж, считающийся изобретателем вычислительных машин, — один из самых выдающихся и противоречивых героев нашей истории. Он родился на окраине Лондона предположительно в 1791 году; достоверно известна лишь дата его крещения — 6 января 1792 года, в церкви Сент-Мэри в Ньюингтоне. Он изучал математику и химию — сначала в Кембриджском Тринити-колледже, куда поступил в 1810 году, затем в менее крупном и престижном колледже Петерхаус (1812). Считается, что Бэббидж сменил колледж потому, что двое его близких друзей по Тринити-колледжу Джон Гершель и Джордж Пикок превосходили его в учебе, а в Петерхаусе он стал первым учеником. В 1814 году он получил степень бакалавра, в 1817 — степень магистра математики.

Потрет Чарльза Бэббиджа кисти Сэмюэля Лоренса.

В 1812 году Бэббидж, Гершель и Пикок с коллегами под руководством профессора Роберта Вудхауза основали Аналитическое общество. Их целью было распространение аналитического исчисления Лейбница и противостояние анализу Ньютона.

Наиболее значимым достижением общества стал перевод с французского книги Сильвестра Франсуа Лакруа Traite de calcul differentiel et integral («Трактат о дифференциальном и интегральном исчислении», 1816), а также введение Пикоком нотации Лейбница на некоторых экзаменах (1817). Трехтомный труд Лакруа, переведенный Бэббиджем, Гершелем и Пикоком, получил широкое распространение в Англии. В 1819 году общество стало называться Кембриджским философским обществом.

В год окончания университета (1814) Бэббидж женился на Джорджиане Витмор. У них было восемь детей. Когда его отец, жена и ребенок умерли в 1827 году, Бэббидж получил в наследство недвижимость и солидную сумму, однако чувствовал себя совершенно разбитым и подавленным. По совету врача он на год отправился в путешествие по Европе. По возвращении он занял должность профессора Кембриджского университета, ранее принадлежавшую Ньютону. Однако он счел жалование невысоким и появлялся в университете, только когда требовалось оценить кандидатов на премию Смита, которая вручалась лучшему студенту Кембриджа.

Чарльз Бэббидж вошел в историю как создатель механических вычислительных машин. Первой из них была разностная машина (Difference Engine), которую он создал для вычисления значений многочленов. Принцип ее действия был основан на использовании конечных разностей, что позволило избежать умножения и деления. Изготовление машины было начато в 1822 году при поддержке британского правительства, однако этот проект так и не был завершен. Работы над машиной остановились в 1834 году, когда было прекращено финансирование проекта.

Изображение разностной машины Чарльза Бэббиджа, опубликованное в журнале Harper's Magazine в декабре 1864 года.

Некоторые исследователи считают, что машина Бэббиджа не могла быть закончена из-за существовавших на тот момент технических ограничений. Однако швед Георг Шутц (1785–1873) и его сын Эдвард, прочитав статью о разностной машине Бэббиджа, создали свой вариант этой машины и представили его в 1843 году.

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

В отличие от Чарльза Бэббиджа, который не смог завершить работу над своей машиной, Шутц создал полностью рабочий экземпляр. В 1991 году в лондонском Музее науки был воссоздан первый прототип машины Бэббиджа с использованием технологий того времени. Также был воссоздан второй прототип, который в настоящее время хранится в Музее компьютерной истории в городе Маунтин-Вью (штат Калифорния, США). Машина Бэббиджа позволяла выполнять расчеты с точностью до 31 знака, вычислять значения многочленов седьмой степени и имела размеры 2,4 X 2,1 X 0,9 м. Размеры машины Шутца составляли 54 X 86 X 65 см, однако она была способна вычислять значения многочленов всего лишь третьей степени с точностью до 15 знаков. В 2000 году в лондонском Музее науки также была построена печатная машина, спроектированная Бэббиджем для своей вычислительной машины.

Оставив работу над разностной машиной в 1834 году, Бэббидж занялся новым устройством, которое он назвал аналитической машиной (Analytical Engine). Аналитическая машина стала ближайшим предком современных компьютеров. С помощью разностной машины можно было вычислять лишь значения многочленов, в то время как аналитическая задумывалась как устройство широкого применения, способное вычислять значения произвольных функций. Источником энергии для новой машины Бэббиджа служил паровой двигатель, ввод информации выполнялся с помощью перфокарт, вывод — с помощью печатной машины и устройства для нанесения перфорации на перфокарты. В памяти машины могло храниться до тысячи 50-значных чисел. Она также содержала арифметическое устройство для выполнения четырех основных действий, которое Бэббидж назвал мельницей (the mill).

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

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

* * *

АДА БАЙРОН, ГРАФИНЯ ЛАВЛЕЙС (1815–1852)

Ада Августа Байрон была единственной дочерью лорда Байрона и Анабеллы Милбэнк. Девочка не знала отца, так как родители разошлись за месяц до ее рождения, и лорд Байрон навсегда покинул Англию. Она была болезненным ребенком (слабое здоровье она унаследовала от отца), поэтому обучалась на дому. Особое внимание при этом уделялось математике и другим наукам. Ее обучали известные преподаватели: Уильям Френд, Уильям Кинг, Мэри Сомервилл и Огастес де Морган. Учителя считали, что девочка сможет стать исследователем первой величины. Мэри Сомервилл представила ее Чарльзу Бэббиджу. В знак признания ее заслуг по созданию языков программирования Министерство обороны США назвало в ее честь язык программирования Ада.

* * *

Они начали сотрудничать, когда Бэббидж попросил Аду Байрон перевести с французского текст Луиджи Менабреа об аналитической машине, написанный вскоре после выступления Бэббиджа в Турине, куда его пригласил математик Джованни Плана. Ада дополнила статью Менабреа примечаниями, которые по объему превысили исходный текст. В знаменитом примечании G помимо других важнейших открытий описывается алгоритм вычисления чисел Бернулли на языке программирования машины Бэббиджа с помощью двух циклов. Так было доказано, что машина Бэббиджа может иметь самое широкое применение. Это была первая в мире компьютерная программа. Ада также описала алгоритмы вычисления тригонометрических функций, в которых использовались переменные.

* * *

БУДУЩЕЕ, ОПИСАННОЕ В ПРИМЕЧАНИИ G

В примечании G Ада Лавлейс выразила уверенность, что не только машина Бэббиджа, но и сам новый способ обработки информации произведут революцию в науке: «Аналитическая машина не претендует на то, чтобы дать начало чему-либо. Она способна выполнить всё, что мы сможем приказать ей. Она может произвести анализ, но не способна предугадать ни истинность высказываний, ни взаимосвязь между ними. Она способна помогать нам, делая доступнее то, что нам уже известно. Изначально эффект от ее использования будет получен преимущественно в этой области, однако весьма вероятно, что она окажет косвенное и взаимное влияние на саму науку. Распространение и сочетание истин и формул анализа, которое возможно будет выполнить при помощи машины, прольет свет на взаимосвязи и природу множества научных материй, которые станет возможно изучить более глубоко. Возможно, это косвенный и несколько спекулятивный результат этого открытия, но нет сомнений, что эта новая форма записи математических истин и работы с ними открывает новые перспективы, пусть и в теории. Во всех областях человеческой власти и познания помимо основной цели всегда сочетаются различные побочные воздействия».

* * *

Некоторые исследователи высказывают сомнения относительно того, кто был автором примечания G. Быть может, это был сам Бэббидж? Как бы то ни было, бесспорно, Ада обладала обширными знаниями математики и была знакома с принципом действия аналитической машины. Она настолько тесно сотрудничала с ее изобретателем, что ее вклад в разработку аналитической машины трудно переоценить.

Ада превосходно разбиралась в устройстве станка Жаккара, и некоторые авторы считают, что именно она подсказала Бэббиджу, что для ввода программ и данных в аналитическую машину можно использовать перфокарты. Ада сформулировала понятия инструкций, циклов и подпрограмм, которые известны каждому, кто знаком с языками программирования. За ее талант и знания математики Бэббидж называл ее «повелительницей чисел» (the Enchantress of Numbers).

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

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

В 1903 году ирландский бухгалтер Перси Ладгейт спроектировал машину, схожую с машиной Бэббиджа, в которой на смену паровому двигателю пришел электромотор. Испанский инженер, математик и автор множества изобретений Леонардо Торрес Кеведо использовал идеи Бэббиджа при создании автоматической шахматной машины в 1911 году. Его машина была способна играть с человеком окончание шахматной партии с королем и ладьей против короля. Машина действовала не совсем точно, но всегда ставила мат за минимально возможное число ходов, неизменно одерживая победу в партии.

Позднее, в 1930-е годы, американский ученый Вэнивар Буш создал цифровой электрический компьютер и несколько машин для решения дифференциальных уравнений. Даже в первом электромеханическом компьютере Harvard Mark I, который был создан в период с 1939 по 1943 год американским инженером Говардом Хатауэем Эйкеном при поддержке IBM, 760000 зубчатых колес и 800 километров проводов были расположены по схеме, предложенной Бэббиджем.

Если бы аналитическая машина Бэббиджа была построена, в ней было бы 30 метров в длину, 10 метров в ширину и 4,5 метра в высоту. Сложение выполнялось бы за 3 секунды, умножение — от 2 до 4 минут, не считая времени, затраченного на ввод данных в арифметическое устройство — это заняло бы еще 2,5 секунды.

Чарльз Бэббидж также известен благодаря многим другим открытиям. Он взломал шифр Виженера (вариант шифра Цезаря), разработал приспособление, сбрасывающее посторонние предметы с путей перед локомотивом, а также сформулировал экономический «принцип Бэббиджа». Он также создал современную почтовую систему и был первым, кто указал, что ширина колец на спиле дерева зависит от погодных условий, что позволило изучить климат прошлых лет.

В области философии и богословия, которые он также не обошел стороной, ему не удалось достичь столь значимых успехов. Он был очень верующим человеком и в 1837 году опубликовал «Девятый трактат Бриджуотера» (Ninth Bridgewater Treatise), последовавший за восемью трактатами по богословию, издание которых было оплачено из наследства преподобного Фрэнсиса Генри, графа Бриджуотерского. Бэббидж пытался доказать существование Бога с позиций математики. Он писал, что Бог как высший законодатель создал законы или программы, согласно которым различные виды живых существ появлялись тогда, когда это было необходимо, и не вмешивался в земные дела напрямую. Он также доказывал возможность происхождения чудес с математической точки зрения, использовав методы теории вероятности. Его работы были написаны в то же время, что и труды Чарльза Дарвина (1809–1882).

Логика и Джордж Буль

В 1847 году была опубликована книга «Математический анализ логики» (Mathematical Analysis of Logic) Джорджа Буля, в которой была представлена булева алгебра — попытка применить методы алгебры к логике первого порядка. В настоящее время булева алгебра в общем виде используется при проектировании электрических схем, однако изначально открытия Буля были признаны только узкими специалистами. Лишь в XX веке была понята их важность и возможность применения в информатике.

Большая заслуга в этом принадлежит американскому математику и инженеру Клоду Шеннону (1916–2001), который считается создателем теории информации. Шеннон познакомился с работой Буля на занятиях по философии в Мичиганском университете, и в 1937 году защитил магистерскую диссертацию в Массачусетском технологическом институте (MIT), показав, что булеву алгебру можно использовать для оптимизации электрических цепей. В 1935 году независимо от Шеннона логик Виктор Шестаков (1907–1987) из Московского государственного университета также использовал булеву алгебру в этих же целях.

Булева алгебра оказалась столь полезной в информатике потому, что она описывает идеальный сценарий с точки зрения двоичной логики. В ней используются только нули и единицы, основными операциями являются И, ИЛИ и НЕ, то есть конъюнкция (бинарная операция, обозначаемая ), дизъюнкция (бинарная операция, обозначаемая ) и отрицание (унарная операция, обозначаемая ¬). Эти логические операции определяются с помощью следующих таблиц истинности.

Другие привычные операции, например импликация (операция, схожая с конструкцией «если… то»), выражаются через три основные операции, представленные выше: (х — > у) = ¬ х  y, Кроме того, в виде комбинации этих операций можно представить любую другую логическую функцию. Так называемый закон де Моргана гласит, что существует всего две основные логические операции. Например, это могут быть дизъюнкция и отрицание, с помощью которых также можно выразить операцию конъюнкции.

* * *

ДЖОРДЖ БУЛЬ (1815–1864)

Британский математик и философ Джордж Буль создал алгебру, которая стала основой современной вычислительной техники. Именно поэтому он считается одним из основателей информатики. Его важнейшими математическими трудами являются Treatise on Differential Equations («Трактат о дифференциальных уравнениях»), опубликованный в 1859 году, и его продолжение Treatise on the Calculus of Finite Differences («Трактат о конечных разностях»), вышедший в 1860 году. Свою систему правил для математической записи и упрощения логических и философских задач, аргументы которых могут принимать только два значения (истина или ложь), он изложил в труде «Исследование законов мышления, на которых основываются математические теории логики и вероятностей» (An Investigation of the Laws of Thought, on Which are Founded the Mathematical Theories of Logic and Probabilities).

* * *

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

Число π в XIX веке

В середине XVIII века, точнее в 1761 году, немецкий математик, физик, астроном и философ французского происхождения Иоганн Ламберт (1728–1777) показал, что число π и его квадрат π2 являются иррациональными числами. Тем самым была доказана невозможность вычислить их «точное» значение. Лишь 120 лет спустя работы по вычислению значения π снова обрели важность. В 1882 году математик Фердинанд Линдеман (1852–1939) доказал, что число π является трансцендентным. Это означало, что задача о квадратуре круга нерешаема с помощью циркуля и линейки.

Некоторые задачи, касающиеся числа π, до сих пор остаются открытыми, в частности задача о нормальности π. Иррациональное число является нормальным, если вероятность появления числовых последовательностей равной длины в его записи одинакова. Например, все цифры от 0 до 9 фигурируют в записи нормального с одинаковой вероятностью, равной 1/10, все последовательности из двух цифр — с вероятностью 1/100 и так далее. Нормальность числа π все еще не доказана, однако считается, что π действительно является нормальным. Были подсчитаны частоты, с которыми в его записи появляются различные цифры. В конце XX века американский математик Дэвид Бэйли проанализировал первые 29360000 знаков π. Рассмотрев последовательности длиной до 6 цифр включительно, он не обнаружил никаких признаков неравномерности. Различия в частотах оказались минимальными и не имели статистической значимости. Приведем в качестве примера частоты, с которыми в записи π появляются цифры от 0 до 9.

* * *

АЛГЕБРАИЧЕСКИЕ И ТРАНСЦЕНДЕНТНЫЕ ЧИСЛА

Число называется алгебраическим, если оно является корнем многочлена одной переменной с целыми коэффициентами. Все целые и рациональные числа, а также некоторые иррациональные, являются алгебраическими. Наиболее известное из алгебраических иррациональных чисел — √2. Это число является корнем многочлена х2 — 2 = 0. Множество алгебраических чисел является счетным. Трансцендентное же число не является корнем многочлена с целыми коэффициентами. Самыми известными трансцендентными числами являются π и е.

Глава 4 Компьютеры в XX веке

Бурный XX век стал свидетелем всевозможных изменений в политике, общественной жизни и, разумеется, в науке, которые сопровождались невероятной технической революцией. Эта история великих теорий, потрясающих открытий и горьких разочарований сопровождалась прорывом в области вычислений, благодаря чему стало возможным создание нового цифрового мира. Развитие информатики было поистине удивительным, однако в архитектуре вычислительных машин не произошло значительных изменений. В современных компьютерах по-прежнему используется архитектура фон Неймана.

Серия Z Конрада Цузе

Главными героями в истории информатики и вычислительной техники в XX веке были исключительные личности, которые много лет были никому не известны. Среди них — немецкий инженер Конрад Цузе и его вычислительные машины серии Z. Большинство изобретений Цузе долгое время оставались незамеченными, так как были сделаны незадолго до начала Второй мировой войны, а работа над ними продолжалась в последующие несколько лет. Цузе, сам того не осознавая, следовал идеям Бэббиджа, с работами которого он был совершенно не знаком. Когда Джон фон Нейман позднее описал архитектуру компьютера, он не руководствовался работами Цузе. Несомненно, созданная ими архитектура вычислительных машин была оптимальной: это подтвердили специалисты в области логики. Она содержала устройство управления, память и арифметико-логическое устройство для выполнения вычислений.

Цузе создал две первые машины в период с 1935 по 1939 год, перед самым началом Второй мировой войны. Его первая патентная заявка датирована 11 апреля 1936 года. В 1938 году он подал патентную заявку в США. Она была отклонена, так как Цузе изложил свое открытие недостаточно подробно. Его вычислительные машины назывались Z1 и Z2. Сначала Цузе назвал первую машину VI (от слова Versuchsmodell, что означало «экспериментальная модель»), но затем сменил название, чтобы избежать путаницы с названиями ракет VI и V2 Вернера фон Брауна.

Первая машина Z1 имела размеры 2 х 1,5 метра. Сделанная из стали, она была достаточно ненадежной: поправки требовалось вносить каждые несколько минут. Это был всего лишь двоичный механический калькулятор с ограниченными возможностями программирования, работавший от электричества. Цузе сконструировал Z2, чтобы исправить недостатки первой машины. Для сохранения чисел и представления чисел с фиксированной запятой в ней использовались реле. Позднее, по совету Хельмута Шрайера, Цузе спроектировал машину Z3, в которой использовались электронные лампы. Эта машина работала без сбоев.

Она была представлена в Институте аэродинамических исследований 5 декабря 1941 года. В машине Z3 ввод данных выполнялся с клавиатуры, а управляющая программа записывалась на целлулоидной ленте. В памяти машины можно было сохранять до 64 чисел, представляемых в двоичной системе счисления с плавающей запятой. Для хранения каждого числа использовалось 22 бита: 1 бит для знака, 7 для показателя степени, 14 для мантиссы. Цузе обнаружил, что в представлении числа с плавающей запятой первый бит может быть всегда равным единице — достаточно подобрать соответствующий показатель степени. Эта форма представления чисел используется и сейчас. С ее помощью можно «сэкономить» один бит, который всегда равен единице. Благодаря открытию Цузе машина Z3 могла работать с числами, мантисса которых представлялась 13 битами. Тем не менее эта машина имела одно важное ограничение: в ней не были реализованы условные переходы. Скорость вычислений составляла три-четыре операции сложения в секунду, умножение выполнялось за четыре-пять секунд.

По заказу Института аэродинамических исследований Цузе немедленно приступил к работе над Z4. Окончательный вариант машины был представлен 28 апреля 1945 года. В памяти машины можно было сохранять 1024 32-битных числа. В ней также были реализованы подпрограммы и условные переходы. Кроме того, был реализован механизм чтения двух инструкций, следующих за данной. Таким образом, операции можно было менять местами, если это не влияло на результат, что обеспечивало экономию времени. Эта процедура была реализована в более поздних компьютерах и получила название lookahead («просмотр вперед»).

Перед самым окончанием войны Цузе переехал на ферму в Альпах и начал работу над докторской диссертацией, озаглавленной «Общая теория вычислений». В этой диссертации, завершенной в 1946 году, описывался язык Планкалкюль (от нем. Plankalkül — «исчисление планов») — протоязык программирования, который тем не менее не был реализован. Планкалкюль был создан для решения числовых и других задач. Для него был характерен высокий уровень абстракции, значительно превосходящий другие языки программирования того времени. Первым языком, который действительно мог с ним сравниться, был Алгол, созданный много лет спустя.

* * *

КОНРАД ЦУЗЕ (1910–1995)

В университетские годы немецкому инженеру Конраду Цузе приходилось выполнять множество расчетов вручную. Он изнывал от скуки и задумался о создании машины, способной помочь ему в расчетах. По окончании университета он начал работать на авиационном заводе, но вскоре оставил работу и занялся постройкой своей машины в доме родителей. Вскоре он создал первый в мире работающий программируемый компьютер. Он создал машины общего назначения серии Z, машины S1 и S2 для выполнения расчетов, связанных с бомбардировками, а также машину L1 для вычисления значений логических функций. Он также разработал язык программирования Планкалкюль, который не вышел за рамки теории. Цузе основал несколько компаний для постройки своих машин. Важнейшей из них стала Zuse KG, силами которой были частично изготовлены машины серии Z. Zuse KG считается первой в истории компьютерной компанией.

* * *

В 1947 году в разрушенной послевоенной Германии Цузе возвращается к работе над своими машинами. Он наладил контакты с IBM, а позднее с Remington-Rand, с которой заключил соглашение. Он создал машины на электронных лампах, в частности Z22, и на транзисторах, в частности Z23 и Z3. Позднее ученый разработал Z64 — графопостроитель, управляемый машиной.

Единственным образцом первых машин Цузе, дошедшим до наших дней, стала Z4 — первая коммерческая вычислительная машина. Она использовалась во множестве учреждений вплоть до 1959 года. Один из экземпляров Z4 вместе с воссозданной версией Z3 сейчас хранится в Немецком музее Мюнхена. К сожалению, все остальные машины были разрушены во время бомбардировок Берлина.

Машина Тьюринга и «Колосс»

Алан Тьюринг (1912–1954) в детстве хотел стать врачом, но в итоге стал математиком, философом и специалистом по криптографии, а также создателем современной информатики. Он известен в первую очередь благодаря своим теоретическим работам, однако также сыграл очень важную роль в практической реализации одного из первых компьютеров. Тьюринг сделал свое первое открытие в теоретической математике в 1936 году, решив проблему разрешения (Entscheidungsproblem), сформулированную Давидом Гильбертом. Чтобы справиться с этой задачей, Тьюринг создал модель вычислений, в которой дал формальное определение алгоритму (или программе). Эта модель вошла в историю под названием машина Тьюринга.

В 1928 году влиятельный немецкий математик Давид Гильберт (1862–1943), который в 1900 году предложил знаменитый список задач, начал работу над проблемой разрешения, которую впервые сформулировал Лейбниц. Гильберт считал, что нерешаемых задач не существует. Он предложил гипотезу, согласно которой всегда можно составить программу (алгоритм), которая сможет дать однозначный верный ответ на любой заданный вопрос. Независимо друг от друга Алан Тьюринг и американский математик Алонзо Чёрч доказали, что Гильберт ошибался: нерешаемые задачи существуют, а предложенную Гильбертом программу (алгоритм) составить невозможно. Следовательно, математика не является разрешимой, то есть не существует метода, который позволил бы определить истинность или ложность произвольного математического утверждения.

Математик Алан Тьюринг, считающийся одним из создателей компьютеров.

Чёрч и Тьюринг в своих доказательствах использовали созданные ими модели: первый применял лямбда-исчисление, второй — разработанную им машину. Оба дали формальное определение алгоритму и использовали в своих доказательствах арифметические задачи. Существование арифметических задач, для которых решения отсутствуют, означало бы, что решить любую произвольную задачу также невозможно. Однако работа Тьюринга была намного более доступной и понятной.

Он свел проблему разрешения к проблеме остановки и доказал, что она неразрешима с помощью его машины: нельзя определить алгоритмически, завершит ли данная машина Тьюринга свою работу в какой-то момент или нет. Чёрч и Тьюринг не соперничали; напротив, оба осознавали, что их модели, несмотря на формальные различия, были одинаково мощными, и объединили усилия.

* * *

КАК РАБОТАЕТ МАШИНА ТЬЮРИНГА?

Представим себе бесконечную ленту, на которой записаны входные символы некой задачи и на которой можно печатать. Машина Тьюринга содержит считывающее устройство, расположенное в определенной части ленты. Это считывающее устройство позволяет выполнять считывание и запись на ленту, а программа машины Тьюринга может перемещать считывающее устройство в заданное положение. Возможные состояния машины представляются посредством множества состояний Q. Программирование машины представляется в виде функции перехода, которая определяет новое состояние на основе текущего состояния и входного символа.

Формально машина Тьюринга определяется на основе кортежа из семи элементов. Кортеж — это упорядоченная последовательность элементов, то есть перечень ограниченного числа объектов. Кортежи используются для описания математических объектов, имеющих структуру. Обозначим кортеж, который будет обрабатывать наша машина Тьюринга, как

МТ = (Γ, Σ, Ь, Q, q0, f, F).

Его элементы определяются следующим образом.

• Γ — алфавит, символы которого записываются на ленте.

• Σ  Γ — алфавит, символы которого подаются на вход машины. Множество возможных входных символов является подмножеством символов, которые могут быть записаны на ленте. На ленте также будут находиться символы, записанные самой машиной.

• b  Γ, Ь  Σ: Ь определяет пустое пространство. Это символ, не принадлежащий множеству входных символов. Изначально лента содержит конечное число символов Σ; оставшаяся часть ленты (которая является бесконечной) заполнена символами Ь.

• Q — множество состояний.

• q0   Q — начальное состояние.

• f — функция перехода. Для данного состояния и элемента, записанного на ленте, эта функция определяет новое состояние, записывает символ на ленте и перемещает считывающее устройство влево (I), вправо (D) или же оставляет неподвижным (Р). Таким образом, функция f является функцией вида f: Q x Γ —> Q x Γ х {I, D, Р}.

F  Q — множество конечных состояний.

* * *

В апреле 1936 года американский математик Алонзо Чёрч из Принстонского университета опубликовал работу о проблеме разрешения. Чёрч пришел к тому же выводу, что и Тьюринг, доказав, что не все в математике является вычислимым.

В своем доказательстве он использовал лямбда-исчисление, разработанное им совместно с коллегой Стивеном Клини, которое радикально отличалось от машины Тьюринга. Тьюринг опубликовал свое решение проблемы разрешения в августе того же 1936 года. Это была его знаменитая статья «О вычислимых числах в приложении к проблеме разрешения», в которой были переформулированы результаты Курта Гёделя (1906–1978) о пределах доказуемости и вычислений, а также содержались ссылки на работу Чёрча. Вместо того чтобы спорить, кто совершил открытие первым, в сентябре того же года Тьюринг переходит на работу в Принстонский университет, чтобы написать диссертацию о проблеме разрешения под руководством Чёрча. Он защитил диссертацию в 1938 году, получил степень доктора и вернулся в Кембридж. Этот удачный союз талантов принес немалую выгоду всему человечеству.

* * *

БЛЕТЧЛИ-ПАРК И ЭНИГМА

Легендарное шифровальное подразделение Великобритании Блетчли-парк располагалось в графстве Бакингемшир в 80 километрах от Лондона. Во время Второй мировой войны наиболее авторитетные английские ученые работали в Блетчли-парке над взломом немецких шифров. Это подразделение располагалось в одноименном викторианском поместье (сегодня музей криптографии). В Блетчли-Парке был расшифрован код шифровальной машины «Энигма». Эта машина содержала шифровальный механизм, состоящий из вращающихся роторов и колец, который позволял вооруженным силам нацистской Германии расшифровывать и зашифровывать сообщения. Усилия британских ученых по взлому шифра «Энигмы» не пропали даром: считается, что прочтение предположительно секретных сообщений немцев позволило приблизить окончание войны на несколько лет.

* * *

Эти значимые события, касающиеся наиболее теоретической области науки, происходили в один из самых драматичных моментов современной истории. Политическая ситуация в Европе накалялась, и мир двигался к войне. Опасаясь, что Англия вступит в войну с Германией, Тьюринг во время работы над диссертацией начал заниматься криптографией. Британское правительство в 1939 году пригласило его работать в Блетчли-парке вместе с другими исследователями. Перед ними стояла задача взломать секретный шифр немецкой армии — код «Энигмы». Благодаря своим знаниям Тьюринг смог взломать шифр немецких воздушных сил в середине 1941 года, однако в феврале 1942 шифр был усложнен, и сообщения немцев снова стало невозможно прочесть.

Чтобы расшифровать их, Тьюринг и его коллеги разработали несколько вычислительных машин. Тьюринг еще во время работы в Принстоне изобрел машину, позволявшую выполнять умножение. Группа Тьюринга создала машину под названием «Колосс», которая считается первым электронным программируемым компьютером в мире. Было построено десять экземпляров «Колосса». Первый из них начал работу в декабре 1943 года, на два года раньше, чем американский ENIAC. В конце 1942 — начале 1943 года Тьюринг совершил новую поездку в США, чтобы помочь американским военным взломать немецкие шифры. Во время поездки он познакомился с Клодом Шенноном, создателем теории информации и автором определения энтропии.

После окончания войны Тьюринга пригласили в Национальную физическую лабораторию (National Physical Laboratory), отвечавшую за развитие научно-технических стандартов в Великобритании. Там он разработал ACM (Automatic Computer Machine) — автоматическую компьютерную машину — и сформулировал понятие микропрограммирования как способа задания и изменения команд арифметико-логического устройства. Существует и альтернативный вариант, при котором арифметико-логическое устройство реализовано в оборудовании компьютера и его операции изменять нельзя. Тьюринг также определил понятия подпрограммы и программной библиотеки.

Весь 1947 год он отдыхал в Кембридже, где написал статью, в которой представил нейронную сеть — модель, использующую понятия из физиологии и неврологии. В следующем году, увидев, что работы над автоматической компьютерной машиной остановились, он перешел на службу в Манчестерский университет, где начал работу над программным обеспечением компьютера Mark I Максвелла Ньюмана.

В этот период он создал свои наиболее абстрактные работы. Он написал знаменитую статью «Вычислительные машины и разум», опубликованную в журнале Mind в октябре 1950 года, в которой изложил свою точку зрения на искусственный интеллект и описал знаменитый эксперимент, известный как тест Тьюринга. Целью эксперимента было определить, может ли машина мыслить.

Два оператора работают на «Колоссе» Mark 2.

* * *

ПОСТЫДНАЯ НЕСПРАВЕДЛИВОСТЬ

Математик и логик, который в немалой степени определил облик современного мира, в последние годы жизни подвергся столь постыдному и несправедливому преследованию со стороны полного предрассудков послевоенного британского общества, что это стоило ему жизни. Блестящая карьера Алана Тьюринга прервалась, когда его начали преследовать за нетрадиционную сексуальную ориентацию, которая в то время считалась в Великобритании преступлением. От подобных обвинений за 50 лет до этого пострадал Оскар Уайльд. Тьюринг знал, что ему нечего стыдиться, и начался судебный процесс, широко освещавшийся в прессе. Суд предложил ему выбор между тюремным заключением и гормональной терапией для подавления либидо. Желая избежать тюрьмы, он согласился на лечение, которое продолжалось в течение года, привело к значительным изменениям в организме ученого и сделало его импотентом. После этого Тьюринг покончил жизнь самоубийством, приняв цианид. Еще более примечательно, что в письмах коллегам он выражал беспокойство по поводу того, что эти обвинения бросят тень на его работы по искусственному интеллекту, которые он сам считал крайне важными для всего человечества. В 2009 году Гордон Браун, который в то время занимал пост премьер-министра Великобритании, публично принес извинения от имени британского правительства за преследование, которому подвергся Алан Тьюринг в последние годы жизни. С момента смерти Тьюринга, который оказал неоценимые услуги своей стране и всему цивилизованному миру в борьбе с нацизмом, прошло почти 60 лет.

* * *

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

Архитектура фон Неймана

Джон фон Нейман вошел в историю информатики в неспокойный период, во время Второй мировой войны, когда он работал над атомной бомбой в рамках «Проекта Манхэттен». Для проекта требовались новые вычислительные машины, которые в то время становились все более мощными и продвинутыми. Фон Нейман начал поиски ведущих исследователей в области вычислений по всей стране. Он обратился к Джону Пресперу Эккерту (1919–1995) и Джону Уильяму Мокли (1907–1980) из Пенсильванского университета, которые сконструировали компьютер ENIAC (Electronic Numerical Integrator and Computer — электронный числовой интегратор и вычислитель), американский ответ британскому «Колоссу». Они хотели разработать новую, улучшенную машину под названием EDYAC (Electronic Discrete Variable Automatic Computer — электронный автоматический вычислитель с дискретными переменными). В марте 1945 года фон Нейман изложил свои идеи в ставшем знаменитым документе «Первый черновик отчета об EDYAC», автором которого значился он один, что стало причиной разногласий Неймана с Эккертом и Мокли.

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

1. Извлечение инструкции из памяти.

2. Декодирование.

3. Исполнение.

* * *

ENIAC

ENIAC был завершен и представлен прессе в 1945 году, проработав десять лет до окончательной остановки в 1955 году. Учеными, внесшими основной вклад в его создание, были Герман Хайн Голдстайн, Джон Пресперт Эккерт и Джон Уильям Мокли. Этот огромный компьютер занимал площадь в 63 м2, весил 30 тонн и имел 2,6 метра в высоту, 0,9 — в ширину и 26 — в длину. В нем использовалось 18000 электронных ламп, 72000 диодов, 70000 резисторов и 1500 реле. Чтобы построить ENIAC, потребовалось выполнить примерно 5 миллионов соединений ручной пайки. Его стоимость составила почти полмиллиона долларов. В нем отсутствовала память, однако в его 20 накопителях могло сохраняться 20 десятизначных чисел. Переключатели также позволяли сохранять значения функций (104 двенадцатизначных числа). Сложение выполнялось за 0,2 миллисекунды, умножение — за 2,8 миллисекунды. При работе ENIAC температура в машинном зале поднималась до 50 °C. Ходили слухи, что во время его работы в Филадельфии, где располагался компьютер, случались кратковременные отключения электричества, так как он потреблял 160 кВт электроэнергии.

* * *

Таким образом обрабатывались все инструкции, последовательно записанные в памяти компьютера, если только среди инструкций не встречалась инструкция условного перехода. Эта архитектура не слишком отличалась от той, что использовали Чарльз Бэббидж и Конрад Цузе. Эта же архитектура используется в современных компьютерах.

После публикации «Первого черновика» фон Нейман занялся поисками финансирования для постройки более мощной вычислительной машины. Этой машиной стал ADIVAC, разработанный в IAS (Institute for Advanced Study — Институт перспективных исследований) в Принстоне в 1953 году.

* * *

ДЖОН ФОН НЕЙМАН (1903–1957)

Американец венгерского происхождения Джон фон Нейман — одна из ключевых фигур в науке XX столетия. Он был пионером современных цифровых вычислений и совершил открытия во многих областях: квантовой физике, кибернетике, экономике и, разумеется, математике. Фон Неймана называли вундеркиндом; в 1926 году, когда ему было всего 23 года, он получил степень доктора математики, защитив диссертацию по аксиоматике теории множеств. В Европе он занимался исследованиями в области математики и квантовой механики.

Он преимущественно работал в Гёттингене под руководством Давида Гильберта и написал книгу ««Математические основы квантовой механики» на немецком языке. В 1930 году Нейман эмигрировал в США, в возрасте 29 лет занял одну из пяти первых профессорских должностей в принстонском Институте перспективных исследований. Еще одну из этих должностей занимал Альберт Эйнштейн. Фон Нейман считается создателем теории игр и автором понятия MAD (Mutually Assured Destruction — «Взаимное гарантированное уничтожение»). Он работал над Манхэттенским проектом и созданием водородной бомбы.

* * *

Первые компьютеры в США

ENIAC как компьютер общего назначения был огромным шагом вперед, однако некоторые технические решения, использованные при его постройке, оставляли желать лучшего. Основная проблема заключалась в том, что для смены программы требовалось изменять конфигурацию электрических цепей вручную. Так как программа не сохранялась в памяти, в отличие от современных компьютеров, то для определения того, какие расчеты и в каком порядке следует произвести, требовалось подключать и отключать переключатели, как на старинных телефонных станциях. Эта задача была очень трудоемкой и требовала столько времени, что выгода от использования компьютера была крайне сомнительной.

С целью решить проблемы ENIAC были начаты работы над новым компьютером — EDVAC. Эккерт, Мокли и фон Нейман очень подробно проанализировали, как должно производиться программирование компьютера, и пришли к выводу, что оптимальным вариантом будет хранение программы в памяти подобно тому, как в ней сохранялись числа. Трудно поверить, что в прошлом компьютерные программы и аппаратное обеспечение не были разделены. Результатом этой идеи стало рождение языков программирования и программирования как отдельной дисциплины.

Создание EDVAC стало значимым событием в истории информатики.

Работы над EDVAC были закончены в 1949 году в Институте Мура Пенсильванского университета. К тому времени Эккерт и Мокли уже не участвовали в проекте, так как покинули его в 1946 году. В EDVAC использовалось 6000 ламп и 12 000 диодов, он весил 7850 килограммов и занимал площадь в 45,5 квадратных метров. Для работы ему требовалось 56 кВт электроэнергии. Он был намного легче ENIAC, учитывая масштаб этих цифр. Он также был быстрее своего предшественника: сложение выполнялось за 864 микросекунды, умножение — за 2900 микросекунд.

В это же время на «Первый черновик» фон Неймана обратили внимание в Великобритании. Морис Уилкс из Кембриджского университета в том же 1949 году сконструировал EDSAC (Electronic Delay Storage Automatic Calculator — автоматический вычислитель на электронных линиях задержки). Это была первая электронная вычислительная машина с набором внутренних команд. Однако первым компьютером с набором внутренних программ стал SSEM. Его память состояла из 512 ячеек по 17 бит каждая. Первая компьютерная игра в мире — крестики-нолики под названием ОХО — была создана на EDSAC. На основе этой вычислительной машины был создан первый компьютер, применявшийся в коммерческих целях — LEO I.

Вырезка из британской газеты, в которой рассказывается о создании EDSAC.

Оставив Пенсильванский университет, Эккерт и Мокли основали компанию Eckert-Mauchly Computer Corporation для постройки UNIVAC — акроним от Universal Automatic Computer, универсальный автоматический компьютер, где слово «универсальный» означало, что компьютер будет способен решать научные, технические, экономические и другие задачи.

Первой организацией, которая приобрела UNIVAC Эккерта и Мокли, стало Бюро переписи населения США. По завершении работ над компьютером в 1951 году компания Эккерта и Мокли была поглощена более крупной компанией Remington Rand. Второй компьютер был куплен Пентагоном в 1952 году. Эти вычислительные машины считаются первыми коммерческими компьютерами в мире.

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

Пульт управления UNIVAC I, хранящийся в Музее науки Бостона.

Основным преимуществом UNIVAC для многих пользователей была не только скорость вычислений, но и использование лент вместо перфокарт для чтения и записи информации. Перфокарты требовали вмешательства оператора, и их замена на ленту означала увеличение степени автоматизации расчетов. Отбор данных производился самой машиной. UNIVAC производил сложение двух чисел за 0,5 микросекунды.

До выхода UNIVAC на рынок компания IBM уделяла основное внимание выпуску калькуляторов, работавших на перфокартах. Однако увидев интерес к новому компьютеру, IBM начала развивать проекты в этом направлении. Первой вычислительной машиной подобного типа стал IBM 701, который был схож с UNIVAC и назывался «электронной машиной для обработки данных». Фон Нейман, который в то время работал над созданием своего компьютера в Принстоне, участвовал в этом проекте в качестве консультанта. Работы над IBM 701 были завершены в 1952 году, а в начале 1953-го он был отправлен в лабораторию Лос-Аламоса, где велась разработка ядерного оружия.

Число π в XX веке

Развитие аппаратного обеспечения в течение XX века позволило вычислить τ с более высокой точностью. В настоящее время известно более триллиона знаков этого числа. Последний результат содержит почти 2,7 триллиона знаков после запятой, то есть 2,7·1012 знаков[1].

До появления компьютеров наилучших результатов добился англичанин Д. Фергюсон, который исключительно с помощью калькулятора вычислил свыше тысячи знаков: 620 знаков в 1946 году, 808 — в 1947-м, 1120 — в 1949-м (совместно с Джоном Ренчем).

Джон Ренч в том же году впервые в истории вычислил приближенное значение τ с помощью компьютера. По инициативе Джона фон Неймана расчеты производились на компьютере ENIAC. Спустя 70 часов вычислений было получено 2037 знаков Я. Пять лет спустя, в 1954 году, Николсон и Джинель превзошли этот результат, вычислив 3092 знака Я всего за 13 минут с помощью IBM NORC — самого мощного компьютера того времени. В 1959 году, опять же спустя пять лет, на IBM 704, первом массовом компьютере, где была реализована арифметика с плавающей запятой, за 4,3 часа было вычислено 16167 знаков. Расчеты произвел Франсуа Женюи в Париже. Вскоре пал рубеж в 100000 знаков: его преодолели Дэниел Шенке и Джон Ренч в 1961 году с помощью нового компьютера IBM 7090, в котором вместо электронных ламп использовались транзисторы, что позволило в шесть раз увеличить скорость расчетов по сравнению с его предшественниками. 100265 знаков были вычислены за 8,7 часа.

Джин Гийу в 1966 году установил новый рекорд, вычислив 250 000 знаков за 41 час 55 минут. Он же в 1967 году получил 500 000 знаков за 28 часов 10 минут.

Впечатляющий показатель в миллион знаков был достигнут усилиями Джина Гийу и Мартина Буйе в 1973 году. Они использовали компьютер CDC 7600 компании Control Data Corporation — конкурента IBM на рынке компьютеров второго поколения (в них использовались транзисторы), которые выпускались в 1960-е. За 23 часа 18 минут было вычислено 1001250 знаков 71.

В 1980-е главную роль играли японцы Ясумаса Канада и Казунори Миёши: в 1981 году им удалось преодолеть отметку в 2 миллиона знаков за 137 часов, в 1982-м — 8 миллионов за 6 часов 52 минуты, в 1983-м — 16 миллионов менее чем за 30 часов, в 1987-м на японском компьютере NEC SX-2 им удалось вычислить 100 миллионов знаков за 35 часов 15 минут. В 1989 году Григорий Чудновский, который считается одним из лучших среди ныне живущих математиков, и его брат Давид вычислили свыше миллиарда знаков 71 на компьютере IBM 3090.

Отметку в триллион знаков преодолел Ясумаса Канада и возглавляемая им группа, которая использовала компьютер HITACHI SR8000/MPP. Этот рекорд был установлен в Токио в декабре 2002 года. Для вычисления 1241100000000 знаков потребовалось 600 часов, то есть 25 суток вычислений, что соответствует скорости 574583 знака в секунду. В апреле 2009 года японец Дайсуке Такахаши из университета Цукуба вычислил более 2 триллионов знаков за 29,09 часа. Нынешний рекорд, который составляет почти 2,7 триллиона знаков[2], удерживает французский программист Фабрис Беллар, который использовал обычный персональный компьютер под управлением операционной системы Linux. На выполнение расчетов ему потребовался 131 день.

Большинство этих результатов были получены благодаря открытиям удивительного и загадочного индийского математика Сринивасы Рамануджана (1887–1920). Один из полученных им рядов, опубликованный в 1914 году, дает 8 новых знаков π на каждый член ряда. Этот ряд записывается так:

На основе результатов, полученных Рамануджаном, были найдены ряды, которые сходятся еще быстрее и позволяют получить несколько верных знаков числа π для каждого члена ряда. Братья Джонатан и Питер Борвейн, канадцы шотландского происхождения, открыли ряд, каждый член которого дает 31 новый знак π.

Остальные результаты, среди которых выделяются достижения Ясумасы Канады, получены с помощью формулы Карла Фридриха Гаусса (1777–1855), в которой устанавливается связь между числом π и средним арифметико-геометрическим. Формула Гаусса записывается следующим образом:

В этой формуле MAG (а, Ь) — это среднее арифметико-геометрическое чисел а и Ь.

Равенства, недавно полученные Дэвидом Бэйли, Питером Борвейном и Саймоном Плуффом, представляют собой наиболее интересные выражения, связанные с числом π. В 1997 году эти исследователи опубликовали ряд формул, которые позволяют вычислить любой знак двоичной записи π без необходимости вычислять предшествующие ему знаки. Эти же формулы, очевидно, можно использовать для расчета знаков π в любой системе счисления по основанию, кратному двум, в частности в шестнадцатеричной системе счисления. Авторы подтвердили корректность своего метода, вычислив миллионный, 10-миллионный, 100-миллионный, миллиардный и 10-миллиардный знаки шестнадцатеричной записи π. В результате были получены следующие шестнадцатеричные числа.

* * *

СРЕДНЕЕ АРИФМЕТИКО-ГЕОМЕТРИЧЕСКОЕ

Среднее арифметико-геометрическое определяется на основе двух сходящихся рядов: один из них образован средними арифметическими, другой — средними геометрическими. Напомним выражения для вычисления обеих средних величин:

МА(а, Ь) = (a + b)/2

MG(a, b) = √(a·b).

Первые члены рядов mа и mg определяются так: ma1 = МА(a, b), mg1 = MG(а, b). Члены ряда в общем виде определяются так:

man+1 = МА(man, mgn),

mgn+1 = МG(man, mgn)

Эти два ряда сходятся к одному и тому же значению — среднему арифметико-геометрическому MAG(а, Ь).

* * *

Одна из формул, предложенных Бэйли, Борвейном и Плуффом записывается так:

* * *

СИСТЕМЫ СЧИСЛЕНИЯ

В десятичной системе счисления, как следует из ее названия, используется десять различных цифр. Они записываются в привычном нам виде: 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9.

В двоичной системе счисления используются всего две цифры — 0 и 1. В шестнадцатеричной системе используется 16 цифр. Чаще всего они записываются так: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, А, В, С, D, Е, F. Символ А соответствует значению 10 в десятичной системе счисления, В — 11, С — 12, D — 13, Е — 14, F — 15.

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

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

* * *

Сомножитель 1/16n  позволяет находить с помощью этого выражения знаки двоичной записи π. Еще одна из предложенных ими формул выглядит так:

Расчеты знаков Я велись на протяжении нескольких тысяч лет, и в них участвовали наиболее выдающиеся умы в истории человечества. В настоящее время благодаря компьютерам число известных знаков π превышает несколько триллионов, однако для большинства вычислений достаточно всего нескольких знаков.

В статье, опубликованной в специализированном журнале в 1984 году, братья Борвейн констатировали удивительный факт, не углубляясь в анализ его причин:

«На практике всего 39 знаков Я достаточно для вычисления длины окружности радиуса 2·1025 метров (это расстояние больше, чем путь, который пройдет частица, движущаяся со скоростью света, в течение 20 000 миллионов лет, то есть это расстояние превышает радиус Вселенной), причем ошибка не будет превышать 10-12 метра (это расстояние меньше радиуса атома водорода). Нет никаких сомнений, что вычисление значения π с максимально возможной точностью имеет больше математическую, чем практическую ценность».

Глава 5 Программирование и программы

Развитие аппаратного обеспечения шло параллельно с эволюцией языков программирования. На бытовом уровне язык программирования можно определить как коммуникативный код, с помощью которого можно объяснить компьютеру, что нужно делать, чтобы решить данную задачу. Иными словами, это перечень инструкций, записанный понятным компьютеру способом в заданном порядке. Инструкции описывают последовательность действий, необходимых для получения желаемого результата. При взгляде на это определение в памяти мгновенно всплывают наши старые знакомые, о которых мы рассказали в первых главах этой книги, — алгоритмы.

И действительно, согласно более формальному определению, язык программирования — это способ описать алгоритмы, управляющие поведением компьютера.

Разумеется, инструкции языка программирования должны быть четкими и однозначными и всегда должны служить решению конкретной задачи. В языке программирования также должен быть реализован основной элемент алгоритмов и языков программирования — повтор. В языках программирования повторы реализованы двумя способами — с помощью итерации и рекурсии. Итерация — это организация обработки данных, при которой действия повторяются многократно. Она реализуется с помощью инструкций, подобных операторам repeat, while и for. Рекурсия — это повторение действий самоподобным образом, при котором процедуры вызывают сами себя.

В прошлых главах этой книги вы могли убедиться, что понятие «алгоритм» появилось намного раньше, чем компьютеры. Изначально этот термин относился к чистой математике и означал исключительно описание последовательности инструкций, необходимых для выполнения арифметических расчетов. Лишь позднее это понятие стали использовать в более широком смысле и связывать с информатикой, столь популярной в наши дни. Языки программирования — это всего лишь следующий этап эволюции форм записи алгоритмов, более формальный и точный (в противном случае они не могли бы быть использованы в компьютерах).

* * *

ТЕРМИН «РЕАЛИЗАЦИЯ»

Реализация — это осуществление или воплощение чего-либо. В информатике этот термин означает запись определенного алгоритма на заданном языке программирования.

ТЕРМИН «ПРОГРАММИРОВАНИЕ»

Слово «программировать» (англ, to program), означающее задание инструкций, которые должен выполнить компьютер, было придумано группой исследователей, работавших над созданием компьютера ENIAC в Институте Мура Пенсильванского университета. В то время использовалось слово «настраивать» (to set up), так как программирование ENIAC (изображен на иллюстрации ниже) осуществлялось с помощью соединений и переключателей, то есть путем изменения электрической схемы самого компьютера. Постепенно, по мере того как разделение между аппаратным и программным обеспечением становилось все более явным, стало применяться слово «программирование».

* * *

Древнейшие алгоритмы, которые позволили вавилонянам провозгласить себя первыми математиками, способными решать достаточно сложные задачи, использовались для решения алгебраических уравнений, записывались в общем виде и демонстрировались на конкретных примерах. В них не использовались итерации или условные конструкции вида «если x < 0, то», так как вавилонянам не был известен нуль. Чтобы выразить несколько возможных вариантов, математики Вавилонии повторяли алгоритм необходимое число раз. Прошло много веков, прежде чем Евклид примерно в 300 году до н. э. описал алгоритм вычисления наибольшего общего делителя двух чисел. Этот алгоритм, который сегодня известен как алгоритм Евклида, как правило, реализуется с помощью рекурсии.

* * *

РЕАЛИЗАЦИЯ АЛГОРИТМА ЕВКЛИДА

Приведем в качестве примера реализацию алгоритма для нахождения наибольшего общего делителя чисел А и В сначала на языке Пролог, затем на языке Java. Сокращение gcd означает great common divisor — наибольший общий делитель.

В реализации на языке Пролог использованы три правила, соответствующие трем возможным случаям. Во всех случаях два первых аргумента являются числами, третий аргумент можно интерпретировать как результат. В первом правиле второй аргумент принят равным нулю. Второе правило применяется тогда, когда первый аргумент больше второго, третье правило — когда второй аргумент больше первого.

gcd (А, 0, А).

gcd (А, В, D)(А > В), (В > 0), R is A mod В, gcd(B, R, D).

gcd (А, В, D)(А < В), (А > 0), R is В mod A, gcd(A, R, D).

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

public static int gcd (int A, int B) {

if (B == 0) {return A;}

else if (A > B) {return gcd(B, A % B);}

else if (A < B) {return gcd(A, В % A);}

return 1;

}

public static int gcdlterative (int A, int B) {

int r = 0;

while (B > 0) {

r = A % B;

A = B;

В = r;

}

return A;

}

* * *

Однако эти алгоритмы представляют собой не элементы общего эволюционного процесса, а отдельные частные случаи. Наиболее известным средством автоматического выполнения задач было программирование ткацких станков Жаккара. В станке Жаккара узор ткани определялся с помощью перфокарт. Эти перфокарты содержали примитивные программы, которые исполнялись станком. Чарльз Бэббидж использовал перфокарты для программирования своей вычислительной машины.

С современной точки зрения эти примитивные программы были написаны на машинном языке, поэтому Ада Лавлейс считается первым в истории программистом. Однако понятие программы, хранящейся в памяти вычислительной машины, появилось значительно позже.

Несмотря на все усилия, предпринятые в 1930-е и 1940-е годы, а также написанные в этот период теоретические работы, в особенности те, что были посвящены лямбда-исчислению и машине Тьюринга, развитие алгоритмов началось лишь с появлением первых компьютеров: «Колосса», Mark I, ENIAC, EDSAC и UNIVAC. Языки программирования, с помощью которых стало возможным написание программ, хранящихся в оперативной памяти, позволили сэкономить время и уйти от взаимодействия с аппаратным обеспечением напрямую — именно так осуществлялось программирование первых компьютеров.

Программы для первых компьютеров писались в восьмеричном коде. Среди первых языков программирования, допускавших представление символов, были Short Order Code (1949) Джона Мокли и Sort-Merge Generator Бетти Холбертон. Short Order Code исполнялся на компьютере BINAC и был интерпретируемым языком.

Процедуры, соответствовавшие символам, хранились в памяти компьютера и вызывались системой. Эту же систему унаследовал UNIVAC. Программа, записанная на этом языке, исполнялась в 50 раз медленнее той же программы, записанной на машинном языке.

Sort-Merge Generator, в свою очередь, был приложением, разработанным для UNIVAC, которое осуществляло слияние и перемешивание карточек с входными и выходными операциями.

Бетти Холбертон (на этой фотографии она изображена за работой на ENIAC), создавшая один из первых языков программирования.

Эти первые системы, автоматического программирования (англ, automatic programming systems) всего лишь предоставляли понятные человеку коды операций и инструкции, записанные в символьном виде либо позволяли извлекать подпрограммы из библиотек и вставлять их в требуемый участок программного кода. Некоторые системы допускали интерпретацию операций для чисел с плавающей запятой и операций индексирования (indexing). Как бы то ни было, за исключением компилятора А-2 и алгебраической системы Лейнинга и Цирлера, до 1954 года даже наиболее мощные системы представляли собой всего лишь синтетические машины с кодом, отличающимся от машинного кода.

Эта модель обладала недостатками не только с технической, но и с экономической точки зрения. Оплата труда программистов вычислительного центра превышала стоимость самого компьютера, и этот разрыв неуклонно возрастал по мере того, как стоимость технологий и соответственно стоимость компьютеров снижалась. Кроме того, на программирование и отладку (debugging) тратилось от 25 до 50 % машинного времени. Системы автоматического программирования снижали быстродействие компьютера в 5—10 раз. Продавцы этих систем в худших традициях рынка стали завышать стоимость. Это привело к тому, что использование этих систем оказывалось невыгодным, и отношение к ним было скептическим.

В середине 1954 года в компании IBM под руководством Джона Бэкуса были начаты работы над языком Фортран (FORTRAN — FORmula TRANslation). Целью работ было решение всех вышеперечисленных проблем. При создании компилятора основное внимание уделялось генерации эффективного объектного кода, и эта задача была успешно решена. Качество объектного кода и преобразования, выполняемых для получения эффективных программ, удивили даже самих создателей языка FORTRAN.

Перфокарта с разметкой колонок для языка программирования Фортран.

С появлением языка Фортран появилась возможность записывать математические процедуры на четко определенном языке. Этот язык обеспечивал новый, более высокий уровень абстракции, поэтому программный код мог исполняться на разных компьютерах. Информация сохранялась в памяти и рассматривалась не как последовательность бит, а как целые или вещественные числа. В языке появились первые базовые конструкции императивных языков: условный оператор (IF <условие> <выражение_1_если_условие__истинно> <выражение_2_если_условие_ложно>) и оператор цикла (DO <инструкция> переменная = начальное значение, конечное значение, шаг).

За Фортраном последовали другие языки: Алгол-60 (одним из его создателей был голландский ученый Эдсгер Дейкстра), Кобол и LISP (предшественник функциональных языков программирования). Эти языки предназначались для решения определенных задач. В отличие от этих языков, язык PL/I был создан как язык общего назначения и содержал все нововведения, представленные в более ранних языках, что сделало его громоздким и сложным.

Компьютер Electrologica XI, работавший в период с 1958 по 1965 год, в котором использовался язык Алгол-60.

Авторы языков программирования ставили перед собой менее амбициозные задачи, но созданные ими языки оказались более эффективными. Среди них выделялись Simula 67 и Pascal. Вместо предопределенного полного множества абстракций эти языки обладали гибкими и удобными средствами определения новых произвольных абстракций. Pascal и Алгол-68 позволяли определять новые типы данных на основе предопределенных простых типов и служебных слов (array, record и других). Эти новые типы можно было рассматривать как абстракции, созданные на основе внутренних представлений, и им сопоставлялось множество операций. Эта модель была гибкой, но обладала существенным недостатком. Доступ к представлению предопределенных типов был закрыт, то есть с предопределенными объектами нельзя было работать напрямую (только с помощью операций), однако доступ к структуре пользовательских типов был открыт, и их значения можно было изменять. Причина заключалась в том, что в языке не было различий между двумя уровнями абстракции: уровнем, на котором программист использует тип данных, и уровнем реализации этого типа. Это осложняло чтение программ и исправление ошибок. Когда программы достигали определенных размеров, эта задача становилась невыполнимой.

Решением проблемы стало использование абстрактных типов данных и языков, в которых они поддерживались (Ada, Modula-2 и CLU). В них проводилось различие между этими уровнями абстракции и применялась так называемая инкапсуляция (ограничение доступа к определенным компонентам объектов). На уровне, на котором программист использовал тип, доступ к его внутренней структуре был закрыт. На уровне реализации определялся интерфейс объекта, его внутренняя структура и доступные операции.

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

Благодаря этим механизмам абстракции программы, написанные на этих языках, стало возможным представлять в терминах объектов. В некоторых языках, например в языке Ада и Modula-2, использование объектов было необязательным, в других — обязательным. В языке CLU программист должен был группировать данные приложения в классы, которые назывались кластерами. Аналогичный принцип использовался в объектно-ориентированных языках, в которых вводилось понятие наследования, позволявшее определять объекты на основе предопределенных объектов.

Объектно-ориентированное программирование — это парадигма программирования, в которой приложения и компьютерные программы понимаются как совокупность объектов и их взаимодействий.

Его появление должно было облегчить создание крупномасштабных программ и помочь в создании искусственного интеллекта. В работах над искусственным интеллектом эта парадигма помогла разработать приемы структурирования знаний путем группировки информации о каком-либо понятии и о его свойствах.

Первым языком, в котором данные и операции группировались в рамках единой сущности, был Simula I, предназначенный для решения задач симуляции. Он был разработан в Норвежском вычислительном центре под руководством математика и политика Кристена Нюгорда. Работы над первой версией языка были завершены в январе 1965 года. Следующая версия получила название Simula 67. Это был язык общего назначения, в котором были формализованы понятия объекта и класса и вводилось понятие наследования. Позднее в языке Smalltalk 80, который был создан на основе языка Simula и двух предыдущих версий (Smalltalk 72 и Smalltalk 76), понятие объекта было обобщено и объекты стали единственными сущностями, используемыми в языке. В начале 1970-х в научно-исследовательском центре Xerox Palo Alto Research Center, известном как Xerox PARC, была создана система Dynabook — персональное средство обработки информации с оконным интерфейсом, текстовыми меню, значками, то есть с полноценным графическим интерфейсом (англ. GUI — Graphical User Interface), очень похожим на современные. Dynabook был разработан американцем Аланом Кеем для обучения детей работе с компьютером. Работы были завершены в 1972 году. Программы в этой системе были написаны на языке BASIC, в них использовался механизм передачи сообщений, а также понятия класса и объекта, введенные в языке Simula.

Алан Кей получает степень почетного доктора испанского Университета Мурсии за вклад в развитие информатики. Торжественная церемония состоялась 28 января 2010 года.

Сейчас существует множество объектно-ориентированных языков программирования (Eiffel, C++ и другие), некоторые из которых являются расширенными и дополненными вариантами других языков. Так, C++ является расширенным вариантом языка С. Он был создан датским программистом Бьёрном Страуструпом и содержит классы, подобно языку Simula. Система CLOS была разработана с целью стандартизировать объектную систему языка Common LISP. Понятия объекта и наследования использовались в работах по созданию искусственного интеллекта при разработке языков для представления знаний, например KRL и KL-ONE, и языков с акторами, в частности Actl, Act2, Act3, ABCL/1 и других.

Абстракция и объекты применяются во всех языках программирования, появившихся в последние годы, как в объектно-ориентированных языках, например Java или Python, так и в процедурных, где используются объектно-ориентированные конструкции, например в языке РНР. Также появились языки, ориентированные на быструю разработку приложений, и сценарные языки. К ним относятся РНР и JavaScript, разработанные в последнее десятилетие XX века. Целью авторов этих языков было упростить и ускорить разработку программ. Разумеется, для небольших программ этого действительно удалось достичь, однако по сравнению с языками прошлого проектирование крупномасштабных программ усложнилось. Как бы то ни было, влияние объектно-ориентированных языков на разработку программ привело к появлению новых вспомогательных средств, например языков моделирования, подобных UML.

Функциональная парадигма

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

Функциональные языки впервые были описаны Джоном Маккарти из MIT (Массачусетского технологического института), создателем термина «искусственный интеллект», в работе, опубликованной в 1960 году в журнале Communications of the ACM. Этот ежемесячный журнал выпускается американской Ассоциацией вычислительной техники (ACM) — обществом, присуждающим премию Тьюринга.

В 1958 году Маккарти изучал использование операций с упорядоченными списками в программе символьного дифференцирования. Дифференцирование — это рекурсивный процесс, поэтому Маккарти использовал рекурсивные функции. Более того, он передавал функции в качестве аргументов другим функциям. Проект по реализации задуманного им языка начался осенью того же года. Результаты были опубликованы спустя два года под названием «Рекурсивные функции над символьными выражениями и их вычисление с помощью машины. Часть I» (часть II никогда не была опубликована). Так появилась первая версия языка LISP (англ. List Processing — «обработка списков») — первого функционального языка, в котором нашло применение множество передовых идей. В описании разработанного им языка Маккарти использовал лямбда-исчисление Алонзо Чёрча.

Джон Маккарти, создатель термина «искусственный интеллект». Стэндфордский университет, 1980 год.

* * *

ЛЯМБДА-ИСЧИСЛЕНИЕ

Эта система была разработана Алонзо Чёрчем и Стивеном Клини в начале 1930-х годов. Ее возможности были эквивалентны возможностям машины Тьюринга, но основной принцип лямбда-исчисления был иным. С формальной точки зрения в лямбда-исчислении используются выражения и правила преобразования выражений, которые моделируют использование функций и вычислений. Рассмотрим в качестве примера определение истинности и ложности:

истина: λху. х

ложь: λху. у.

Логическая функция «И» определяется так:

И: λpq.p q р.

Чтобы найти значение выражения «истина ложь», заменим каждый член этого выражения его эквивалентом с точки зрения лямбда-исчисления:

(λpq.p q р) (λху. х) (λху. у).

Применив правила записи, получим выражение (λху. у), что, как мы уже говорили, эквивалентно значению «ложь». Числа и операции с числами определяются аналогично.

* * *

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

* * *

ПРЕФИКСНАЯ (ПОЛЬСКАЯ) НОТАЦИЯ

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

(а + Ь) — (с·d)

в польской записи будет выглядеть так:

- + ab · cd.

* * *

В середине 1960-х Питер Лэндин создал новый функциональный язык ISWIM (от англ. If You See What I Mean — «если ты видишь, что я имею в виду»), в основе которого находился язык LISP и лямбда-исчисление. На основе языка ISWIM было разработано целое семейство функциональных языков (ML, FP, Miranda и другие).

В то время функциональное программирование было интересно лишь немногим исследователям. Оно начало набирать популярность в 1978 году, когда Джон Бэкус, создатель языка Фортран, опубликовал статью «Можно ли освободить программирование от стиля фон Неймана?» Бэкус критиковал традиционные языки программирования и выступал за развитие новой парадигмы, которую он назвал «функциональное программирование». В ней делался акцент на функционалы (функции, аргументами которых являются другие функции). В своей статье, за которую он был удостоен премии Тьюринга, Бэкус описал язык FP (Functional Programming), в котором не использовались переменные. Статья пробудила интерес исследователей к функциональным языкам и привела к появлению новых подобных языков.

В настоящее время существует два обширных семейства функциональных языков. Первое образовано языками, созданными на основе LISP, второе — языками, созданными на основе ISWIM. К первому семейству принадлежат разновидности языка LISP, например Common LISP, и самостоятельные языки, например Scheme.

Ко второму семейству принадлежит язык Standard ML — результат стандартизации языков ML и Норе, созданных в Эдинбургском университете. ML в отличие от LISP является строго типизированным функциональным языком (strongly-typed language). Это означает, что все выражения в этом языке имеют тип, который определяется системой во время компиляции (статический тип). Кроме этого, программист может вводить новые типы, определяя абстрактные типы данных. Язык ML допускает определение модулей и общих модулей, которые называются функторами. В языке Норе, в отличие от ML, типы требуется определять явно.

* * *

ФУНКЦИОНАЛЬНЫЕ ЯЗЫКИ: ПРИМЕРЫ РЕАЛИЗАЦИИ

Ниже приведены примеры определения функции факториала на разных языках программирования. Обратите внимание на схожесть синтаксиса языков, принадлежащих к двум основным семействам функциональных языков. В языках, подобных USP (Scheme, Норе и ML), используются переменные, определение факториала является рекурсивным и напоминает его определение на языке Java, которое приводилось несколькими страницами ранее. В языке FP, напротив, переменные не используются. В определении на языке FP используется функция iota. Эта функция возвращает список всех натуральных чисел, меньших заданного числа. К этому списку применяется конструкция / *, осуществляющая умножение его элементов. Конструкция /op расширяет бинарную операцию, применяя ее ко всем элементам списка.

Определение на языке LISP:

(defun factorial (n) (if (= n 0) 1 (* n (factorial (- n 1)))))

Определение на языке Scheme:

(define factorial

(lambda (n)

(if (= n0) 1 (*n (factorial (-n 1))))))

Определение на языке Hope:

dec fact: num — > num;

- - - fact 0 < = 1;

- - - fact n < = n*fact(n — 1);

Определение на языке ML

fun f (0: int): int = 1

|f (n: int): int = n * f(n — 1)

Определение на языке FP:

fact =/* op iota

* * *

БЕСКОНЕЧНЫЕ СПИСКИ ЯЗЫКА HASKELL

Следующие определения двух бесконечных списков на языке Haskell помогут вам понять разницу между «жадными» и «ленивыми» вычислениями. Эти определения являются рекурсивными, то есть используют сами себя.

Первое определение соответствует списку натуральных чисел. По индукции предполагается, что список уже определен корректно. Все элементы списка увеличиваются на единицу, таким образом, получается список 2, 3, 4…., к которому добавляется единица. В определении все элементы списка натуральных чисел увеличиваются на единицу с помощью конструкции «mар (+1) naturales».

Второе определение соответствует списку чисел Фибоначчи. Предположим, что этот список уже определен. В определении списка чисел Фибоначчи каждому числу ставится в соответствие следующее число, затем вычисляется сумма в каждой такой паре чисел. В определении «listafibs» ставится в соответствие «хвосту» listafibs, который получается с помощью конструкции «tail listafibs». Далее соответствующие элементы двух списков складываются с помощью конструкции «zipWith (+)».

naturales = 1: map (+1) naturales

listafibs = 0:1: zipWith (+) listafibs (tail listafibs)

Эти определения являются корректными, так как в них используются «ленивые» вычисления. Если бы в них, как в большинстве других языков, использовались «жадные» вычисления, то компьютер обрабатывал бы эти определения бесконечно долго. Обратите внимание, что для определения натуральных чисел сначала требуется выявить бесконечный список, после чего прибавить единицу ко всем его элементам.

* * *

В языках LISP и ML используются «жадные» вычисления (greedy evaluation). Это означает, что все аргументы функции вычисляются перед ее использованием.

Также существуют языки, где применяются «ленивые» вычисления, в частности Haskell, Lazy ML, некоторые версии языка Норе и в особенности язык Miranda, созданный Дэвидом Тернером на основе языков KRC и SASL. В этих языках аргумент оценивается только тогда, когда требуется узнать его значение. Это позволяет создавать программы, которые выполнялись бы бесконечное время, если бы в них использовались «жадные» вычисления.

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

Главная страница сайта, посвященного языку Miranda, который был создан Дэвидом Тёрнером.

Логическая парадигма

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

В императивном и функциональном программировании программа понимается как функция, которая выдает результат на основе заданных входных значений. В императивных языках программа — это последовательность команд, определяющих порядок чтения карточек с входными данными и записывающих выходные данные на других карточках после выполнения необходимых вычислений. В логических языках программы реализуют отношения. С помощью множества правил, называемых дизъюнктами Хорна, программист указывает, какие факты являются истинными, а пользователь может сформировать запрос к программе для оценки истинности некоторого отношения. Вычисления основаны на принципе резолюции Робинсона и заключаются в оценке того, истинно или ложно заданное пользователем отношение, либо в указании случаев, когда это отношение является истинным.

* * *

ДИЗЪЮНКТЫ ХОРНА

Дизъюнкты Хорна — это множество логических правил вида «если антецедент является истинным, то консеквент является истинным». Можно сказать, что дизъюнкты Хорна представляют собой логические операции импликации, содержащие множество предпосылок и единственное следствие.

Предпосылок может быть 0, 1 или более:

а1^а2 ^… ^ aN —> b.

* * *

Самым известным логическим языком является Пролог (PROLOG — от фр. PROgrammation еп LOGique). Он был разработан в 1972 году и является единственным логическим языком, широко используемым на данный момент. Первая версия была разработана под руководством Алана Колмерауэра в университете ЭксМарсель группой, работавшей над созданием искусственного интеллекта, при участии британского логика Роберта Ковальски из Эдинбургского университета. Пролог появился в результате слияния двух направлений исследований. Первое, во главе которого стоял Колмерауэр, не было напрямую связано с информатикой, а было посвящено изучению естественного языка; второе, возглавляемое Ковальски, было сосредоточено на автоматическом доказательстве теорем. На этот язык повлияли В-грамматика (нотация, использованная для описания языка Алгол-68) и язык Planner, разработанный в Стэнфордском университете. Успех Пролога был обусловлен его реализацией усилиями Дэвида Уоррена из группы Ковальски в Эдинбургском университете. Так называемая абстрактная машина Уоррена (VAM) исполняла программы со скоростью, сравнимой со скоростью исполнения программ на языке LISP.

* * *

ОПРЕДЕЛЕНИЕ НА ЯЗЫКЕ ПРОЛОГ

Представим в качестве примера небольшую программу на Прологе, вычисляющую натуральные числа. Для этого определим nat (N) так, что это условие будет выполняться только в том случае, когда N — натуральное. Определение является конструктивным в том смысле, что вычисление натуральных чисел будет производиться только тогда, когда мы будем задавать вопрос, какие значения N удовлетворяют заданному нами условию. Программа выглядит так:

nat(N): — N = 0.

nat (N): — nat(Np), N is Np + 1

В первой строке указано, что ноль является натуральным числом. Вторая строка означает, что если существует натуральное число Np, то Np + 1 также является натуральным. Если говорить более формально, то программа указывает, что N является натуральным, если N равно нулю или если существует такое Np, что N равно Np + 1.

* * *

Формальное описание языков программирования

Описание синтаксиса и семантики первых языков программирования производилось неформальными методами. Научное сообщество приступило к рассмотрению вопросов синтаксиса языков программирования. В 1960 году для описания синтаксиса языка Алгол-60 Джон Бэкус и Петер Наур создали нотацию BNF (форма Бэкуса — Наура), которая оказалась очень полезной при формальном описании синтаксиса языка и в значительной степени способствовала его разработке. Несколько лет спустя была обнаружена существенная схожесть формы Бэкуса — Наура с правилами грамматики, которые в IV веке до н. э. сформулировал Панини для описания классического санскрита.

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

К типу 1 относятся контекстно-зависимые грамматики, к типу 0 — неограниченные грамматики. Каждая следующая обладает большей выразительностью, чем грамматики предыдущих типов. Иерархия Хомского связана с вычислительной мощностью. Вычислительная система общего назначения способна распознавать фразы на любом языке с грамматикой типа 0. К этой категории вычислительных систем относятся машина Тьюринга и лямбда-исчисление. Конечные автоматы являются вычислительными системами типа 3.

Несколько лет спустя швейцарский ученый Никлаус Вирт, лауреат премии Тьюринга и создатель множества языков, описал синтаксис языка Pascal с помощью синтаксических диаграмм и расширенной формы Бэкуса — Наура, EBNF (Extended BNF). Эти нотации не являются более выразительными, чем BNF, однако в настоящее время они широко используются, так как существуют программы, автоматически генерирующие распознаватели синтаксиса по его заданному описанию.

Лингвист Ноам Хомский, создатель иерархии грамматик, носящей его имя.

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

Первой из предложенных была VDL (Vienna Definition Language), созданная в венской лаборатории IBM для формального определения языка PL/I. Она состоит из двух частей: транслятора, выстраивающего абстрактное синтаксическое дерево для программы на языке PL/I, и интерпретатора, который указывает, как следует исполнять или интерпретировать программу, соответствующую этому дереву. Эта семантика называется операционной семантикой и является крайне подробной. Так как язык PL/I очень объемен, беспорядочен и изобилует частными случаями, его формальная спецификация также очень объемна и сложна для понимания. За свои размеры она получила шутливое название VTD — Vienna Telephone Directory («Венский телефонный справочник»). Тем не менее создание этой спецификации стало важным достижением в данной области.

Работы в венской лаборатории были продолжены, и появилась вторая, улучшенная версия спецификации — VDM (англ. Vienna Development Method — венский метод разработки), содержащая несколько особых свойств для создания спецификаций императивных языков. Эта спецификация была создана в 1982 году как объединение точек зрения Динеса Бьёрнера и Клиффа Джонса, которые легли в основу двух школ программирования — датской и английской соответственно. VDM использовался для созданий спецификаций языков Pascal и Алгол-60, а также для подмножества языка Ада’79.

С другой стороны, выдающийся американский ученый Роберт Флойд в 1967 году показал, как можно оценить корректность программы с помощью утверждений (assertions), помещенных в определенные участки программы. Каждое утверждение — это логическая формула, устанавливающая некое отношение между переменными программы. Утверждение остается истинным по завершении программы и устанавливает связь между ее входными и выходными значениями. Метод Флойда улучшил и дополнил британский логик Чарльз Хоар, изложив его в виде набора аксиом и правил вывода, связанных с построением языков программирования, и дав определение аксиоматической семантике. В 1973 году Хоар и Вирт опубликовали аксиоматическую спецификацию подмножества языка Pascal. Во время работы над ней они обнаружили некоторые недостатки в языке и исправили их, создав новую, улучшенную версию Pascal. В следующем году Хоар и Лоуэр изучили возможность одновременного использования аксиоматической и операционной семантики. Эдсгер Дейкстра представил понятие слабейшего предусловия в 1973 году.

Дональд Кнут (слева) и Гэрман Цапф обсуждают свойства новой компьютерной типографики. Стэнфордский университет, Калифорния, 1980 год.

Существуют и другие способы описания семантики языка. В 1968 году силами Дональда Кнута, одного из самых уважаемых специалистов в области вычислительных систем, известного своим чувством юмора, была создана атрибутивная грамматика.

Эта грамматика подробным образом изучается применительно к методам компиляции. Существует и четвертый тип семантики — денотационная, которая была разработана в Оксфордском университете американцами Даной Скоттом и британцем Кристофером Стрэчи в начале 1970-х. В денотационной семантике каждой программе присваивается значение, называемое денотацией (denotation), выраженное в терминах математических объектов. Денотация, как правило, является функцией, сопоставляющей входные и выходные значения программы. Проводились исследования систем для генерации компиляторов на основе денотационной семантики языка, однако на данный момент подобные системы являются крайне неэффективными.

Теория вычислительных систем далека от того момента, когда найдут применение все ранее полученные результаты и будут объединены ранее созданные теории. Напротив, эволюция вычислительных систем продолжается, и она как никогда связана с развитием технологий, дающих нам возможности, о которых раньше нельзя было и мечтать. Языки программирования управляют не только нашими компьютерами, но и телевизорами, мобильными телефонами и даже простейшей бытовой техникой. Мы вновь совершаем первые шаги в новый мир. Как вы увидели, современный облик нашего мира сформировался не случайно, а в результате упорного труда человека. Тем не менее настоящее — лишь эпизод по дороге к непредсказуемому, но, вне всяких сомнений, удивительному будущему.

Библиография

Al-KHWARIZMI, М. IbN Musa, El libro del algebra, Madrid, Nivola, 2009.

BENTLEY, P. J., El libro de las cifras, Barcelona, Paidos, 2008.

BOYER, C., Historia de la matematica, Madrid, Alianza, 1996.

CoELLO, C. A., Breve historia de la computation у sus pioneros, Mexico, Fondo de Cultura Economica, 2003.

Ifrah, G., Historia universal de las cifras, Madrid, Espasa-Calpe, 2002.

SMITH, D. E., History of Mathematics, Nueva York, Dover Publications, obra de 1921 reeditada en 1951.

* * *

Научно-популярное издание

Выходит в свет отдельными томами с 2014 года

Мир математики

Том 15

Бизенц Торра

От абака к цифровой революции. Алгоритмы и вычисления

РОССИЯ

Издатель, учредитель, редакция:

ООО «Де Агостини», Россия

Юридический адрес: 

Россия, 105066, г. Москва, ул. Александра Лукьянова, д. 3, стр. 1

Письма читателей по данному адресу не принимаются.

Генеральный директор: Николаос Скилакис

Главный редактор: Анастасия Жаркова

Выпускающий редактор: Людмила Виноградова

Финансовый директор: Наталия Василенко

Коммерческий директор: Александр Якутов

Менеджер по маркетингу: Михаил Ткачук

Менеджер по продукту: Яна Чухиль

Для заказа пропущенных книг и по всем вопросам, касающимся информации о коллекции, заходите на сайт , по остальным вопросам обращайтесь по телефону бесплатной горячей линии в России:

8-800-200-02-01

Телефон горячей линии для читателей Москвы:

8-495-660-02-02

Адрес для писем читателей: Россия, 105066, г. Москва, а/я 13, «Де Агостини», «Мир математики»

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

Распространение: ООО «Бурда Дистрибьюшен Сервисиз»

УКРАИНА

Издатель и учредитель:

ООО «Де Агостини Паблишинг» Украина

Юридический адрес: 

01032, Украина, г. Киев, ул. Саксаганского, 119

Генеральный директор: Екатерина Клименко

Для заказа пропущенных книг и по всем вопросам, касающимся информации о коллекции, заходите на сайт , по остальным вопросам обращайтесь по телефону бесплатной горячей линии в Украине:

0-800-500-8-40

Адрес для писем читателей: 

Украина, 01033, г. Киев, a/я «Де Агостини», «Мир математики»

Украïна, 01033, м. Кiев, а/с «Де Агостiнi»

БЕЛАРУСЬ

Импортер и дистрибьютор в РБ:

ООО «Росчерк», 220037, г. Минск, ул. Авангардная, 48а, литер 8/к,

тел./факс: +375 17 331 94 27

Телефон «горячей линии» в РБ:

+ 375 17 279-87-87 (пн-пт, 9.00–21.00)

Адрес для писем читателей:

Республика Беларусь, 220040, г. Минск, а/я 224, ООО «Росчерк», «Де Агостини», «Мир математики»

КАЗАХСТАН

Распространение:

ТОО «КГП «Бурда-Алатау Пресс»

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

Отпечатано в соответствии с предоставленными материалами в типографии:

Grafica Veneta S.p.A Via Malcanton 2 35010 Trebaseleghe (PD) Italy

Подписано в печать: 07.12.2013

Дата поступления в продажу на территории

России: 29.04.2014

Формат 70 х 100 / 16. Гарнитура «Academy».

Печать офсетная. Бумага офсетная. Печ. л. 4,5.

Усл. печ. л. 5,832.

Тираж: 200 000 экз.

© Vicenc Тогга, 2010 (текст)

© RBA Collecionables S.A., 2011

© ООО «Де Агостини», 2014

ISBN 978-5-9774-0682-6

ISBN 978-5-9774-0710-6 (т. 15)

Примечания

1

На момент написания книги (2010).

(обратно)

2

Данные на 31.12.2009 года. 19 октября 2011 года Александр Йи и Сигэру Кондо вычислили 10 триллионов знаков после запятой.

(обратно)

Оглавление

Предисловие

Глава 1 Начало эпохи вычислений. Позиционные системы счисления

Глава 2 Средневековая Европа

Глава 3 Первые механические вычислительные машины

Глава 4 Компьютеры в XX веке

Глава 5 Программирование и программы

Библиография Fueled by Johannes Gensfleisch zur Laden zum Gutenberg