Тьюрмиты
АрхивСовмещать приятное с полезным, хоть и не всегда, но порой удается. Например, совсем недавно я совместил подготовку статьи в "Досуги" с участием в замечательном конкурсе тьюрмитных рисунков. Что из этого вышло - судить не мне.
"Тьюрмит - это существо, вылезшее из разбитой машины Тьюринга, после того как Грегори Тэрк уронил ее со своего стола. С тех пор тьюрмиты распространились довольно широко, однако по-прежнему остаются мало исследованными созданиями. Живут тьюрмиты на бесконечной плоскости, разделенной на квадратные клетки. Чем они питаются, неизвестно. Живой тьюрмит постоянно движется по плоскости, он не может оставаться в покое".
Это вовсе не цитата из фантастического романа, а отрывок из учебного пособия по занимательной тьюрмитологии. Само это пособие, а также все остальные материалы, относящиеся к уже упомянутому конкурсу рисунков, помещены на сервере Университета города Переславля (http://up.botik.ru/~inform/thurmits/index.html). Автор текста (а также главный организатор конкурса) - программист и преподаватель этого университета Евгений Лилитко (crgames@ks.botik.ru). К слову, увлечение подобными вещами у Евгения очень давнее: еще десять лет тому назад он написал программу, которая стала чемпионом мира по "Бою в памяти". (Для тех, кто никогда не слышал о "Бое в памяти", могу сказать только, что это борьба двух программ-вирусов на ограниченном участке машинной памяти по заранее оговоренным правилам. Игра эта очень интересна и требует более подробного рассказа. Возможно, когда-нибудь в другой раз…)
Я возвращаюсь к тьюрмитам. Если попытаться кратко изложить суть, то она сводится вот к чему: тьюрмит всегда работает по программе, заложенной в его "мозг". Входной язык этой программы - не процедурный (как C++), а скорее декларативный (как, например, Пролог). В каждый момент времени выполняется одна из строк программы, а какая именно - зависит от "ситуации". Точнее - от цвета клетки, в которой тьюрмит находится, и от той строки, которая выполнялась перед этим. Результатом выполнения этой строки будет следующее:
- тьюрмит покрасит ту клетку, на которой он стоит, в некоторый (заданный в этой строке) цвет;
- затем он либо сдвинется прямо относительно своего текущего направления движения, либо свернет налево, либо повернет направо;
- тьюрмит узнает, какую строку программы он должен выполнить следующей.
Если такой строки в тексте не обнаружится, тьюрмит "умирает".
Пока такие строки находятся, тьюрмит живет вечно - а точнее, до тех пор, когда хозяин компьютера не прервет выполнение программы.
На экране при этом появляются замысловатые рисунки, красота и сложность которых зависят только от фантазии (и умения программировать!) автора тьюрмитной программы.
Кстати, синтаксис всех строк таких программ очень прост:
буква; текущий цвет; новый цвет; код поворота; новая буква.
Под буквой здесь понимается любая буква, а также цифра или другой символ, цвета кодируются числами от 0 до 15, а поворотов бывает всего три: -1="налево", 0="прямо", 1="направо".
Например, строка
A 0 15 1 A
означает, что после попадания на черное (цвет 0) поле в строке, обозначенной буквой A, тьюрмит перекрасит его в белый цвет (15), повернет направо и будет искать следующую строку для выполнения. Эта строка должна начинаться буквой A, а следом за этой буквой должен стоять цвет клетки, на которую тьюрмит попал.
Отмечу, что начальный цвет всего поля - черный, а тьюрмит при рождении находится "в состоянии A". Таким образом, первой будет выполнена та строка программы, которая начинается с "A 0".
Задача 1
Определите, что будет нарисовано тьюрмитом, если вся его программа состоит из одной приведенной выше строки - "A 0 15 1 A". А если эта программа будет иметь вид "A 0 15 0 A"?
Задача 2
А теперь разберитесь в чуть более сложной программе:
A 0 2 0 B
B 0 2 0 C
C 0 2 1 A
Задача 3
И, наконец, последнее упражнение на освоение тьюрмитной азбуки: определите, что будет рисовать тьюрмит с программой
A 0 15 1 A
A 15 15 0 A
Ответы к задачам
- Тьюрмит обойдет и закрасит белым цветом четыре соседние клетки, стоящие в вершинах квадрата. После этого он попадет на исходную клетку и умрет: ведь у него в программе нет строки для действий в ситуации "A 15".
А во втором случае тьюрмит начнет бесконечно двигаться по прямой, оставляя за собой белый след - и так будет до тех пор, пока его не остановят извне (либо он не выйдет за границы экрана, но об этом программном ограничении я еще, кажется, не упоминал).
- Будет нарисован зеленый (цвет 2) квадрат со стороной 3.
- Тьюрмит станет рисовать белую линию (точнее, двойную линию), которая будет постепенно удлиняться - по очереди то в одну, то в другую сторону.
Ну, а теперь пару слов о конкурсе. Участником его (а также членом жюри) мог стать любой житель Сети. Достаточно было зайти на соответствующую страничку, зарегистрироваться (совершенно бесплатно), скачать программу-тьюрмитник, после чего можно было садиться и писать своих тьюрмитов.
Я так и сделал.
Одной из первых моих удач была красивая "вертушка":
Ее программа совсем простая и довольно короткая:
A 0 2 0 C
A 2 0 0 B
B 2 2 1 A
B 15 2 1 A
C 2 0 -1 A
C 0 15 -1 A
C 15 2 -1 A
Хотя, конечно, эта простота обманчива - тьюрмит, рисуя вертушку, бегает по очень хитрой траектории, периодически возвращаясь от ее краев к центру, а затем убегая обратно.
Вообще, нарисовать что-либо при помощи тьюрмита не так сложно, как кажется с первого взгляда. Насколько я понял, есть два пути: либо пытаться тщательно запрограммировать поведение тьюрмита, либо действовать наобум, методом тыка. Второй путь гораздо проще и не требует от "программиста" почти никаких усилий.
Из простых программок, полученных, скорее всего, именно таким путем, я приведу здесь только одну. Автор назвал ее "желтый дом".
A 0 14 0 B
A 14 13 -1 A
A 13 0 1 B
B 0 13 1 A
B 13 14 -1 A
B 14 0 0 A
Но кроме написания таких простеньких программок, можно попытаться действительно придумать что-нибудь нетривиальное. Например, я долго бился над такой задачей: как обучить тьюрмита "красиво" обходить всевозможные изогнутые препятствия. Когда это наконец получилось, я не поверил сам себе: тьюрмит нарисовал почти правильную архимедову спираль!
Когда я пишу этот текст, результаты конкурса рисунков подведены, но еще не опубликованы, поэтому авторы многих красивых тьюрмитов мне пока неизвестны. Например, я пришел в восторг от такой картинки:
По-видимому (я сужу по использованию тех же 13-го и 14-го цветов), ее и "желтый дом" делал один и тот же автор. А программка и здесь очень проста:
A 0 14 0 B
B 0 14 0 C
C 0 14 0 E
E 0 14 0 F
F 0 14 0 J
J 0 13 -1 A
A 14 13 0 A
A 13 14 0 A
J 14 13 0 A
J 13 14 1 A
Для тех, кто еще не совсем разобрался: первые шесть строк рисуют квадратик, а дальше… остается всего четыре строки, и вот они-то и определяют весь остальной рисунок!
Но все эти рисуночки - просто детские забавы по сравнению с той гигантской работой, которую проделал Дмитрий Папичев. Дима просто взял и написал игру "Жизнь", о которой я недавно рассказывал (см. "Компьютерру" #243). "Жизнь" на одном-единственном тьюрмите! Я не поверил своим глазам и не верю до сих пор, но вот оно - работает, смотрите:
Здесь в качестве начальной конфигурации выбрано "планерное ружье" (см. первый из трех рисунков). Из него каждые 30 тактов вправо и вверх вылетает планер. Долетает до границы поля и там исчезает, потому что граница поля жестко задана рамкой, внутри которой все и происходит. Весь рисунок - ружье, планер, смена поколений - рисуется одним крошечным тьюрмитом, который обегает все поле внутри рамки. На втором рисунке показано состояние ружья после пары тактов жизни (это десятки тысяч команд тьюрмита, но на экране все происходит очень быстро). А на третьем - то же ружье, уже почти готовое выстрелить (еще примерно через 20 тактов "жизни").
Чтобы рисунки были хорошо видны, мне пришлось увеличивать их в восемь раз по сравнению с остальными, так что не удивляйтесь, что все точки оказались такими крупными.
Программу для "Жизни" и, в частности, для планерного ружья я уже никак не смог бы привести здесь: она занимает около 400 строк.
Кстати, это тоже превосходный результат. Попробуйте-ка уместить программу для этой игры, написанную на любом из процедурных языков, кроме ассемблера, в 400 строк и в 5 килобайт!
Ну и напоследок еще одна задача для тех, кто заинтересовался.
Задача 4
Разберитесь, что получается на экране во время работы вот такой тьюрмитной программы:
A 0 15 1 B
A 15 1 0 B
A 1 15 1 B
B 0 0 0 A
B 15 15 0 A
B 1 1 0 A
