Владимир Успенский – Апология математики (сборник статей) (страница 26)

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

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

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

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

Игровыми принадлежностями будут служить пластинки, похожие на костяшки, что используются при игре в домино. Как и костяшка домино, каждая пластинка разделена пополам чертой. В каждой половине что-то написано. Отличие от домино заключается в том, чтó именно написано. В случае домино в каждой из половин точками фиксируется число очков от 0 до 6. В нашем случае в каждой из половин записывается цепочка из букв x и z. Вот примеры таких цепочек. Цепочки длины один: x, z. Цепочки длины два: xx, xz, zx, zz. Цепочки длины три: xxx, xxz, xzx, xzz, zxx, zxz, zzx, zzz. Возможна и цепочка длины ноль, в этом случае не записано ничего. А вот одна из 128 цепочек длины семь: zxzxxxz. Возможный вид пластинок изображён на рис. 1.

Изображённые на рис. 1 четыре пластинки, в том порядке, как они показаны, обозначим – для дальнейших ссылок – буквами A, B, C, D. Если приложить одну пластинку к другой, но не торцами, как при игре в домино, а боками, то в результате получим две строчки букв: одну сверху, другую снизу. Так, прикладывая A к D (слева D, справа A), получаем zzzx сверху и zzx снизу. Если приложить в другом порядке, получим xzzz сверху, zxz снизу. Аналогично можно прикладывать друг к другу несколько пластинок и считывать верхнюю и нижнюю строчки букв. Более того, каждую пластинку разрешается воспроизводить в неограниченном количестве и создавать сочетания из повторяющихся пластинок, такие, например, как AACA. В этом примере верхней строчкой будет xxxzx, а нижней – zxzxzzzx. Прошу у читателя прощение за долгое вступление, но хотелось бы, чтобы всё было предельно ясно.

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

Поясним сказанное на примерах. Пусть объявленный набор содержит всего только одну пластинку A из приведённого выше перечня. Ясно, что решение невозможно, потому что, сколько раз ни прикладывай пластинку A саму к себе, нижняя строка всегда окажется длиннее верхней. По сходной причине решения не существует, если объявленный набор состоит из одной только пластинки D, только тут длиннее будет верхняя строка. Желающие могут попытаться доказать, что решения не существует и в том случае, когда объявленный набор состоит из двух пластинок A и D. А вот если объявить набор из всех наших четырёх пластинок A, B, C и D, то решение существует. Действительно, если сложить пластинки в таком порядке: DBCDA, – то и верхняя, и нижняя строка окажутся одинаковы: zzzxxzzzzx.

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

Глава 7

Парадокс Галилея, эффект Кортасара и понятие количества

Мне áлеф-ноль сияет в вышине, Как лишь песцы сияют голубые, И я ищу спасения от змия В теории Георга, как в вине.

В детстве меня иногда посещал кошмар. Мне представлялось большое число стульев (наглядно – в виде рядов в партере летнего театра). И вот их начинают пересчитывать. Получают некоторое число. Затем пересчитывают в другом порядке и получают другое число. Кошмар заключался в том, что оба числа верны.

Только в университете я узнал, что невозможность описанного составляет предмет особой и притом не слишком просто доказываемой теоремы. А потом прочёл «Записи в блокноте» Хулио Кортасара. Там говорилось о произведённой в 1946-м или 1947 г. операции по учёту пассажиров на одной из линий метро Буэнос-Айреса:

‹…› Было установлено точное количество пассажиров, в течение недели ежедневно пользующихся метро. ‹…› Учёт производился с максимальной строгостью у каждого входа и выхода. ‹…› В среду результаты исследований были неожиданными: из вошедших в метро 113 987 человек на поверхность вышли 113 983. Здравый смысл подсказывал, что в расчётах произошла ошибка, поэтому ответственные за проведение операции объехали все места учёта, выискивая возможные упущения. ‹…› Нет необходимости добавлять, что никто не обнаружил мнимой ошибки, из-за которой предполагались (и одновременно исключались) четверо исчезнувших пассажиров.

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

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