Теорема Кертиса – Хедлунда – Линдона. - Curtis–Hedlund–Lyndon theorem

В Теорема Кертиса – Хедлунда – Линдона. математический характеристика из клеточные автоматы с точки зрения их символическая динамика. Он назван в честь Мортон Л. Кертис, Густав А. Хедлунд, и Роджер Линдон; в своей статье 1969 года, излагающей эту теорему, Хедлунд назвал Кертиса и Линдона соавторами открытий.[1] Его назвали «одним из фундаментальных результатов символической динамики».[2]

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

Версия теоремы в статье Хедлунда применима только к одномерным конечным автоматам, но является обобщением на многомерные целочисленные решетки вскоре был опубликован Ричардсон (1972),[3] и его можно еще обобщить с решеток на дискретные группы. Одним из важных следствий теоремы является то, что для обратимые клеточные автоматы обратная динамика автомата также может быть описана клеточным автоматом.

Определения

An алфавит - любой конечный набор символов, который можно рассматривать как состояния ячеек в клеточный автомат. А конфигурация это би-бесконечная последовательность символов из алфавита:

..., Икс−2, Икс−1, Икс0, Икс1, Икс2, ....

А должность в конфигурации целое число, индекс одного из символов в последовательности; позиции можно рассматривать как клетки клеточного автомата. А шаблон - конечный набор позиций и присвоение символов каждой из этих позиций.

В сдвинуть пространство - это множество всех возможных конфигураций в данном алфавите. Ему может быть придана структура топологическое пространство согласно Топология Кантора, в котором фундаментальные открытые множества - это наборы конфигураций, которые соответствуют любому единственному шаблону, а открытые множества - это произвольные объединения фундаментальных открытых множеств. В этой топологии функция ж от конфигураций к конфигурациям непрерывный если для любого фиксированного шаблона п определение фундаментального открытого множества п, набор ж−1(п) конфигураций, отображаемых ж в п сам может быть описан (возможно, бесконечным) множеством S шаблонов со свойством, которому принадлежит конфигурация ж−1(п) тогда и только тогда, когда он соответствует шаблону в S.

В карта сдвига - конкретная непрерывная функция s на пространстве смены, которое преобразует конфигурацию Икс в новую конфигурацию y в котором каждый символ сдвигается на одну позицию по сравнению с предыдущей позицией: то есть для каждого целого числа я, yя = Икся − 1. Функция ж является эквивариантный под картой сдвига, если преобразование конфигураций, описываемых ж коммутирует со сменной картой; то есть для каждой конфигурации Икс, должно быть так, что ж(s(Икс)) = s(ж(Икс)). Интуитивно это означает, что каждая позиция конфигурации обновляется ж используя то же правило, что и любую другую позицию.

А клеточный автомат определяется правилом для вычисления нового значения каждой позиции в конфигурации на основе только значений ячеек в заранее фиксированной конечной окрестности, окружающей позицию, при этом все позиции конфигурации обновляются одновременно на основе того же правила обновления. То есть новое значение позиции является функцией только значений ячеек в его окрестности, а не зависит в более общем случае от неограниченного количества ячеек предыдущей конфигурации. Функция ж который использует это правило для отображения конфигурации клеточного автомата в его последующую конфигурацию, обязательно эквивариантен по отношению к карте сдвига, исходя из предположения, что все позиции используют одно и то же правило обновления. Он также обязательно непрерывен в топологии Кантора: если п фиксированный паттерн, определяющий фундаментальное открытое множество п, тогда ж−1(п) определяется конечным набором шаблонов, присвоения ячейкам в окрестности п это причина ж производить п. Теорема Кертиса – Хедлунда – Линдона утверждает, что этих двух свойств достаточно для определения клеточных автоматов: каждая непрерывная эквивариантная функция является правилом обновления клеточного автомата.

Доказательство

Чекерини-Зильберштейн и Корнаерт предоставляют следующее доказательство теоремы Кертиса – Хедлунда – Линдона.[4]

