Несколько лет назад группа математиков и специалистов вычислительной науки (включая и редакторов этих трудов) задумалась о том, чтобы предпринять своего рода научное паломничество к местам рождения аль-Хорезми, выдающегося математика IX в., чье имя воплотилось в слове "алгоритм". Как видно из его имени, аль-Хорезми происходил из Хорезмского оазиса, исторического центра цивилизации, давшего миру целое созвездие замечательных философов, ученых и поэтов. Мы теперь знаем, что не только знаменитые труды аль-Хорезми постепенно привели к нашему слову "алгоритм", но что и слово "алгебра" также восходит к названию одной из его главных работ; таким образом, с личностью аль-Хорезми неразрывно связаны алгоритм и алгебра - два понятия, принадлежащие к кругу наиболее важных концепций всей математики и ее приложений. Естественно, нам показалось, что посещение этих мест станет уникальным предприятием для любого математика, кто бы он ни был: теоретик или прикладник, специалист по философским вопросам и обоснованиям или практик, атакующий актуальные сегодняшние задачи.
После обсуждения этой идеи с более широким кругом ученых, а также консультаций с Академиями наук СССР и Узбекской ССР наши мечты воплотились в реальность. В городе Ургенче, современном центре Ургенчской области Узбекистана, с 16 по 22 сентября 1979 г. состоялся международный симпозиум на тему "Алгоритмы в современной математике и ее приложениях". Симпозиум был организован Академией наук Узбекской ССР при поддержке Академии наук СССР и ее Сибирского отделения.
В желании сделать такое паломничество продуктивным мы обратились при подготовке симпозиума к потенциальным участникам со следующим письмом:
"Нам кажется, что тем самым появляется великолепная возможность для поистине уникальной, плодотворной и незабываемой конференции. Вместо просто еще одного "обычного" симпозиума с представленными и зачитанными докладами мы хотели бы сосредоточиться на взаимной дискуссии по наиболее фундаментальным проблемам математики и вычислительной науки. Мы убеждены, что следы истории и дыхание пустыни, окружающей место проведения конференции, будут сильно способствовать тому, чтобы отвлечь нас от повседневной работы, заполняющей нашу жизнь дома, придадут зоркость нашему взгляду на природу вещей, вдохновят на более глубокие и философские размышления. Тем не менее, мы не думаем, что симпозиум приведет к успеху, если люди приедут полностью неподготовленные, полагаясь только на спонтанные дискуссии; определенная предварительная подготовка поможет нам и работать и учиться лучше в период нашего совместного пребывания. Присутствующие, без сомнения, будут принадлежать разным дисциплинам, характерным каждая своим стилем мышления, и мы со всей определенностью не предполагаем достичь какого-то унифицирующего консенсуса мнений о внутренней природе алгоритмов, хотя и надеемся накопить опыт, способствующий дальнейшему прогрессу".
Сейчас мы можем с полным удовлетворением заявить, что наши большие ожидания были полностью оправданы и превзойдены всем случившимся во время этой незабываемой недели.
При подготовке симпозиума был заблаговременно разослан предварительный перечень вопросов, представляющих, как нам казалось, общий интерес и обсуждение которых могло бы помочь в достижении взаимопонимания.
"1. Существует ли фундаментальная разница между "алгебраическим" и "алгоритмическим" методами в математике?
2. Каков наилучший способ обмена алгоритмами между людьми?
3. Как поступать при необходимости разрешения конкретного варианта алгоритмически неразрешимой массовой проблемы?
4. Как правильно построить программу, содержащую, скажем, более миллиона команд?
5. Как выразить оригинальные труды аль-Хорезми в современной нотации?
6. Какого типа неалгоритмические языки желательны для программирования?
7. Существуют ли, какие и где специальные разделы знания, наилучшим образом представляемые в виде алгоритмов?"
Конечно, эти вопросы сами по себе были призваны лишь обозначить обшую направленность провоцируемой нами дискуссии, нежели очертить и ограничить ее рамки.
Некоторые из потенциальных участников в переписке выдвинули свои вопросы и тезисы, которые помогли составить предмет нашего собрания. Вот некоторые из них.
"Можно ли сформулировать подходящее обобщение тезиса Чёрча, которое позволило бы охватить вычислимость в произвольных областях и, в частности, вычислимость с помощью вероятностных и недетерминистских устройств? (Д.Скордев)
Ваша идея проведения симпоэиуда в Хорезмской области очень хороша. Слишком многие исследователи работают над проблемами только потому, что кто-то другой назвал эту проблему интересной. В результате получается большое количество компетентных работ, ведущих в никуда. Мы очень нуждаемся в размышлениях по поводу того, почему конкретная задача так важна и к чему приведет успех в ее решении... К перечню тем я бы добавил вопрос о математической нотации. Я часто с удивлением размышлял, почему естественные проблемы так часто оказываются полными. Казалось бы, что априорная вероятность для задачи оказаться полной должна бы быть исчезающе мала. Что-то должно быть в природе нашей нотации, что толкает нас рассматривать только подходящие проблемы. (Дж. Хопкрофт)
Что собой представляют алгоритмы над вещественными числами? (Н.Н.Непейвода)
Мне интересны различные связи концепции алгоритма с другими математическими понятиями: алгоритмы и перечислимые множества, алгоритмы в логике, алгоритмы и автоматы и другие процессы, алгоритмы и проблемы высокой степени сложности, относительная вычислимость. (Г.С.Цейтин)
Я особенно интересуюсь тем, как построить алгоритм. (Э.Х.Тыугу)
Существует позиция, с которой "алгоритмические" и "алгебраические" подходы выглядят почти одинаково. Может быть, реальная альтернатива - это "алгоритмический" и "теоретико-множественный"? Может ли понятие алгоритма быть выраженным в терминах других стандартных (скажем, теоретико-множественных) математических понятий или оно по существу независимо и первично? (Б.А.Успенский)
Каков должен быть хороший курс алгоритмов и логики, читаемый на факультете прикладной математики? Разумно ли искать инвариантные характериэации вычислимых санкций, алгоритмов и вычислительных процессов? (А.П.Ершов)"
Конечно, существовала необходимость ограничить размеры симпозиума сравнительно небольшим числом делегатов, для того чтобы обеспечить продуктивность дискуссий, но в конце мы заметили, что прошедшие дискуссии и выступления могли бы оказаться ценными и стимулирующими для существенно более широкого круга людей, нежели только участников. Поэтому большая часть программы работы симпозиума получила позднее оформление в виде написанных материалов, которые и предлагаются теперь вниманию читателя. Английский вариант трудов был опубликован в 1981 г. издательством Шпрингер-Ферлаг (Lecture Notes in Computer Science, vol.122).
Участники симпозиума глубоко признательны узбекским хозяевам, которые проявили непревзойденное гостеприимство, сделавшее наше пребывание на конференции незабываемым праздником. Наши особые благодарности С.Х.Сираждинову - вице-президенту АН УзССР и председателю оргкомитета, Р.И.Ишчанову - председателю исполкома Совета народных депутатов Хорезмской области, В.К.Кабулову - директору Института кибернетики АН УзССР и сопредседателю оргкомитета, К.Ш.Бабамурадову - заведующему отделом Института кибернетики и заместителю председателя оргкомитета.
Мы также полны благодарности ко многим замечательным людям, встретившим нас в городе и за его пределами с радушием, тепло которого навсегда осталось с нами. Эти встречи происходили во время поездок и экскурсий, позволивших нам посетить не только исторические места, но и современные школы, колхозы и предприятия. На нас произвел глубокое впечатление интерес, проявленный жителями Хорезма к работе симпозиума, освещавшейся в газетах и по телевидению. К нашему приезду была приурочена специальная церемония закладки памятника аль-Хорезми в центре Ургенча. Нам было очень радостно видеть, что традиция аль-Хорезми живет в его родных местах.
А.П. Ершов и Д.Е. Кнут