От числа к алгоритму

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

Понятие числа удивляет своей универсальностью. Два плюс два равно четырем вне зависимости от того, складываем ли мы яблоки или секунды, выполняем ли мы сложение на Земле или на Марсе. Сложно представить себе мир, в котором результат сложения менялся бы каждый раз. И даже фантасты, несмотря на все свое воображение, не рискуют описывать подобные миры! Такое постоянство результатов сложения связано, в первую очередь, с тем, что сложение — это умственная операция объединения объектов, не подразумевающая какого-то конкретного физического взаимодействия между ними. Ведь «физическое» сложение далеко не всегда равносильно математическому, и если сложить вместе две половинки критической массы радиоактивного вещества, в ответе получится не просто единица…

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

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

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

Математика пошла дальше по пути абстрагирования не только от реальных объектов, заменяя операции с ними действиями над числами, но и от самих чисел, перейдя к операциям с переменными величинами. Например, мы можем написать равенство A + B = B + A, выполняющееся независимо от конкретных значений A и B. Это свойство самой операции сложения: для деления это равенство уже не будет выполняться. Более сложным примером является вывод решения квадратного уравнения. Работа с переменны-ми величинами, поиск для них общих законов — это удел высшей математики, основное развитие которой приходится на XVII–XVIII века. Числа постепенно исчезают из чистой математики и остаются лишь символы.

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

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

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

1) для любых A, B, С из G верно (A # B) # C = A # (B # C);
2) существует такое E из G, что для любого A из G верно E # A = A # E = A;
3) для любого A из G существует Z из G такое, что A # Z = Z # A = E.

Следует оговориться, что аксиомы 1–3 могут быть записаны вовсе без слов, с использованием нескольких дополнительных символов (символа принадлежности множеству, кванторов существования и всеобщности).

Такое множество будет называться группой (E называется единичным элементом, а Z — обратным к A элементом). Из аксиом можно получить разнообразные следствия. К приме-ру, можно доказать, что обратным элементом к единичному является сам единичный элемент или что если A = B, то A # C = B # C для любого C.

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

Можно согласиться, что аксиоматический подход выглядит весьма полезным, но при чем же здесь компьютеры и искусственный интеллект?.. Дело в том, что в математике в центре внимания всегда была проблема истинности. С помощью рассуждений мы проводим доказательство истинности некоторой теоремы. Но где гарантия, что проводимые людьми рассуждения корректны? И, кроме того, как чело-век придумывает доказательства? «Человеческий фактор» всегда мешал математике достигнуть идеальности. В связи с этим и возникал вопрос: как математически описать само мышление человека?

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

Список наиболее сложных нерешенных проблем был со-ставлен выдающимся математиком Давидом Гильбертом в 1900 году. Некоторые из этих проблем могут показаться на первый взгляд простыми. Например, десятая проблема Гильберта заключалась в разработке метода нахождения решений (или доказательства их отсутствия) для систем диофантовых уравнений. Диофантово уравнение является алгебраическим уравнением, у которого как все коэффициенты, так и все значения неизвестных являются целочисленными. Напри-мер, следующая система диофантовых уравнений: xyz = 105 и x – y = 4 имеет решение x = 7, y = 3, z = 5. Но как разработать метод, «механическое» применение которого будет позволять решать диофантовы уравнения?

В 1928 году была сформулирована «программа Гильберта» по обоснованию математики. Эта программа восходит к рассуждениям Декарта о методах решения математических проблем. Чуть позже (еще в XVII веке) и Лейбниц после создания арифметической машины, аналогичной машине Паскаля, размышлял о возможности построения машины, которая бы, манипулируя символами, «вычисляла» носить математических утверждений. Необходимость обо-снования математики стала особенно важной после того, как в конце XIX века в основах математики (в частности, в теории множеств Кантора) обнаружились противоречия. А как известно из логики, из противоречивых посылок можно вывести произвольные следствия, т. е. многие из полученных ранее математических результатов вполне могли оказаться ошибочными! Аксиоматический подход (наряду с интуиционализмом) стал одним из подходов к устранению подобной опасности. Программа Гильберта по доказательству непротиворечивости классической математики подразумевала ее полную формализацию через построение системы аксиом и правил вывода, с помощью которых можно было бы получить все основные математические теоремы. При этом доказательства должны были состоять из таких элементарных шагов, корректность которых проверялась непосредственно. Это привело к формализации понятия алгоритма.

Само слово «алгоритм» возникло гораздо раньше. Оно происходит от Algorithmi — латинского написания имени арабского математика аль-Хорезми. В первой половине IX века появился его трактат с описанием разработанной в Индии десятичной системы счисления. Благодаря переводу этого трактата в XII веке на латинский язык средневековая Европа познакомилась с позиционной системой счисления, поэтому долгое время алгоритмом называлось искусство счета в этой системе. Интересно, что от арабского названия этой книги также происходит слово «алгебра».

Вычисления в позиционной системе счисления описывались гораздо более простыми и единообразными правилами, которые могли быть легко использованы (попробуйте, к при-меру, произвести элементарные арифметические операции в непозиционной римской записи: XIX + VI или XII – IV, — без их перевода в десятичную систему). Именно благодаря этому свойству вычисления могли быть воплощены в машинах Паскаля, являвшихся аппаратной реализацией соответствующих алгоритмов.

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

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

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

Любые ли алгоритмы имеют формальные описания? Для любой ли задачи существует алгоритм ее решения? Какой архитектурой должно обладать гипотетическое устройство, выполняющее некоторый алгоритм?