Теорема Curtis-Хедлунд-Линдона представляет собой математическую характеристику из клеточных автоматов с точки зрения их символической динамики . Он назван в честь Мортона Л. Кертиса , Густава А. Хедлунда и Роджера Линдона ; в своей статье 1969 года, излагающей теорему, Хедлунд назвал Кертиса и Линдона соавторами-первооткрывателями. [1] Это было названо «одним из фундаментальных результатов символической динамики». [2]
Теорема утверждает, что функция из пространства сдвигов в себя представляет собой функцию перехода одномерного клеточного автомата тогда и только тогда, когда она непрерывна (относительно топологии Кантора ) и эквивариантна (относительно отображения сдвига). В более общем смысле, он утверждает, что морфизмы между любыми двумя пространствами сдвига (то есть непрерывными отображениями, которые коммутируют со сдвигом) - это в точности те отображения, которые могут быть определены равномерно по локальному правилу.
Версия теоремы из статьи Хедлунда применялась только к одномерным конечным автоматам, но ее обобщение на целочисленные решетки более высокой размерности было вскоре опубликовано Ричардсоном (1972) , [3], и ее можно еще обобщить с решеток на дискретные группы. . Одним из важных следствий теоремы является то, что для обратимых клеточных автоматов обратная динамика автомата также может быть описана клеточным автоматом.
Определения
Алфавит любое конечное множество символов, которые можно рассматривать как состояния клеток в клеточном автомате . Конфигурация является би-бесконечная последовательность символов из алфавита:
- ..., х -2 , х -1 , х 0 , х 1 , х 2 , ... .
Положение в конфигурации представляет собой целое число , индекс одного из символов в последовательности; позиции можно рассматривать как клетки клеточного автомата. Шаблон конечное множество позиций и назначение символов для каждой из этих позиций.
Пространство сдвига - это набор всех возможных конфигураций в данном алфавите. Ему может быть дана структура топологического пространства в соответствии с топологией Кантора , в которой фундаментальные открытые множества - это множества конфигураций, которые соответствуют любому единственному шаблону, а открытые множества являются произвольными объединениями фундаментальных открытых множеств. В этой топологии функция f от конфигураций к конфигурациям является непрерывной, если для любого фиксированного шаблона p, определяющего фундаментальное открытое множество P , набор f −1 ( P ) конфигураций, отображаемых f в P, сам может быть описан a (возможно бесконечное) множество S узоров, со свойством , что конфигурация принадлежит ф -1 ( Р ) , если и только если она соответствует шаблону в S .
Карта сдвига - это конкретная непрерывная функция s в пространстве сдвига, которая преобразует конфигурацию x в новую конфигурацию y, в которой каждый символ сдвигается на одну позицию по сравнению с его предыдущей позицией: то есть для каждого целого числа i , y i = x i - 1 . Функция F является эквивариантным при отображении сдвига , если преобразование от конфигурации , описанной F коммутирует с картой сдвига; то есть для каждой конфигурации x должно быть так, что f ( s ( x )) = s ( f ( x )) . Интуитивно это означает, что каждая позиция конфигурации обновляется f с использованием того же правила, что и любая другая позиция.
Клеточный автомат определяются правилом для вычисления нового значения каждой позиции в конфигурации , основанной только на значениях ячеек в предшествующих уровне фиксированного конечных окрестностей вокруг позиции, со всеми позициями конфигурации обновляемыми одновременно на основе того же обновить правило. То есть новое значение позиции является функцией только значений ячеек в его окрестности, а не зависит в более общем случае от неограниченного количества ячеек предыдущей конфигурации. Функция f, которая использует это правило для отображения конфигурации клеточного автомата в конфигурацию его преемника, обязательно эквивариантна по отношению к отображению сдвига в предположении, что все позиции используют одно и то же правило обновления. Он также обязательно непрерывен в топологии Кантора: если p - фиксированный шаблон, определяющий фундаментальное открытое множество P , то f −1 ( P ) определяется конечным набором шаблонов, присваиваний ячейкам в окрестности p, которые заставить f произвести p . Теорема Кертиса – Хедлунда – Линдона утверждает, что этих двух свойств достаточно для определения клеточных автоматов: каждая непрерывная эквивариантная функция является правилом обновления клеточного автомата.
Доказательство
Чекерини-Зильберштейн и Корнаерт предоставляют следующее доказательство теоремы Кертиса – Хедлунда – Линдона. [4]
Предположим, что f - непрерывная эквивариантная по сдвигу функция на пространстве сдвигов. Для каждой конфигурации x пусть p будет шаблоном, состоящим из одного символа, который появляется в нулевой позиции f ( x ) . По непрерывности f , должен существовать конечный образец q в x такой, что, если позиции вне q изменяются произвольно, но позиции внутри q фиксируются на своих значениях в x , то результат применения f остается таким же в нулевой позиции . Эквивалентно должно существовать фундаментальное открытое множество Q x такое, что x принадлежит Q x и такое, что для каждой конфигурации y в Q x , f ( x ) и f ( y ) имеют одинаковое значение в нулевой позиции. Эти фундаментальные открытые множества Q x (для всех возможных конфигураций x ) образуют открытое покрытие пространства сдвигов. Однако пространство сдвигов - это компактное пространство : это произведение конечных топологических пространств с алфавитом в качестве их точек, поэтому компактность следует из теоремы Тихонова . По компактности каждое открытое покрытие имеет конечное подпокрытие. Конечный набор позиций, появляющихся в этом конечном подпокрытии, может использоваться как окрестность нулевой позиции в описании f как правила клеточного автомата.
Же доказательство применимо в более общем случае, когда множество целочисленных позиций заменяются любой дискретной группой G , пространство конфигураций заменяются набором функций из G до конечного алфавита и сдвига эквивариантность заменяется эквивариантностью под действием из G на себя. В частности, это относится к клеточным автоматам, определенным на целочисленной сетке любой размерности.
Контрпример для бесконечных алфавитов
Рассмотрим пространство би-бесконечных последовательностей целых чисел, и определим функцию F из этого пространства к себе в соответствии с правилом , что если е ( х ) = у , то для каждой позиции я , у я = х я + х I . Это правило одинаково для каждой позиции, поэтому оно эквивалентно сдвигу. И можно показать, что он непрерывен в соответствии с топологией Кантора: для каждого конечного шаблона p в y существует шаблон в x не более чем с вдвое большим количеством позиций, который вынуждает f генерировать p , состоящий из ячеек в p вместе с ячейки, значения которых копируются в p . Однако, несмотря на непрерывность и эквивариантность, f не является правилом клеточного автомата, потому что значение любой ячейки потенциально может зависеть от значения любой другой ячейки, а не только от ячеек в любой заранее фиксированной конечной окрестности. [4]
Приложение к обратимым клеточным автоматам
Клеточный автомат называется обратимым, если каждая конфигурация автомата имеет ровно одного предшественника. Из аргумента компактности следует, что функция, отображающая каждую конфигурацию на ее предшественницу, сама является непрерывной в пространстве сдвига, и она, очевидно, также инвариантна относительно сдвига. Следовательно, согласно теореме Кертиса – Хедлунда – Линдона, обращенная во времени динамика клеточного автомата может сама генерироваться с использованием другого правила клеточного автомата. [3] Однако окрестность клетки в обратном автомате может быть значительно больше, чем окрестность той же клетки в прямом автомате. [5] [6]
Обобщение
Можно обобщить определение клеточного автомата на те карты, которые определяются правилами вычисления нового значения каждой позиции в конфигурации на основе значений ячеек в конечной, но изменчивой окрестности, окружающей позицию. В этом случае, как и в классическом определении, локальное правило одинаково для всех ячеек, но соседство также является функцией конфигурации вокруг позиции.
Приведенный выше контрпример для непрерывного и эквивариантного по сдвигу отображения, не являющегося классическим клеточным автоматом, является примером обобщенного клеточного автомата . Когда алфавит конечен, определение обобщенных клеточных автоматов совпадает с классическим определением клеточных автоматов из-за компактности пространства сдвигов.
Обобщенные клеточные автоматы были предложены Sobottka & Gonçalves (2016) [7], где было доказано, что они соответствуют непрерывным сдвиг-эквивариантным отображениям.
Смотрите также
Рекомендации
- ^ Хедлунд, Gustav A. (1969), "Эндоморфизмы и АВТОМОРФИЗМЫ сдвига динамических систем", Математическая теория системы , 3 (4): 320-375, DOI : 10.1007 / BF01691062.
- ^ Sunic Зоран (2014), "Клеточные автоматы и группы, по Туллио Чеккерини-Зильберштейн и Мишель Coornaert (Книжное обозрение)", Бюллетень Американского математического общества , 51 (2): 361-366, DOI : 10.1090 / S0273-0979 -2013-01425-3.
- ^ а б Ричардсон, Даниэль (1972), "Паркеты с локальными преобразованиями", журнал компьютерных и системных наук , 6 : 373-388, DOI : 10.1016 / S0022-0000 (72) 80009-6 , MR 0319678.
- ^ а б Чекерини-Зильберштейн, Туллио; Coornaert, Michel (2010), «Теорема 1.8.1 (теорема Кертиса – Хедлунда)», Клеточные автоматы и группы , Монографии Springer по математике, Springer-Verlag, p. 20, ISBN 978-3-642-14033-4.
- ^ Мардженштерн, Морис (2007), Клеточные автоматы в гиперболических пространствах - Том I, том 1 , Archives contemporaines, стр. 134, ISBN 978-2-84703-033-4.
- ^ Кари, Яркко (2005), «Обратимые клеточные автоматы» (PDF) , Развитие теории языков , Лекционные заметки по информатике, 3572 , Springer-Verlag, стр. 2–23, doi : 10.1007 / 11505877_5.
- ^ Соботтка, Марсело; Гонсалвес, Даниэль (2016), Заметка об определении кодов скользящего блока и теореме Кертиса-Хедлунда-Линдона , arXiv : 1507.02180 , Bibcode : 2015arXiv150702180S.