Читать «Том 33. Разум, машины и математика. Искусственный интеллект и его задачи» онлайн - страница 65

Два основных компонента машины Тьюринга — бумажная лента и устройство чтения-записи.

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

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

Некоторые из бесконечного множества возможных конфигураций клеточного автомата порождают повторяющиеся узоры, как, например, в игре «Жизнь» Конвея.

Читатель найдет в интернете множество фигур, порождающих прекрасные рисунки, которые затем уничтожаются и создаются вновь, причем все подобные фигуры описываются очень простыми правилами.

Паровая машина Тьюринга. Рисунок, сделанный студентами Вашингтонского университета в одной из аудиторий.

* * *

КЛЕТОЧНЫЙ АВТОМАТ ДЖОНА КОНВЕЯ, ИЛИ ИГРА «ЖИЗНЬ»

Игра «Жизнь», придуманная Джоном Хортоном Конвеем (род. 1937), представляет собой клеточный автомат, который, несмотря на простоту, демонстрирует удивительное поведение. Правил, описывающих его работу, всего два. В них учитываются восемь клеток, смежных с каждой, а также состояние самой клетки, в которой расположен клеточный автомат.

Правило № 1: если у белой клетки три соседние с ней клетки имеют черный цвет, то эта клетка также окрашивается в черный цвет. В противном случае клетка остается белой.

Правило № 2: если клетка окрашена в черный, а две или три соседние с ней клетки также черного цвета, то клетка не меняет цвет. В противном случае она становится белой.

Если читатель знаком с основами программирования, мы советуем ему реализовать эти простые правила в программе, чтобы посмотреть на игру «Жизнь» в действии. Для всех остальных далее приведено несколько примеров.

Это одна из конфигураций, возникающих при программировании правил игры «Жизнь», известная как «планер». Она порождает следующую циклическую последовательность.

Как показано на иллюстрации, фигура t + 4 идентична фигуре t, но смещена на одну клетку вниз и вправо. Следовательно, в момент времени t + 9 «планер» (именно так называется фигура, изображенная на рисунке) вновь сместится вдоль диагонали, отмеченной на иллюстрации ниже.