Апология математики (сборник статей)

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

Другой простой пример. Требуется решить квадратное уравнение x2 − 13x + 30 = 0. Это единичная задача, и её решением служит пара чисел 3 и 10. А вот изучаемая в средней школе задача решения произвольного квадратного уравнения является массовой, и её решением служит всем известная (по крайней мере она должна быть всем известна) формула, дающая решение для любого конкретного квадратного уравнения.

Остановим свой взгляд на какой-нибудь массовой задаче и посмотрим, чем различаются составляющие её единичные задачи. Мы видим, что они различаются своими исходными данными. Для каждой единичной задачи умножения исходным данным служит конкретная пара чисел. А для каждой единичной задачи на решение квадратного уравнения исходное данное – это конкретное квадратное уравнение. Решением же массовой задачи является общий метод, дающий решение для каждой из составляющих её единичных задач. Если предложенный общий метод состоит в последовательности строго детерминированных операций, ведущих от исходных данных к результату, он называется конструктивным, или эффективным, или алгоритмическим, или, ещё короче, алгоритмом. Таким образом, можно говорить об алгоритме сложения столбиком, об алгоритме умножения столбиком, об алгоритме решения квадратных уравнений и т. п. Алгоритмы играют в математике – да и во всей нашей жизни – большую роль, особенно в связи с развитием компьютерной технологии.

Само слово «алгоритм» достаточно интересно: это, возможно, единственный математический термин, произошедший от географического названия – Хорезм. Это название носили историческая область и древнее государство в Средней Азии в низовьях реки Амударьи. В конце VIII – первой половине IX в. здесь жил замечательный ученый Мухаммед бен Муса аль-Хорезми (аль-Хорезми буквально означает «из Хорезма»). Он предложил некоторые методы решения арифметических задач, и на его авторитет ссылались средневековые европейские авторы, писавшие, как это было принято, на латыни. Начиная с XII в. его имя транслитерировалось как Algoritmi. Отсюда и пошёл термин «алгоритм». Поиски общего метода для решения массовой задачи велись со времён Античности. Однако впервые ясное понимание алгоритма в качестве самостоятельной сущности встречается лишь в 1912 г. в трудах великого французского математика Эмиля Бореля.

Понятие алгоритма – одно из центральных в математике. Программа для компьютера есть не что иное, как запись алгоритма на одном из так называемых языков программирования. Прорыв в осмыслении этого важнейшего понятия произошёл в 1936 г., когда независимо друг от друга Алонзо Чёрч в Америке и Алан Тьюринг в Великобритании предложили математические уточнения понятия алгоритма (каждый своё) и на основе этих уточнений предъявили первые примеры массовых проблем, неразрешимых алгоритмически, в числе которых оказалась и очень знаменитая, стоявшая с 1915 г. так называемая проблема разрешения (das Entscheidungsproblem), считавшаяся главной в математической логике. Поясним, что термины «проблема» и «задача» для нас синонимы и что массовая проблема считается алгоритмически неразрешимой, если не существует решающего её алгоритма, т. е. такого единого алгоритма, который позволял бы находить решение для каждой из тех единичных проблем, которые и составляют рассматриваемую массовую проблему.

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

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