커티스-헤들런드-린던 정리

Curtis–Hedlund–Lyndon theorem

커티스-Hedlund-Lyndon 정리는 세포 자동화의 상징적 역학 측면에서 수학적 특성화다.그것은 모튼 L의 이름을 따서 명명되었다. 커티스, 구스타프 A. Hedlund와 Roger Lyndon; 이 정리를 진술한 1969년 논문에서 Hedlund는 Curtis와 Lyndon을 공동 발견자로 인정했다.[1]그것은 "심볼한 역학의 근본적인 결과 중 하나"[2]라고 불려왔다.

정리는 이동 공간에서 그 자체로 함수가 연속적인 경우(칸토르 위상에 관한 경우)와 등가성(시프트 맵에 관한 경우)에만 1차원 세포 자동화의 전환 함수를 나타낸다고 기술하고 있다.보다 일반적으로, 그것은 두 교대 공간 사이의 형태론(즉, 교대조에서 통근하는 연속 매핑)이 정확히 지역 규칙에 의해 균일하게 정의될 수 있는 매핑이라고 주장한다.

헤들룬드의 논문에서 정리된 버전은 1차원 유한 오토마타에만 적용되었지만, 곧 리처드슨(1972년)에 의해 고차원 정수 격자로 일반화되었으며,[3] 격자에서 이산 집단까지 훨씬 일반화될 수 있다.정리의 중요한 결과 중 하나는 가역성 세포 자동화의 경우, 자동화의 역역학도 세포 자동화로 설명할 수 있다는 것이다.

정의들

알파벳은 세포 자동에서 세포의 상태로 생각될 수 있는 어떤 유한한 기호들의 집합이다.구성은 알파벳에서 기호를 무한대로 배열한 것이다.

..., x−2, x−1, x0, x1, x2, ....

구성에서 위치는 정수, 즉 시퀀스에 있는 기호 중 하나의 색인이다. 위치는 셀룰러 자동화의 셀로 생각할 수 있다.패턴은 유한한 위치 집합과 이들 위치 각각에 대한 기호의 할당이다.

이동 공간은 주어진 알파벳에 걸쳐 가능한 모든 구성의 집합이다.칸토어 토폴로지에 따라 위상학적 공간의 구조가 주어질 수 있는데, 여기서 기본 오픈 세트는 어떤 단일 패턴과 일치하는 구성 집합이고 오픈 세트는 기본 오픈 세트의 임의 조합이다.이 토폴로지에서, 구성 구성까지 함수 f의 끊임 없는 경우에 고정된 패턴 p을 정의하는 근본적인 개방을 설정할 P는 세트 f−1(P)의 구성 지도에 의해 f로 P 수 있는 그 자체에서 설명하는(아마도 무한한)세트 S패턴을 사용하여 속성은 구성에 속하는 f−1(P)만일 근데 어울리는데 a파파S에 있다.

우리가 각각의 상징에 대한 그것의 종전 입장에서 한 자리 이동한 새로운 구성은 y로 구성)변형시킨 변화 공간의 변화 지도는 특정한 연속 함수 s:그, 나는, 의)xi − 1.A기능 f변화 지도 아래equivariant 경우 구성에 변화가 설명한 모든 정수를 위한 것이다.f에 의해시프트 맵과 통근한다. 즉, 모든 구성 x에 대해 f(s)(x) = s(f(x))인 경우여야 한다.직관적으로 이것은 구성의 모든 위치가 다른 모든 위치와 동일한 규칙을 사용하여 f에 의해 업데이트된다는 것을 의미한다.

셀룰러 자동화는 그 위치를 둘러싸고 있는 이전의 고정된 유한한 이웃의 셀 값에만 근거한 구성에서 각 위치의 새로운 값을 계산하기 위한 규칙에 의해 정의되며, 구성의 모든 위치는 동일한 업데이트 규칙에 근거하여 동시에 업데이트된다.즉, 어떤 위치의 새로운 가치는 이전 구성의 무한한 수의 셀에 더 일반적으로 의존하기 보다는 그 근방에 있는 셀의 값들만을 가지고 있는 기능이다.이 규칙을 사용하여 셀룰러 자동화의 구성을 후속 구성으로 매핑하는 함수 f는 모든 위치가 동일한 업데이트 규칙을 사용한다는 가정 하에 반드시 시프트 맵과 관련하여 등가변한다.또한 칸토어 위상에서도 반드시 연속적이다: p가 고정된 패턴이고, 기초적인 오픈 세트 P를 정의한다면, f−1(P)는 유한한 패턴 집합에 의해 정의되며, f가 p를 생성하게 하는 p 근처의 세포에 할당된다.커티스-Hedlund-Lyndon 정리에서는 이 두 가지 특성이 세포 자동화를 정의하기에 충분하다고 기술하고 있다: 모든 연속적인 등가함수는 세포 자동화의 업데이트 규칙이다.

증명

체케리니-실버슈타인과 쿠오르네르트는 커티스-에 대한 다음과 같은 증거를 제공한다.헤들런드-린든 정리.[4]

