Всем наверняка доводилось видеть сложнейшие лабиринты муравейника или геометрически правильные пчелиные соты. Однако некоторые искусственные создания с очень простым «мозгом» способны создавать удивительно сложные и причудливые узоры. Здесь мы рассмотрим такие существа, которые назовем «тьюрмитами«. Название их происходит от скрещивания двух слов — Тьюринг и термит. Машина Тьюринга — это воображаемая машина, которая оперирует на бесконечной ленте, разбитой на ячейки, и состоит из считывающего/записывающего устройства и устройства для перемещения ленты на один шаг вперед или назад. Считывающее/записывающее устройство служит для считывания из ячейки ленты или записи в ячейку ленты символа. Машины Тьюринга были названы в честь математика Алана Тьюринга, который изобрел их. По существу такая машина — это фундаментальная цифровая вычислительная машина. Она может решить любую задачу, доступную современному компьютеру, если ей предоставить необходимое время. Как работает такая машина? Машина Тьюринга может находится в нескольких состояниях. Сначала она считывает символ из текущей ячейки ленты. Затем она обращается к внутренней таблице и определяет символ, который нужно будет записать на ленту в зависимости от текущего состояния и считанного символа. После она записывает указанный символ на ленту, продвигает ленту по направлению, указанному в таблице, и наконец, переходит в указанное в таблице состояние. Таким образом, каждый элемент таблицы состоит из символа, который нужно записать на ленту, направление перемещения ленты и следующее состояние машины. Например, возьмем такую таблицу:
0 1
A (1, вперед, В) (0, назад, В)
B (0, вперед, А) (1, вперед, А)
Строки таблицы — это состояния, в которых может находится машина, в данном случае — два состояния А и В. Столбцы — символы, которые машина может записать на ленту или считать с нее. В начальный момент времени вся лента помечена символом «0», а машина находится в состоянии «А». Машина считывает с ленты символ («0») и обращается к элементу таблицы в строке «А» и столбце «0». Это — «1,вперед,В». Это значит, что нужно записать на ленту «1», продвинуть ее вперед и перейти в состояние «В». Далее цикл повторяется. Таким образом, поведение машины целиком определяется ее таблицей, которая в современных терминах называется программой, а лента оказывается памятью компьютера. Движение относительно, и с таким же успехом можно представить, что лента неподвижна, а сама машина перемещается по ней. А если пойти еще дальше, то одномерную ленту можно заменить на двумерную плоскость. Такая машина Тьюринга, перемещающаяся по плоскости и есть тьюрмит. (Можно пойти еще дальше и добавить третье измерение, чтобы тьюрмит перемещался в пространстве, но это уже для маньяков :). Тьюрмиты появились благодаря Г.Тэрку из Университета Северной Каролины в Чепел-Хилле, США. Для случая двумерной машины Тьюринга в таблице состояний направление движения придется расширить — кроме «вперед» и «назад» добавить повороты направо и налево на 90 градусов относительно текущего направления движения. Например, на рисунке представлен след тьюрмита с одним единственным состоянием А.

рисунок 1

Его внутренняя таблица такая:
Черный Белый
А (Белый, влево, А) (Черный, вправо, А)
Обратите внимание, как хаотическое движение сменяется замысловатой структурой, растущей в бесконечность. Еще один тьюрмит, придуманный Тэрком, оставляет рисует расширяющиеся спирали, как на следующем рисунке:

рисунок 2

Его поведение описывается такой таблицей:
Белый Зеленый
A (Зеленый, влево, А) (Белый, прямо, В)
B (Зеленый, вправо, А) (Зеленый, вправо, А)
Большинство тьюрмитов создают случайные хаотические структуры, но встречаются и настоящие «художники», как например на этом рисунке:

рисунок 3

Он руководствуется такой таблицей:
Черный Красный Синий Желтый
А (Красный, влево, А) (Синий, вправо, А) (Желтый, вправо, А) (Черный, влево, А)
Интересно, что рисунок, созданный этим тьюрмитом, обладает симметрией. Написать программу, которая моделирует движение тьюрмитов на плоскости, несложно. Каждый тьюрмит в программе описывается несколькими параметрами: текущими координатами на плоскости x и y, текущим состоянием s, текущим направлением движения d и внутренней таблицей. Внутренняя таблица тьюрмита проще всего описать тремя отдельными таблицами: — color (цвет) — таблица, определяющая цвет, в который надо закрасить текущую ячейку; — motion (движение) — таблица, которая определяет направление движения тьюрмита; — state (состояние) — таблица, определяющая состояние, в которое перейдет тьюрмит. Плоскость, по которой двигается тьюрмит, описывается таблицей field. Например для тьюрмита №2: Закодируем состояние «А» — цифрой 0, а «В» — цифрой 1, белый цвет цифрой «0», зеленый — «1». Перемещения: 0 — влево, 1 — вправо, 2- вперед, 3 — назад. Тогда таблицы примут такой вид: Таблица color
0 1
0 1 0
1 1 1
Таблица motion
0 1
0 0 2
1 1 1
Таблица state
0 1
0 0 1
1 0 0
Опишем алгоритм движения тьюрмита:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
очистить_поле
x := ширина/2
y := высота/2
s := 0
d := 0
repeat
    col := field[x,y]
    c := color[s,col]
    field[x,y] := c;
    окрасить_точку[x,y,c]
    s := state[s,col]
    d := определитьd(motion[s,col])
    x := определитьX(d,x)
    y := определитьY(d,y)
until false
Сначала очистим поле, по которому будет двигаться тьюрмит (закрасим его цветом «0»), установим начальные координаты x и y посередине поля, зададим начальное состояние — «0» и начальное направление движения. В бесконечном цикле проводим такие вычисления: в переменную col занесем цвет, в который окрашена ячейка, на которой находится тьюрмит. Определяем следующий цвет по таблице color и рисуем точку в текущих координатах заданным цветом. Не забудем внести этот цвет и в таблицу field. Определяем по таблице motion новое направление движения; затем по координатам и заданному направлению движения определяем следующие координаты в которые и должен переместиться тьюрмит (на мой взгляд — это самая сложная часть программы :). Однако возникает одна проблема. По определению плоскость, по которой движется тьюрмит, считается бесконечной, что на компьютере не смоделируешь. В таком случае эту плоскость лучше свернуть в тор, то есть при пересечении тьюрмитом правой границы поля он появляется слева и наоборот, а также при пересечении верхней границы он появляется снизу и наоборот. Сделать это можно, например так:
1
2
if x=Xmax then x:=0
if x<-1 then x:=Xmax-1
где координата x меняется от 0 до Xmax-1; точно так же сделать и для координаты y. Но можно и схитрить:
1
x:=(x+Xmax) % Xmax
где % — операция взятия остатка от деления целых чисел. Удачи в программировании! Для ленивых предлагаю скачать готовую программу для конструирования своих тьюрмитов.
Тьюрмиты
Тьюрмиты
TurmiteSetup0.25.exe
Version: 0.25
340.2 KiB
371 Downloads
Детали
О.Воронин, А.К.Дьюдни

Страница просмотрена 4960 раз(а)