Предположим ж - непрерывная сдвиг-эквивариантная функция на пространстве сдвигов. Для каждой конфигурации Икс, позволять п быть шаблоном, состоящим из одного символа, который появляется в нулевой позиции ж(Икс).По преемственности ж, должен существовать конечный образец q в Икс так что, если позиции вне q изменяются произвольно, но позиции внутри q фиксируются на своих значениях в Икс, то результат применения ж остается неизменным в нулевой позиции. Эквивалентно должно существовать фундаментальное открытое множество QИкс такой, что Икс принадлежит QИкс и такой, что для каждой конфигурации y в QИкс, ж(Икс) и ж(y) имеют такое же значение в нулевой позиции. Эти фундаментальные открытые множества QИкс (для всех возможных конфигураций Икс) для мужчины открытая крышка сменного пространства. Тем не менее, пространство смены - это компактное пространство: это произведение конечных топологических пространств с алфавитом в качестве точек, поэтому компактность следует из Теорема Тихонова. По компактности каждое открытое покрытие имеет конечное подпокрытие. Конечный набор позиций, появляющихся в этом конечном подпокрытии, может использоваться как окрестность нулевой позиции в описании ж как правило клеточного автомата.

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

Контрпример для бесконечных алфавитов

Рассмотрим пространство бибесконечных последовательностей целых чисел и определим функцию ж из этого пространства в себя по правилу, что если ж(Икс) = y, то для каждой позиции я, yя = Икся + Икся. Это правило одинаково для каждой позиции, поэтому оно эквивалентно сдвигу. И можно показать, что он непрерывен согласно топологии Кантора: для каждого конечного шаблона п в y, есть узор в Икс не более чем в два раза больше позиций, которые заставляют ж генерировать п, состоящий из ячеек в п вместе с ячейками, значения которых копируются в п. Однако, несмотря на непрерывность и эквивариантность, ж не является правилом клеточного автомата, потому что значение любой ячейки может потенциально зависеть от значения любой другой ячейки, а не только от ячеек в любой заранее фиксированной конечной окрестности.[4]

Приложение к обратимым клеточным автоматам

Клеточный автомат называется обратимый когда у каждой конфигурации автомата есть ровно один предшественник. Из аргумента компактности следует, что функция, отображающая каждую конфигурацию на ее предшественницу, сама является непрерывной в пространстве сдвига, и она, очевидно, также инвариантна относительно сдвига. Следовательно, согласно теореме Кертиса – Хедлунда – Линдона, обращенная во времени динамика клеточного автомата может сама генерироваться с использованием другого правила клеточного автомата.[3] Однако окрестность клетки в обратном автомате может быть значительно больше, чем окрестность той же клетки в прямом автомате.[5][6]

Обобщение

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

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

Обобщенные клеточные автоматы были предложены Соботтка и Гонсалвеш (2016) [7] где было доказано, что они соответствуют непрерывным сдвиг-эквивариантным отображениям.

Смотрите также

использованная литература

  1. ^ Хедлунд, Густав А. (1969), "Эндоморфизмы и автоморфизмы динамических систем сдвигов", Математическая теория систем, 3 (4): 320–375, Дои:10.1007 / BF01691062.
  2. ^ Шунич, Зоран (2014), «Клеточные автоматы и группы, Туллио Чекерини-Зильберштейн и Мишель Корнаерт (рецензия на книгу)», Бюллетень Американского математического общества, 51 (2): 361–366, Дои:10.1090 / S0273-0979-2013-01425-3.
  3. ^ а б Ричардсон, Дэниел (1972), "Тесселяции с локальными преобразованиями", Журнал компьютерных и системных наук, 6: 373–388, Дои:10.1016 / S0022-0000 (72) 80009-6, Г-Н  0319678.
  4. ^ а б Чекерини-Зильберштейн, Туллио; Coornaert, Michel (2010), "Теорема 1.8.1 (теорема Кертиса – Хедлунда)", Клеточные автоматы и группы, Монографии Springer по математике, Springer-Verlag, p. 20, ISBN  978-3-642-14033-4.
  5. ^ Маргенштерн, Морис (2007), Клеточные автоматы в гиперболических пространствах - Том I, Том 1, Archives contemporaines, стр. 134, ISBN  978-2-84703-033-4.
  6. ^ Кари, Джаркко (2005), «Обратимые клеточные автоматы» (PDF), Развитие теории языка, Конспект лекций по информатике, 3572, Springer-Verlag, стр. 2–23, Дои:10.1007/11505877_5.
  7. ^ Соботтка, Марсело; Гонсалвеш, Даниэль (2016), Заметка об определении скользящих блочных кодов и теореме Кертиса-Хедлунда-Линдона, arXiv:1507.02180, Bibcode:2015arXiv150702180S.