f가 시프트 공간의 연속적인 시프트 등가함수라고 가정하자.각 구성 x에 대해 p는 f(x)의 위치 0에 나타나는 단일 기호로 구성된 패턴이 되도록 한다.f의 연속성에 의해, q의 외부 위치가 임의로 변경되지만 q 내의 위치가 x의 값에 고정된 경우, f를 적용하는 결과는 위치 0에서 동일하게 유지되는 x의 유한 패턴 q가 존재해야 한다.마찬가지로, X가 Q에x 속하고 Qx, f(x) 및 f(y)의 모든 구성 y에 대해 위치 0에서 동일한 값을 갖는 기본 오픈 세트 Q가x 있어야 한다.이러한 기본 오픈 세트 Qx(가능한 모든 구성 x에 대해)는 시프트 공간의 개방형 커버를 형성한다.그러나, 시프트 공간은 콤팩트한 공간이다: 알파벳을 포인트로 하는 유한한 위상학적 공간의 산물이기 때문에, 타이코노프의 정리로부터 콤팩트함이 따른다.소형성에 의해, 모든 오픈 커버는 유한 서브 커버를 가지고 있다.이 유한 서브커버에 나타나는 유한한 위치 집합은 f를 셀룰러 오토매틱 규칙으로 기술할 때 위치 0의 근방으로 사용할 수 있다.

동일한 증명은 정수 위치 집합을 어떤 이산 그룹 G로 대체했을 때 보다 일반적으로 적용되며, 구성 공간은 G에서 유한 알파벳까지의 함수 집합으로 대체되며, 이동 균일성은 그 자체로 G의 작용에 따른 동일성으로 대체된다.특히 어떤 차원의 정수 그리드에 정의된 셀룰러 오토마타에 적용한다.

무한 확장 알파벳에 대한 counterexample

정수의 2-무한 시퀀스 공간을 고려하고, f(x) = y이면 모든 위치 i, yi = x에i + xi 대해 이 공간부터 그 자체까지 함수 f를 정의한다.이 규칙은 직급마다 같기 때문에 교대조 등가성이 있다.그리고 칸토어 위상에 따라 연속적으로 보여질 수 있다: y의 각 유한 패턴 p에 대해 x에는 값이 p로 복사되는 세포와 함께 p의 세포로 구성되는 p를 생성하도록 강제하는 위치의 최대 두 배까지를 가진 패턴이 있다.그러나, 연속적이고 등변성이 있음에도 불구하고, 어떤 세포의 가치는 잠재적으로 어떤 사전 고정된 유한한 이웃의 세포에만 의존하는 것이 아니라 다른 세포의 가치에 의존할 수 있기 때문에, f는 세포 자동 법칙이 아니다.[4]

가역성 셀룰러 오토마타 적용

셀룰러 자동화는 자동화의 모든 구성이 정확히 하나의 선행자를 가질 때 되돌릴 수 있다고 한다.각 구성을 전임자에 매핑하는 기능 자체가 시프트 공간에서 연속적이고, 시프트 인바리어트(shift-invariant)도 분명하다는 콤팩트성 주장에 따른 것이다.그러므로, 커티스-에 의해.Hedlund-Lyndon 정리, 세포 자동화의 시간 역학 그 자체는 다른 세포 자동자 규칙을 사용하여 생성될 수 있다.[3]그러나 역자동화에서 셀의 주변은 전방자동화에서 동일한 셀의 주변보다 상당히 클 수 있다.[5][6]

일반화

셀룰러 자동화의 정의를 그 위치를 둘러싼 유한하지만 가변적인 근방의 셀 값에 기초하여 구성에서 각 위치의 새로운 값을 계산하는 규칙에 의해 정의되는 지도에 일반화할 수 있다.이 경우 고전적 정의에서와 마찬가지로 지역적 규칙은 모든 세포에 대해 동일하지만, 근린도 그 위치를 둘러싼 구성의 기능이다.

기존의 셀룰러 자동화가 아닌 연속적이고 시프트 등가변성 지도에 대해 위에 제시된 counterexample은 일반화된 셀룰러 자동화의 예다.알파벳이 유한할 때, 일반화된 세포 자동화의 정의는 이동 공간의 압축성으로 인해 세포 자동화의 고전적 정의와 일치한다.

일반화된 셀룰러 오토마타는 소보트카 & 곤살베스(2016년)에 의해 제안되었고, 여기서 이들이 연속적인 시프트 등가성 지도에 해당한다는 것이 증명되었다.

참고 항목

참조

  1. ^ Hedlund, Gustav A. (1969), "Endomorphisms and Automorphisms of the Shift Dynamical Systems", Mathematical Systems Theory, 3 (4): 320–375, doi:10.1007/BF01691062.
  2. ^ Šunić, Zoran (2014), "Cellular automata and groups, by Tullio Ceccherini-Silberstein and Michel Coornaert (book review)", Bulletin of the American Mathematical Society, 51 (2): 361–366, doi:10.1090/S0273-0979-2013-01425-3.
  3. ^ a b Richardson, Daniel (1972), "Tessellations with local transformations", Journal of Computer and System Sciences, 6: 373–388, doi:10.1016/S0022-0000(72)80009-6, MR 0319678.
  4. ^ a b Ceccherini-Silberstein, Tullio; Coornaert, Michel (2010), "Theorem 1.8.1 (Curtis–Hedlund theorem)", Cellular Automata and Groups, Springer Monographs in Mathematics, Springer-Verlag, p. 20, ISBN 978-3-642-14033-4.
  5. ^ Margenstern, Maurice (2007), Cellular Automata in Hyperbolic Spaces - Tome I, Volume 1, Archives contemporaines, p. 134, ISBN 978-2-84703-033-4.
  6. ^ Kari, Jarkko (2005), "Reversible cellular automata" (PDF), Developments in Language Theory, Lecture Notes in Computer Science, vol. 3572, Springer-Verlag, pp. 2–23, doi:10.1007/11505877_5.
  7. ^ Sobottka, Marcelo; Gonçalves, Daniel (2016), A note on the definition of sliding block codes and the Curtis-Hedlund-Lyndon Theorem, arXiv:1507.02180, Bibcode:2015arXiv150702180S.