| к содержанию |
Я хочу рассказать вам о слонопотамах. Конечно, я бы мог рассказать нечто подобное и о других животных, более известных вам. Но ведь в этом случае вы мне не поверите. Еще хуже, если б я говорил о людях. Чего доброго, вы еще подумаете, что это какие-нибудь намеки на какие-нибудь обстоятельства. И это породит неуместные в данном случае эмоции и затруднит понимание совсем простых вещей, о которых я и хочу вам рассказать.
Итак, слонопотамы. Я расскажу вам о них немного больше, чем вы бы могли узнать из книги о Винни-пухе. Из нее известно только, что слонопотамы большие, и что следы их также большие. Я же расскажу, какого цвета бывают слонопотамы. Конечно, это не намного больше того, что было известно Винни-пуху, но ведь слонопотамы — такие загадочные животные!
Есть две породы слонопотамов: молочные слонопотамы — они имеют белый цвет, и кофейные слонопотамы, которые скорее черные, чем белые. Но если вы посмотрите на стадо молочных слонопотамов, то вы увидите, что они тоже не одинаковые — некоторые из них более белые, чем другие. То же самое и с кофейными слонопотамами — некоторые из них чернее других. Вы видели когда-нибудь светло-белый и темно-белый цвет? А также светло-черный и темно-черный? А у слонопотамов такое бывает! Конечно, если бы исследователи слонопотамов работали в Майкрософт, они бы тут же назвали эти цвета так: белый, серебряный, серый, черный. И они были бы правы. Но только относительно видимого цвета. Но ведь за цветом слонопотама скрывается порода и еще нечто, что совершенно не отражает серая шкала Майкрософта.
Поэтому слонопотамоведы не удовлетворились наблюдением за стадом издали, а исследовали образцы шерсти слонопотамов, которые те оставляют, когда чешут свои спины о стволы деревьев. Оказалось, что цвет шерсти всех молочных слонопотамов одинаковый — белый. Но под шерстью имеется еще и подшерсток, который бывает либо тоже белым, либо черным. Таким образом, молочный слонопотам с черным подшерстком оказывается на вид сероватым. Точно так же и кофейные слонопотамы могли иметь черный и белый подшерсток. Поэтому кофейный слонопотам с белым подшерстком оказывался цвета кофе с молоком. Таким образом, слова светло-белый, темно-белый, светло-черный и темно-черный правильно отражали как цвет подшерстка, так и цвет самой шерсти, а значит были более правильными, чем описание цвета одним словом.
Но и наблюдения издали принесли свои плоды: по некоторым чертам поведения слонопотамов удалось разделить их на самочек и самцов. И что оказалось? Оказалось, что самцы всегда более яркие, чем самочки. То есть все серые слонопотамы были самочками, а представители "чистого" цвета — самцами. То есть, зная о подшерстке, можно сказать, что самцы всегда имеют подшерсток своего цвета, а самочки — противоположного.
Я надеюсь, что сообщенные мною сведения будут вам полезными, и что случайно наткнувшись на слонопотама, вы не помчитесь сломя голову прочь, а по цвету сможете правильно идентифицировать его породу, цвет подшерстка и пол и убедитесь, что все, что я вам здесь сообщил — чистая правда.
Мы с Дейвом Грином обсуждали проблему стыковки односторонних многовалентных барбер-операторов, и Дейв предложил раскрасить вселенную Жизни в 4 цвета. Иногда раскраска доски помогает значительно упростить математическую задачу. Самый известный пример: можно ли костями домино покрыть всю шахматную доску, у которой выпилены 2 противоположных угловых поля? Если не учитывать раскраски, то над перебором всевозможных способов покрытия можно биться часами. Но если учесть, что после выпиливания количество черных и белых полей уже не совпадает, а кость домино всегда покрывает одно черное и одно белое поле, то ответ очевиден: нельзя.
Дейв предложил раскрасить доску так, чтобы одинаковым цветом были закрашены поля, доступные для слона в китайских шахматах, стоящего на таком же поле (о китайских шахматах см. http://www.azartgames.com/chess/Xianggi.htm). Это аналогично тому, как мы раскрашиваем обычную шахматную доску согласно доступности полей для обычного шахматного слона. Но китайский слон может ходить только через одну клетку по диагонали, так что в общем случае поле можно раскрасить в 8 различных цветов, каждый из которых будет образовывать на поле "слоновьи квадраты". Нам же требуется только 4 цвета. Для раскраски доски в эти 4 цвета требуется некоторая гипотетическая шахматная фигура, способная ходить через одну клетку по горизонтали или вертикали (а также, возможно, и по диагонали). Такую фигуру чисто условно я назвал слонопотамом.
Все выше сказанное относительно масти слонопотамов несет вполне определенный математический подтекст. Четыре слонопотамьи цвета имеют 3 бинарных свойства: порода, подшерсток и пол. Примем следующие числовые значения:
Эти свойства не являются независимыми, поскольку иначе они бы давали 8 различных наборов, тогда как результирующих цветов только 4. Зависимость между ними очень простая: пол можно получить как исключающее ИЛИ (XOR), примененное к породе и подшерстку. В силу симметричности операции XOR подшерсток есть исключающее ИЛИ по отношению к породе и полу. Кроме того порода есть исключающее ИЛИ по отношению к подшерстку и полу. То есть, любое из трех свойств может быть получено из двух других путем применения операции XOR.
Четыре цвета серой шкалы имеют следующие значения свойств:
Раскрасим шахматную доску так, чтобы двигаясь с данной клетки "ходом слонопотама", то есть, прыгая через клетку по вертикали и горизонтали, мы всегда попадали на клетку того же цвета. Всего возможно 24 способа такой раскраски. Мы выберем одну из них, а именно: начало координат будет всегда черным; по диагонали от него будет клетка той же породы, но противоположного подшерстка и пола, то есть серая; по вертикали соседней будет клетка того же подшерстка, но противоположных пола и породы, то есть серебряная; а по горизонтали соседней будет клетка того же пола, но противоположных породы и подшерстка, то есть белая.
Рассмотрев подробно раскрашенную клетчатую плоскость, мы заметим, что клетки одинаковой породы выстроились вдоль диагоналей. Если не рассматривать другие свойства клеток, то можно сказать, что порода в нашей раскраске играет ту же роль, что и цвет при обычном двухцветном закрашивании шахматной доски. А клетки с одинаковым подшерстком оказываются выстроены в вертикальные ряды и образуют полосатую структуру. Такую же полосатую структуру, но из горизонтально расположенных рядов мы имеем, если будем учитывать только пол клеток.
Строго говоря, раскраска поля здесь играет чисто иллюстративную роль. Достаточно ввести три булевых свойства ячеек поля d, v и g, связанных соотношением d = v XOR g; Свойство d должно быть одинаковым вдоль диагоналей и меняться при переходе на соседнюю ортогональную ячейку, свойство v не должно меняться вдоль вертикали и должно быть разным для соседних горизонтальных или диагональных ячеек, а свойство g постоянно вдоль горизонталей и меняется вдоль вертикалей и диагоналей. Но цветные понятия намного нагляднее и доступнее для понимания, поэтому я буду использовать главным образом их.
Еще раз напоминаю, что порода нами выбрана, как d-свойство, то есть свойство, постоянное вдоль диагоналей, подшерсток является v-свойством, постоянным вдоль вертикалей, а пол является g-свойством, так как постоянен вдоль горизонталей.
Расположим на раскрашенном поле какой-нибудь объект Жизни. Каждый бит этого объекта окажется на клетке, окрашенной определенным цветом — будем говорить, что бит будет иметь этот цвет. Посмотрим, как будут меняться цвета битов объекта, если его подвергнуть какому-либо пространственному преобразованию.
Под пространственными преобразованиями мы будем понимать всевозможные сдвиги, повороты и отражения объекта, а также их сочетания. Для начала несколько общих положений.
Простейшее преобразование — это сдвиг объекта. Ясно, что сдвиг на 2 клетки по горизонтали, вертикали или диагонали приведет к тому, что все биты объекта окажутся на клетках того же цвета, что и раньше. Это вытекает из того, что согласно "ходу слонопотама" закраска поля периодична с периодом 2. Также ясно, что сдвиг на четное число клеток также не изменит цвет битов объекта. А сдвиг на нечетное число клеток приведет к той же раскраске объекта, что и сдвиг на 1 клетку в том же направлении. Ведь нечетное число можно представить как единица плюс четное число, а как я только что сказал, сдвиг на четное число клеток ничего не меняет в раскраске.
То есть имеет смысл подробно рассмотреть только, как изменится раскраска объекта при его сдвиге на одну клетку. В дальнейшем, если не указано, на сколько клеток производился сдвиг, мы всегда будем иметь в виду именно сдвиг на 1 клетку. Сдвиг по вертикали — это сдвиг вдоль полосатой структуры, которую образует подшерсток. Естественно, при таком сдвиге подшерсток измениться не может. А вот два других свойства — порода и пол изменятся на противоположные. Точно так же, горизонтальный сдвиг не изменит пол ни у одного бита объекта, но зато изменит породу и подшерсток. Сдвинув объект на 1 клетку по диагонали, мы не изменим породу его битов, но пол и подшерсток заменятся на противоположные. Если мы последовательно совершим два сдвига — вертикальный и горизонтальный, то мы дважды изменим породу битов объекта, вернув ее к первоначальному состоянию, и по одному разу их пол и подшерсток, что будет эквивалентно диагональному сдвигу.
Более сложные сдвиги на m клеток по горизотали и n клеток по вертикали очень легко свести к уже рассмотренным: достаточно числа m и n заменить на 0 или 1 в зависимости от того, четные они или нечетные.
В dvg терминологии рассмотренные преобразования более очевидны и легки для запоминания:
Теперь посмотрим, как перекрасятся биты объекта при его отражениях. При нечетном ортогональном отражении, то есть тогда, когда линия отражения вертикальна или горизонтальна и проходит через центры клеток, раскраска битов объекта не меняется. Это следует из того, что раскраска (бесконечного) поля симметрична относительно этих линий.
При четных же ортогональных отражениях, то есть когда линия отражения проходит через границу между клетками, результат зависит от того, вертикальна или горизонтальна линия отражения. Если она горизонтальна, то подшерсток битов объекта не меняется (ведь его биты остаются на тех же вертикалях), а порода и пол меняются на противоположные. То есть вертикальное четное отражение перекрашивает объект точно так же, как и вертикальный сдвиг. И всегда может быть скомпенсировано вертикальным сдвигом. Горизонтальное четное отражение, то есть отражение относительно вертикальной линии, проходящей через границы клеток, не изменяет пол битов объекта, но меняет их породу и подшерсток. Оно действует точно так же, как горизонтальный сдвиг и при необходимости может быть им скомпенсировано.
Несколько сложнее меняется раскраска объекта при диагональном отражении. Прежде всего, не существует двух видов диагонального отражения (четного и нечетного). Образец можно отразить только относительно линии, проходящей через центры ячеек. Но при этом некоторые его биты перекрашиваются по четному типу, а некоторые по нечетному. Не меняют своей окраски биты, чья порода совпадает с породой линии отражения. Они расположены на четном расстоянии по горизонтали и вертикали от этой линии, и при отражении их строка и столбец меняются на четное число, а значит их подшерсток и пол не меняются. Биты с противоположной породой расположены на нечетном расстоянии от линии отражения, и их подшерсток и пол изменяются на противоположные. Эти биты ведут себя подобно тому, как это делают биты при диагональном сдвиге. Но в целом диагональный сдвиг не может скомпенсировать последствия диагонального отражения, так как диагональный сдвиг одинаково действует на все биты независимо от их породы, а отражение — не изменяет биты своей породы и перекрашивает подшерстки и пола противоположной породы.
Последовательное применение диагонального отражения и диагонального сдвига эквивалентно диагональному отражению относительно линии другой породы. А последовательное применение двух диагональных отражений относительно линий разных пород эквивалентно диагональному сдвигу. Для параллельных линий отражения это очевидно, так как действительно сдвигает объект по диагонали на нечетное число клеток.
Теперь рассмотрим повороты объекта на раскрашенном поле. Возможны повороты на углы 90, 180 и 270 градусов. Повороты на 180 и 270 градусов можно рассматривать просто как 2 или 3 раза примененный поворот на 90 градусов. Кроме этого, как и расположение оси при отражениях, существенным является также местоположение центра поворота.
Первый случай (будем называть его поворот-1), это когда центр поворота находится в центре клетки. Тогда цвет бита, расположенного в этой клетке, не изменяется. А значит, не меняется и цвет всех битов той же породы. Биты противоположной породы изменят пол и подшерсток на противоположные при повороте на 90 и 270 градусов и не изменят цвета при повороте на 180 градусов. Это означает, что элементарный поворот на 90 градусов изменяет раскраску точно так же, как диагональное отражение относительно оси той же породы, что и центр поворота-1. А поворот на 180 градусов вообще не изменяет раскраски поля.
Второй случай (поворот-2), когда центр поворота находится в точке пересечения линий сетки, намного сложнее. При таком повороте изменяются цвета всех битов объекта. Причем, поскольку центр поворота соприкасается одинаковым образом с клетками всех возможных цветов серой шкалы, то непонятно, к какому из цветов его привязать. Ясно только, что породы всех битов объекта при повороте на 90 градусов изменятся на противоположные. Кроме того биты одной из пород изменят пол, а биты другой породы изменят подшерсток.
Если после поворота-2 еще и сдвинуть объект по горизонтали или вертикали, то породы всех битов объекта еще раз инвертируются, то есть вернутся в первоначальное положение. Кроме того при сдвиге по горизонтали изменится подшерсток. Это означает, что для той из пород, у которой он изменялся при повороте-2, подшерсток также вернется в первоначальное состояние, и биты этой породы окажутся окрашенными в первоначальные цвета. Биты же другой породы, менявшие пол при повороте-2, дополнительно изменят и подшерсток. То есть результирующая окраска будет соответствовать повороту-1 на 90 градусов (вокруг центра клетки). При сдвиге по вертикали, выполненном после поворота-2, изменится пол всех битов объекта, то есть для одной из пород он вернется в первоначальное состояние, а для другой окажется измененным вместе с подшерстком.
Это означает, что последовательное применение поворота-2 (вокруг центра пересечения линий сетки) и ортогонального сдвига эквивалентно повороту-1 (вокруг центра клетки). Два последовательных поворота-2 , то есть поворот-2 на 180 градусов, возвращают породы всех битов в первоначальное состояние, но меняют пол и подшерсток на противоположные. То есть, поворот-2 на 180 градусов эквивалентен диагональному сдвигу (или повороту-1 на 180 градусов плюс диагональному сдвигу) и может быть им скомпенсирован.
Есть еще одна возможность выбрать центр поворота — расположить эту точку на середине границы клетки. Ясно, что при этом невозможен поворот на 90 градусов. Элементарным поворотом этого типа (назовем его поворот-3) будет поворот на 180 градусов. При этом, если центр поворота расположен в середине вертикальной границы клетки, то клетки объекта перекрасятся одним способом, а если в середине горизонтальной границы — то совсем по-другому. То есть фактически мы имеем два разных преобразования — поворот-3г и поворот-3в.
Поворот-3г сохраняет горизонтальную составляющую цвета, то есть пол, и изменяет породу и подшерсток. То есть он ведет себя, как горизонтальный сдвиг (или как горизонтальное отражение). Поворот-3в изменяет раскраску так же, как вертикальный сдвиг или вертикальное отражение.
Теперь попробуем формализовать все сказанное. Ясно, что все пространственные преобразования объекта, учитывающие изменения цветов его бит, образуют группу. Введем следующие обозначения:
Эта группа преобразований является Абелевой, то есть результат применения двух последовательных преобразований не зависит от порядка их применения. Цвет отдельных битов объекта претерпевает изменения в процессе преобразований. Но сами преобразования не зависят от цвета битов объекта. Индексы m и c, входящие в некоторые преобразования отражают цвет некоторой ячейки или ряда ячеек поля, раскраска которого не меняется при преобразованиях — преобразованиям подвергается только объект (паттерн), находящийся на данном поле.
Верны следующие формулы:
Tg*Tg=E; Tv*Tv=E; Td*Td=E; Tg*Td=Tv; Tv*Td=Tg; Tv*Tg=Td; Mov=E; Mog=E; Mev=Tv; Meg=Tg; Mdm*Mdm=E; Mdc*Mdc=E; Td*Mdm=Mdc; Td*Mdc=Mdm; Mdm*Mdc=Td; R1m=Mdm; R1c=Mdc; R1m*R1m=E; R1c*R1c=E; Td*R1m=R1c; Td*R1c=R1m; R1m*R1c=Td; R2m^4=E; R2m*R2m=Td; Tg*R2m=R1m; Tv*R2m=R1c; R2c^4=E; R2c*R2c=Td; Tg*R2c=R1c; Tv*R2c=R1m; R3g=Meg=Tg; R3v=Mev=Tv; R3g*R3g=E; R3v*R3v=E; R3g*R3v=Td;
Ясно, что изложенные соображения можно применять при преобразованиях объектов в клетчатом пространстве игры Жизнь. Я уже упоминал проблемы стыковки многовалентных барбер-радикалов. Но подробное изложение этого выходит за рамки данного сообщения.
Широко применяются в игре Жизнь так называемые кантователи глайдеров. К ним относятся отражатели, толкатели и фазосдвигатели. Общее у них то, что они преобразуют входной глайдер в выходной, расположенный в другом месте, имеющий другое направление и фазу. Из нескольких кантователей можно собирать более сложные — их свойства определяются свойствами исходных кантователей. Знание того, как именно свойства отдельных кантователей влияют на свойства составного кантователя может значительно облегчить его построение.
Глайдер представляет собой объект периода 4. То есть через 4*N поколений он будет в той же фазе на той же диагонали. Но оказывается для корректного учета его положения после прохода через ряд кантователей недостаточно рассматривать его, как объект периода 4 — надо учитывать сдвиг его фазы как объекта периода 8. Это и определяет полезность изложенной теории слонопотамьих квадратов для целей классификации глайдерных кантователей.
Мне бы хотелось более подробно изложить теорию глайдерных отражателей, но выпуск очередного номера рассылки и так неприлично затянулся, а если я займусь еще и этим, боюсь, мои читатели вообще ничего не получат.
Николай Белюченко.
| к содержанию |