Теорема Кертиса – Хедлунда – Линдона

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

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

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

Определения

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

\dots, Икс -2, Икс -1, Икс 0, Икс 1, Икс 2, \dots

.

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

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

Карта сдвига — это особая непрерывная функция $s$ в пространстве сдвига, которая преобразует конфигурацию $x$ конфигурацию $y$ , в которой каждый символ сдвигается на одну позицию по сравнению с предыдущей позицией: то есть для каждого целого числа $i$ i $y в новую = 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$ в конечный алфавит, а сдвиг-эквивариантность заменяется эквивариантностью действием под $Г$ на себе. В частности, это применимо к клеточным автоматам, определенным на целочисленной сетке любой размерности.

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

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

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

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

Обобщение

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

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

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

См. также

Суръюнктивная группа

Ссылки

^ Хедлунд, Густав А. (1969), «Эндоморфизмы и автоморфизмы динамических систем сдвига», Теория математических систем , 3 (4): 320–375, doi : 10.1007/BF01691062 , S2CID 21803927 .
^ Шунич, Зоран (2014), «Клеточные автоматы и группы Туллио Чеккерини-Зильберштейна и Мишеля Курнаерта (рецензия на книгу)», Бюллетень Американского математического общества , 51 (2): 361–366, doi : 10.1090/S0273-0979 -2013-01425-3 .
^ Перейти обратно: ^а ^б Ричардсон, Дэниел (1972), «Тесселяции с локальными преобразованиями», Журнал компьютерных и системных наук , 6 (5): 373–388, doi : 10.1016/S0022-0000(72)80009-6 , MR 0319678 .
^ Перейти обратно: ^а ^б Чекерини-Зильберштейн, Туллио; Курнат, Мишель (2010), «Теорема 1.8.1 (теорема Кертиса – Хедлунда)», Клеточные автоматы и группы , Монографии Springer по математике, Springer-Verlag, стр. 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, номер документа : 10.1007/11505877_5 .
^ Соботтка, Марсело; Гонсалвес, Дэниел (2017), «Заметка об определении скользящих блочных кодов и теореме Кертиса-Хедлунда-Линдона» , Journal of Cellular Automata , 12 (3–4): 209–215, arXiv : 1507.02180

[1] Хедлунд, Густав А. (1969), «Эндоморфизмы и автоморфизмы динамических систем сдвига», Теория математических систем , 3 (4): 320–375, doi : 10.1007/BF01691062 , S2CID 21803927 .

[2] Шунич, Зоран (2014), «Клеточные автоматы и группы Туллио Чеккерини-Зильберштейна и Мишеля Курнаерта (рецензия на книгу)», Бюллетень Американского математического общества , 51 (2): 361–366, doi : 10.1090/S0273-0979 -2013-01425-3 .

[r72-3] Перейти обратно: ^а ^б Ричардсон, Дэниел (1972), «Тесселяции с локальными преобразованиями», Журнал компьютерных и системных наук , 6 (5): 373–388, doi : 10.1016/S0022-0000(72)80009-6 , MR 0319678 .

[csc-4] Перейти обратно: ^а ^б Чекерини-Зильберштейн, Туллио; Курнат, Мишель (2010), «Теорема 1.8.1 (теорема Кертиса – Хедлунда)», Клеточные автоматы и группы , Монографии Springer по математике, Springer-Verlag, стр. 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 .

[SoboGon-7] Соботтка, Марсело; Гонсалвес, Дэниел (2017), «Заметка об определении скользящих блочных кодов и теореме Кертиса-Хедлунда-Линдона» , Journal of Cellular Automata , 12 (3–4): 209–215, arXiv : 1507.02180

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]