Апология математики, или О математике как части духовной культуры (Успенский) - страница 27

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

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

Средствами игры будут служить пластинки, наподобие тех доминошек, что используются при игре в домино. Как и в домино, каждая пластинка разделена на верхнюю и нижнюю половину. В каждой половине что-то написано. Отличие от домино в том, что именно написано. В случае домино в каждой из половин записывается количество очков, от 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. Прошу у читателя прощение за затянувшееся предварение к игре, но хотелось бы, чтобы всё было предельно ясно.

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