Занимательный компьютер |
"В МИРЕ НАУКИ" 1990/#03 |
Электронные схемы и ковровые узоры в клеточной вселенной
А. К. ДЬЮДНИ
"Шахматная доска -- это мир, фигуры -- его явления, а правила игры -- то, что
мы называем законами Природы".
Томас Хенри Хаксли, "Свободное образование"
Как и шахматная доска, клеточный автомат тоже может представлять целый мир. На
его решетке из квадратных клеток может разместиться значительно больше фигур,
чем на шахматной доске, а количество возможных правил исчисляется у него
мириадами. Мало того, цвета его клеток не ограничиваются черным и белым, они
могут быть окрашены в люьой цвет радуги. Что такое клеточный автомат? В свете
рассматриваемых в настоящей статье примеров -- это бесконечная двумерная
поверхность, заполненная квадратиками, набор возможных состояний и часовой
механизм. Каждая клетка всегда находится в том или ином допустимом состоянии. На
каждом такте часового механизма каждая клетка меняет свое состояние в
соответствии с определенными правилами, которые учитывают состояния соседних
клеток.
Недавно мое внимание привлекли две программы, генерирующие клеточные
автоматы: PHANTOM FISH TANK и RUDY RUCKER'S CA LAB (соответственно "Волшебный
аквариум" и "Лаборатория КА Руди Ракера"). Люди, не обладающие навыками
программирования, теперь могут заняться исследованием уже известных клеточных
автоматов или создавать свои собственные.
... мне больше всего понравился клеточный автомат, с помощью которого можно
создать простой компьютер, работающий в двумерном клеточном пространстве. Я
назвал его миром электронных схем.
При помощи системы экранного редактирования, встроенной в программу
PHANTOM FISH TANK, можно сконструировать и испытать в действии электронные схемы
из клеточных "проводников" и "логических вентелей". Теоретически из этих
клеточных устройств можно собрать компьютер сколь угодно большой мощности. На
практике масштабы такого компьютера ограничиваются лишь несколькими вентилями и
проводниками.
Однако этих нескольких устройств уже более чем достаточно, чтобы произвести
впечатление на любого экспериментатора, увлеченного безграничными возможностями
мира электронных схем. Строительными кирпичиками этого мира являются квадратные
клетки автомата. В каждый данный момент времени клетка может находиться в одном
их четырех разрешенных состояний. Вместо номеров эти состояния имеют названия:
фон, проводник, хвост электрона и голова электрона. Пара прилегающих друг к
другу клеток, голова электрона и хвост электрона, образуют объект, называемый
электроном.
Конечно, не так уж важно, как назвать ту или иную клетку, однако эти названия
приобретают определенный смысл, когда мы обращаемся к правилам. На каждом такте
игры клетка головы электрона становится клеткой хвоста электрона, клетка хвоста
электрона становится клеткой проводника и иногда клетка проводника становится
клеткой головы электрона; клетки фона никогда не изменяют своего состояния.
Каждая клетка изменяет свое состояние в зависимости от состояния своих соседей
-- восьми клеток, касающихся ее по четырем сторонам квадрата и в угловых точках.
Клетки проводника, в окрестности которых находятся одна или две клетки головы
электрона, становятся сами клетками головы электрона, однако клетки, окрестность
которых содержит три или более клеток головы электрона, остаются клетками
проводника.
Вот с таким простым набором правил мир электронных схем готов к работе.
Случайное исходное распределение клеток проводника и электронов, вероятнее
всего, приведет лишь к короткому замыканию. Для того чтобы клетки могли что-то
вычислять, играющий сначала должен сконструировать из клеток проводника и фона
логические устройства. Затем он может испытать свои устройства, вводя электроны
в проводники, которые так непохожи на настоящие проводники в реальных
электронных устройствах. Построить клеточный компьютер -- это лишь половина
удовольствия; интересно наблюдать за тем, как он работает.
Чтобы создать проводник в клеточном пространстве, достаточно расположить
несколько клеток проводника в одну линию и окружить их клетками фона. Чтобы
ввести электрон в проводник, нужно заменить его первую клетку хвостом электрона,
а вторую -- головой электрона. Электрон начнет плавно перемещаться вдоль
проводника вследствие принятых в клеточном пространстве правил: на каждом такте
часового механизма клетка проводника, расположенная перед электроном,
превращается в голову электрона, а голова электрона превращается в его хвост,
хвост же превращается в клетку проводника.
...
Силвермен с энтузиазмом относится к вычислительным возможностям клеточных
автоматов. Он уже представляет себе компьютер, который не только способен
работать на основе клетчных логических схем, подобных описанным выше, но может
еще и модифицировать схемы по ходу работы, чтобы каким-то образом оптимизировать
процесс вычисления, выполняемого в данный момент.
Руди Ракер предвидет еще более широкие горизонты, которые откроются перед
клеточными автоматами в будующем. "Мне кажется, что величайшая научная задача
конца XX в. заключается в создании живых машин ... Они будут таким же высочайшем
достижением ученых в области кибернетики ... каким явилось создание собора
Парижской богоматери средневековыми мастерами".
...
Один из клеточных автоматов, к которому Ракер питает особую симпатию,
называется "Коврик". Он создает цветные орнаменты в виде овальных форм и
эллиптических полосок. Эти орнаменты чем-то напоминают рисунок настенных
ковриков, которые когда-то ткали наши предки в графстве Ланкастер (шт.
Пенсильвания); однако коврики клеточного автомата "живые" -- волны различного
цвета то наступают, то отступают, и орнамент постоянно меняется. Каким образом
создается коврик Ракера?
В этом клеточном автомате каждая клетка имеет восемь соседних -- четыре по
сторонам квадрата и четыре по углам. В процессе, состоящем из четырех шагов,
каждая клетка решает, в каком из 256 возможных состояний она войдет в следующий
цикл. Сначала вычисляется средняя величина по состояниям восьми соседних клеток.
На втором шаге полученная средняя величина округляется до целого значения,
дробная часть отбрасывается. На третьем шаге к этому числу прибавляется
определенное приращение (выбираемое пользователем). И наконец, на четвертом шаге
результирующая сумма маскируется другим числом, также задаваемым пользователем.
"Маскирование" означает, что каждый бит представления нового состояния клетки
логически комбинируется с битом двоичного представления числа, задаваемого
пользователем. ... Даже такое маленькое приращение, как 1, приводит к
возникновению узоров, проявляющих тенденцию либо к росту, либо к сжатию, тем
самым коврики как бы "оживают".