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

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

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

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

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

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

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

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

(Окончание следует.)

Собиратель

Десятников Владимир Александрович — художник, искусствовед. Родился в 1931 году; ветеран Великой Отечественной войны. В 1965 году окончил искусствоведческое отделение исторического факультета МГУ. Заслуженный деятель искусств; автор ряда книг и альбомов, посвященных русскому искусству; вице-президент Международной славянской академии. В “Новом мире” выступил с очерком, посвященным знаменитому архитектору-реставратору П. Д. Барановскому (2006, № 12).

Феликс Евгеньевич Вишневский не любил, когда его называли коллекционером. Он считал себя собирателем: живопись и скульптура, гравюры и акварели, фарфор и фаянс, мебель и часы, шитье бисером и жемчугом — все привлекало его внимание. Знатоком почерков художников, стилей и самих материалов — “вещевиком”, как говорят музейные работники, он был редкостным. К нему не раз обращались музеи страны. Авторитет у него был высочайший. Ко всему прочему, Феликс Евгеньевич был мастером на все руки. Он мог починить старинные часы с боем, собрать из бронзового лома стильную люстру пушкинского времени, переплести книгу, но все-таки мастерство его как реставратора мебели заслуживает особых похвал. Здесь ему мало найдется равных. Он любил, ценил и знал особенности всех видов работ с применением разных пород дерева. Отреставрированная им мебель, украшенная мозаикой из дерева — интарсией и маркетри, вызывает восхищение посетителей в музеях-усадьбах Останкино и Кусково, в краеведческих музеях Серпухова и Дмитрова.

Из тех денег, что зарабатывал Феликс Евгеньевич, на себя он тратил минимум. Все было отдано “одной, но пламенной страсти”. Итогом собирательства Ф. Е. Вишневского явилось создание Музея В. А. Тропинина и московских художников его времени, который он подарил в 1969 году родному городу — Москве. На это ушла вся жизнь без остатка.

Мое знакомство с Ф. Е. Вишневским произошло еще в студенческие годы в залах Третьяковской галереи. Я в ту пору писал курсовую работу на тему “Портрет неизвестного. Скульптура К. Б. Растрелли”. Однажды, придя в Третьяковку пораньше, чтобы не мешать посетителям, я скрупулезно перерисовывал в тетрадь дворянский герб с постамента скульптуры. Недалеко от меня пожилой лысый мужчина, как я понял — реставратор, изучал в крупную лупу трещины красочного слоя — кракелюры — на портретах первой половины XVIII века — времени, к которому относится и скульптурный портрет работы К. Б. Растрелли. Мимо проходила старейшая сотрудница галереи С. И. Битюцкая. Мужчина почтительно поздоровался и показал ей какую-то фотографию.

— Помилуйте,— сказала Софья Иннокентьевна,— разве здесь можно что-либо разобрать? Надо бы сделать с вашей “печной заслонки” рентгенограмму.

— Портрет пока не у меня,— заметно гундося, ответил мужчина. И добавил, как-то смешно пришлепывая губами: — Игра вроде бы стоит свеч.

— Рискните, ведь чутье вас, Феликс Евгеньевич, никогда не обманывало. — И Битюцкая раскланялась.

Улучив момент, я представился моему соседу и попросил у него лупу, чтобы повнимательней рассмотреть герб на постаменте скульптуры. Мне показалось, что гравированный рисунок герба сделан неумелой рукой и разительно отличается от самого мастерски исполненного портрета.

— Этот герб пробовали расшифровать многие, — сказал Феликс Евгеньевич. — Впрочем, быть может, вы будете более удачливы.

Я рассказал о скромной задаче своего исследования. Среди искусствоведов, добавил я, существует мнение, что это портрет петровского сподвижника — генерал-фельдмаршала, сенатора Якова Брюса.

— Думаю, что эта версия не имеет достаточных оснований,— заметил Феликс Евгеньевич. — Графство Брюсу было пожаловано в 1721 году. Его герб представляет собой щит с Андреевским крестом, который вписан в центр другого щита, разделенного на четыре части. Как видите, герб на постаменте скульптуры другой. К тому же в гербе Брюса вместо перьев на шлеме изображено, как сказано в описании герба, “плечо вооруженное”.

Я был поражен памятью и эрудицией Феликса Евгеньевича. Он тут же продиктовал мне список трудов по русской геральдике В. К. Лукомского и рекомендовал внимательно изучить “Подробный словарь русских гравированных портретов” Д. А. Ровинского в четырех томах, вышедший в 1887 году.

— Портрет этого вельможи работы К. Б. Растрелли,— продолжал Вишневский,— ранее был в галерее О. И. и Л. Л. Зубаловых. В 1924 году он поступил в Государственный музей изобразительных искусств имени А. С. Пушкина, а оттуда — в Третьяковскую галерею. В 1939 году портрет экспонировался на ретроспективной выставке в Государственном Эрмитаже. Я творчеством Растрелли специально не занимался, — закончил Вишневский. — Если у меня появятся какие-то новые данные, непременно поставлю вас в известность.