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