Паровая машина Тьюринга. Рисунок, сделанный студентами Вашингтонского университета в одной из аудиторий.
* * *
КЛЕТОЧНЫЙ АВТОМАТ ДЖОНА КОНВЕЯ, ИЛИ ИГРА «ЖИЗНЬ»
Игра «Жизнь», придуманная Джоном Хортоном Конвеем (род. 1937), представляет собой клеточный автомат, который, несмотря на простоту, демонстрирует удивительное поведение. Правил, описывающих его работу, всего два. В них учитываются восемь клеток, смежных с каждой, а также состояние самой клетки, в которой расположен клеточный автомат.
Правило № 1: если у белой клетки три соседние с ней клетки имеют черный цвет, то эта клетка также окрашивается в черный цвет. В противном случае клетка остается белой.
Правило № 2: если клетка окрашена в черный, а две или три соседние с ней клетки также черного цвета, то клетка не меняет цвет. В противном случае она становится белой.
Если читатель знаком с основами программирования, мы советуем ему реализовать эти простые правила в программе, чтобы посмотреть на игру «Жизнь» в действии. Для всех остальных далее приведено несколько примеров.
Это одна из конфигураций, возникающих при программировании правил игры «Жизнь», известная как «планер». Она порождает следующую циклическую последовательность.
Как показано на иллюстрации, фигура t + 4 идентична фигуре t, но смещена на одну клетку вниз и вправо. Следовательно, в момент времени t + 9 «планер» (именно так называется фигура, изображенная на рисунке) вновь сместится вдоль диагонали, отмеченной на иллюстрации ниже.
Более сложная версия «планера». Если бы изображение было анимированным, вы смогли бы увидеть, что рисунки, расположенные под стрелкой, смещаются вдоль линии, отмеченной на иллюстрации.
Имитация разумного поведения природы всегда была источником вдохновения для инженеров, занимающихся искусственным интеллектом. В свое время природа подсказала человеку идею нейронных сетей и эволюционных алгоритмов, которые сыграли важнейшую роль в развитии искусственного интеллекта. О них мы уже рассказывали в прошлых главах. Аналогично возникли и другие модели, в частности искусственные иммунные системы, в которых предпринята попытка сымитировать поведение иммунной системы живых существ, или роевой интеллект — попытка смоделировать отдельное и простое поведение членов колонии (например, пчелиного роя), в совокупности демонстрирующих определенное поведение, которое можно назвать интеллектуальными.
Иммунная система животного представляет собой крайне эффективную систему распознавания образов и оптимизации. Для каждой новой задачи, которую необходимо решить (то есть для нового антигена, попадающего в тело), путем упорядоченного процесса проб и ошибок иммунная система быстро находит решение — антитело, способное распознать антиген.
Действие иммунной системы напоминает эволюционный процесс с одним отличием: при работе иммунной системы не происходит скрещивания различных решений с целью выявления среднего решения, сочетающего в себе достоинства родительских. Действие иммунной системы можно представить следующим образом.
1. Случайным образом генерируется обширное множество антител.
2. Оценивается пригодность каждого антитела, или его способность распознать антиген, попавший в организм.
3. На основе антител первого поколения по следующей схеме создается второе поколение.
1) Генерируется множество копий антител. Число копий каждого антитела пропорционально его пригодности. Иными словами, новое поколение будет содержать много копий очень эффективных антител, а неэффективные антитела будут присутствовать лишь в нескольких копиях или вовсе не попадут в следующее поколение.
2) В копии антител вносятся изменения (мутации, если использовать терминологию эволюционных алгоритмов) обратно пропорционально их эффективности. Иными словами, копии эффективных антител в новом поколении почти не изменятся, а копии неэффективных антител претерпят серьезные изменения.
4. Для новых антител, полученных на предыдущих этапах, вновь оценивается способность распознавать искомый антиген, после чего весь процесс повторяется, и создается новое поколение антител.
5. Когда биологическая система считает, что эффективное антитело для борьбы с антигеном найдено, процесс останавливается.