Новый Мир ( № 11 2007)

Ученица. Очень просто. Поскольку я не могу положиться на свое арифметическое мышление, я взяла и выучила наизусть все результаты умно­жения, какие только возможны».

Всех результатов умножения бесконечно много, так что выучить их наизусть невозможно. Да и не нужно: Ионеско справедливо утверждает, что «математика — заклятый враг зубрёжки». (Кстати, теоретическая невозможность выучить все результаты получила в приведённом диалоге и экспериментальное подтверждение. Дело в том, что Ученица дала неправильный ответ: правильным ответом является число 19 389 602 947 179 164 508, а ею названо число 19 390 002 844 219 164 508. Не берусь судить, получил ли этот факт должное отражение в ионесковедении.)

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

На примере с умножением можно получить представление о понятии массовая задача . Массовая задача образуется путём совместного рассмотрения серии однотипных единичных задач. В случае умножения каждая единичная задача состоит в указании пары конкретных чисел (как, например, тех, которые были названы Ученице Учителем) и требовании найти их произведение. Это произведение является решением предложенной единичной задачи. Массовая же задача состоит здесь в требовании найти некий метод, позволяюший найти произведение для каждой отдельной пары чисел. Другой простой пример. Задача решить квадратное уравнение x 2 - 13 x + 30 = 0 — это единичная задача, и её решением служит пара чисел 3 и 10. А вот изучаемая в средней школе задача о решении произвольного квадратного уравнения — это массовая задача, и её решением служит всем известная (или долженствующая быть всем известной) формула, дающая решение для любого конкретного квадратного уравнения. Остановим свой взгляд на какой-нибудь массовой задаче и посмотрим, чем отличаются друг от друга составляющие её единичные задачи. Мы видим, что они отличаются своими исходными данными . Для каждой единичной задачи умножения исходным данным служит конкретная пара чисел. А для каждой единичной задачи на решение квадратного уравнения исходное данное — это конкретное квадратное уравнение.

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

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

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

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

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

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