기호 동역학

계산물리 물리 마지막 수정: 2026-08-19 04:12:41

1. 개요[편집]

기호 동역학 Symbolic dynamics
기원	Hadamard (1898) · Morse–Hedlund (1938, 용어 확립)
대상	기호열 공간 위의 이동사상 σ
핵심 도구	마르코프 분할 · 전이행렬 · 금지어 목록
위상 엔트로피	log ρ(A) (A = 전이행렬, ρ = 스펙트럼 반경)
주기점 개수	tr(Aⁿ)
계층	유한형 부분이동 ⊂ 소픽 이동 ⊂ 일반 부분이동
공학적 후손	런렝스 제한 부호 · 제약 채널 용량

궤도를 좇지 말고, 궤도가 남긴 발자국의 문자열을 세라.

기호 동역학(symbolic dynamics)은 상태공간을 유한(또는 가산) 개 조각으로 나누고 궤도가 지나간 조각의 번호를 시간 순으로 적어, 연속체 위의 동역학을 문자열 공간 위의 한 칸 밀기(shift)로 바꿔 버리는 방법론이다. 미분방정식의 세계에서 조합론과 선형대수의 세계로 넘어가는 환전소라고 보면 정확하다.

무엇을 얻는가. 주기궤도의 개수는 행렬의 대각합이 되고, 위상 엔트로피는 행렬의 스펙트럼 반경의 로그가 되며, “비주기 궤도가 비가산 개 존재한다” 같은 진술은 문자열을 세는 초등적 논증으로 내려온다. 카오스를 증명한다는 작업이 대체로 “이동사상과의 위상 공액을 찾는다”로 정식화되는 이유가 이것이다.

이 문서는 그 환전소의 환율표를 다룬다. 구체적 사상에서 공액을 실제로 조립하는 과정은 스메일 말굽이, 공액이 무엇을 보존하는지는 위상 공액이, 지수 증가율의 미분기하적 측면은 랴푸노프 지수가 이미 맡고 있으므로 여기서는 반복하지 않는다.

2. 여정 — 궤도에 주소를 붙이기[편집]

사상 $f : X \to X$ 와 분할 $\mathcal{P} = \{P_0, \dots, P_{m-1}\}$ 이 있다고 하자. 점 $x$ 의 여정(itinerary)은

h(x) = (a_0, a_1, a_2, \dots), \qquad a_n = i \iff f^{\,n}(x) \in P_i

이다. $f$ 가 가역이면 음의 시각까지 붙여 양방향 수열 $(a_n)_{n\in\mathbb{Z}}$ 을 쓴다. 정의에 의해

h(f(x)) = \sigma(h(x)), \qquad \sigma(a)_n = a_{n+1}

즉 사상을 한 번 적용하는 것 = 문자열을 한 칸 미는 것이다. 이 등식 하나가 기호 동역학의 전부이고, 나머지는 전부 “이 $h$ 가 얼마나 좋은 대응인가”를 따지는 일이다.

기호열 전체가 사는 공간 $\Sigma_m = \{0,\dots,m-1\}^{\mathbb{Z}}$ 에 거리

d(a,b) = \sum_{n\in\mathbb{Z}} \frac{|a_n - b_n|}{2^{|n|}}

를 주면 콤팩트 거리공간이 되고, “가깝다 = 원점 근처 자릿수가 오래 일치한다”는 직관과 맞아떨어진다. $\sigma$ 는 이 거리에 대해 연속이며, 쌍 $(\Sigma_m, \sigma)$ 를 완전 이동(full shift)이라 부른다.

$h$ 가 전단사 연속이면 $f$ 와 $\sigma$ 가 위상 공액이고, 이때 분할을 생성 분할(generating partition)이라 한다. 대부분의 실전에서 이 조건은 성립하지 않고, 잘해야 유한 대 일 준공액이 얻어진다. 언제 얼마나 깨지는지가 이 분야에서 가장 손이 많이 가는 부분이며, 뒤의 마르코프 분할 절에서 다룬다.

3. 유한형 부분이동 — 금지어 목록[편집]

실제 계에서는 모든 문자열이 나오지 않는다. 어떤 조각에서 다른 조각으로 갈 수 없으면 그 두 글자의 연접은 검열된다. 금지어의 목록 $\mathcal{F}$ 를 정하고

\Sigma_{\mathcal{F}} = \{a \in \Sigma_m : a \text{ 안에 } \mathcal{F} \text{ 의 단어가 부분열로 나타나지 않음}\}

로 잡은 것이 부분이동(subshift)이다. $\mathcal{F}$ 를 유한 개로 잡을 수 있으면 유한형 부분이동(subshift of finite type, SFT)이라 부른다.

여기서 결정적인 단순화가 일어난다. 금지어의 최대 길이가 $L$ 이면 길이 $L-1$ 짜리 블록을 새 알파벳으로 삼아 다시 쓸 수 있고(고차 블록 재부호화), 그러면 모든 SFT는 길이 2 금지어만으로 기술되는 1단계 SFT와 동형이 된다. 즉 SFT는 결국

A_{ij} = \begin{cases} 1 & i \to j \text{ 허용}\\ 0 & \text{금지}\end{cases}

인 0-1 전이행렬 하나, 혹은 같은 말로 유향 그래프 하나로 완전히 결정된다. 문자열은 그 그래프 위의 무한 경로이고, 동역학은 경로를 따라 한 칸 걷는 것이다.

교과서적 예가 황금평균 이동이다. 금지어를 $\{11\}$ 하나로 두면

A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}, \qquad \rho(A) = \frac{1+\sqrt5}{2} = \varphi

이다. “1 다음엔 반드시 0” 이라는 한 줄짜리 문법이 연분수에서 익숙한 그 황금비를 다시 불러낸다.

4. 전이행렬이 다 한다[편집]

SFT의 동역학적 양들이 전부 $A$ 의 선형대수로 계산된다는 것이 이 틀의 밥값이다.

단어 개수. 길이 $n$ 인 허용 단어의 개수는 $A^{n-1}$ 의 모든 성분의 합이다.
주기점 개수. $|\mathrm{Fix}(\sigma^n)| = \operatorname{tr}(A^n) = \sum_i \lambda_i^n$ . 주기궤도를 세는 일이 고유값 문제가 된다.
제타 함수. 주기점 개수를 모은 동역학적 제타 함수가 유리함수로 닫힌다.

\zeta_\sigma(t) = \exp\!\left(\sum_{n\ge1}\frac{|\mathrm{Fix}(\sigma^n)|}{n}t^n\right) = \frac{1}{\det(I - tA)}

위상 엔트로피. $A$ 가 기약(irreducible)이면

h_{\mathrm{top}}(\sigma_A) = \log \rho(A)

로, 페론-프로베니우스 고유값의 로그다. 완전 2-이동은 $A$ 가 전부 1인 $2\times2$ 행렬이라 $\rho=2$ , 엔트로피 $\log 2$ — 스메일 말굽의 그 값이다.

엔트로피가 스펙트럼 반경이라는 사실의 실용적 함의가 크다. 엔트로피 계산이 거듭제곱법 한 번으로 끝난다. 행렬이 수천 차원이어도 희소하므로, 궤도를 수백만 스텝 적분해 랴푸노프 지수를 추정하는 것보다 훨씬 빠르고 오차 통제도 명확하다. 물론 그 전이행렬을 만드는 일이 전부 사람 몫이라는 것이 함정이다.

5. 소픽 이동 — 금지어가 무한히 많을 때[편집]

금지어 목록이 유한하지 않으면 SFT가 아니다. 대표 반례가 짝수 이동(even shift)으로, 연속한 두 개의 1 사이에 오는 0의 개수가 항상 짝수여야 한다는 제약이다. 금지어가 $101, 10001, 1000001, \dots$ 로 무한히 많아 SFT가 될 수 없다.

그런데 이 제약은 상태 두 개짜리 라벨 붙은 그래프로 완전히 표현된다. 정점이 “지금까지 본 0의 개수의 홀짝”을 기억하고, 간선에 출력 기호를 붙이는 식이다. 이렇게 유한 그래프의 간선 라벨 열로 표현되는 부분이동을 소픽 이동(sofic shift)이라 하며¹, 계층은

\text{SFT} \subsetneq \text{소픽} \subsetneq \text{일반 부분이동}

이다. 소픽 이동은 SFT의 인자(factor), 즉 연속 전사 준공액 상이라는 특징으로도 정의된다. 엔트로피는 우측 분해 가능한(right-resolving) 표현 그래프의 인접행렬에서 똑같이 $\log\rho$ 로 나온다. 요컨대 유한 개의 기억 상태만 있으면 문법이 무한해도 선형대수가 계속 작동한다 — 유한 상태 기계 이론과 정확히 같은 경계선이다.

6. 마르코프 분할 — 대응이 깨지는 지점[편집]

이제 어려운 쪽이다. 임의의 분할을 쓰면 여정과 궤도의 대응이 형편없이 망가진다. 궤도를 되살릴 수 있으려면 분할이 마르코프 성질을 가져야 한다. 대략 “각 조각의 상은 다른 조각을 불안정 방향으로 온전히 가로질러 덮거나, 아예 만나지 않는다”는 조건이다. 조각을 안정·불안정 방향에 평행한 변으로 만든 평행사변형으로 잡는 것이 표준 처방이다.

존재성의 역사가 이 분야의 뼈대다.

애들러-바이스(1967) — 쌍곡 원환면 자기동형(고양이 사상)에 대해 명시적 마르코프 분할을 구성했다.
시나이(1968) — 아노소프 미분동형 일반으로 확장.
보웬(1970) — 공리 A 기본집합으로 확장. 이로써 균등 쌍곡계 전반이 SFT의 인자로 환원된다.

대가도 명확하다. 부호화 사상 $h$ 는 전사이고 유한 대 일이지만 단사가 아니다. 조각의 경계에 놓인 점은 코드를 두 개 이상 갖는다. 그래서 얻어지는 것은 공액이 아니라 준공액이고, 이 유한 중복이 엔트로피와 주기점 세기에는 영향을 주지 않지만 측도론적 논의에서는 매번 따로 처리해야 한다. 게다가 보웬(1978)이 보인 바에 따르면 3차원 이상 아노소프계의 마르코프 분할 경계는 매끄러울 수 없다 — 프랙탈 경계가 불가피하다.²

1차원 단봉 사상에서는 사정이 훨씬 구체적이다. 임계점 $c$ 를 기준으로 $L$ (왼쪽), $R$ (오른쪽)로 부호화하면, 어떤 문자열이 실제 궤도에 대응하는지를 반죽열(kneading sequence) 하나가 결정한다. 밀너-서스턴의 반죽 이론에 따르면 임계값 $f(c)$ 의 여정 $K(f)$ 가 상한 역할을 하고, 문자열의 모든 이동상이 부호 사전순으로 $K(f)$ 를 넘지 않을 때만 허용된다. 넘는 것이 곧 검열된 단어다. 완전 텐트 사상(기울기 2)에서는 검열이 하나도 없어 허용 단어가 완전 2-이동 전체이고, 기울기 $s$ 를 낮추면 허용 단어 집합이 단조적으로 줄어들며 엔트로피가 $\log s$ 로 따라 내려간다. 로지스틱 사상의 엔트로피가 매개변수에 대해 단조 증가한다는 유명한 결과가 이 순서 구조에서 나오고, 어떤 주기가 어떤 주기를 강제하는지에 대한 사르코프스키 정리도 같은 뿌리다.

한 가지 덧붙이면, 알파벳이 가산 무한이어도 이 틀은 살아 있다. 가우스 사상 $G(x) = \{1/x\}$ 의 여정이 정확히 연분수 전개의 부분몫 $a_n = \lfloor 1/x_n \rfloor$ 이다. 연분수 이론 전체가 사실은 기호 동역학이었다는 뜻이다.

7. 제약 부호 — 이 이론이 밥벌이를 한 곳[편집]

기호 동역학이 순수수학 밖에서 실제로 돈을 번 곳은 자기·광 저장장치다. 하드디스크나 CD에 비트를 그대로 쓰면 안 된다. 1이 연달아 붙으면 자화 반전이 너무 잦아 신호가 뭉개지고, 0이 너무 길게 이어지면 클럭 복원이 풀린다. 그래서 “연속한 1 사이의 0의 개수는 최소 $d$ 개, 최대 $k$ 개”라는 제약을 걸고 데이터를 그 제약을 만족하는 문자열로 번역해 기록한다. 이것이 $(d,k)$ 런렝스 제한 부호이며, 허용 문자열의 집합은 정확히 하나의 SFT다.

여기서 채널의 용량은 다름 아닌 그 SFT의 위상 엔트로피다.

C(d,k) = \log_2 \rho(A_{d,k}) \quad [\text{기호당 비트}]

$(1,\infty)$ 제약은 금지어가 $\{11\}$ 뿐이라 앞서 본 황금평균 이동이고, 용량은 $\log_2\varphi \approx 0.6942$ 다. 실무에서 쓰이는 값 몇 개를 보면 $C(2,7) \approx 0.5174$ , $C(2,10) \approx 0.5418$ , $C(1,7) \approx 0.6793$ 이다.

그리고 이 숫자가 그대로 설계 기준이 된다. 부호율 $p/q$ 인 유한상태 부호기가 존재할 필요충분조건이 $p/q \le C(d,k)$ 라는 것이 애들러-코퍼스미스-하스너(1983)의 상태 분할(state splitting) 정리이며, 조건이 만족되면 부호기를 구성하는 알고리즘까지 준다. 초기 하드디스크의 $(2,7)$ 부호가 하필 부호율 $1/2$ 인 이유가 여기 있다 — 용량 0.5174가 0.5보다 아슬아슬하게 크기 때문이다. CD의 EFM은 $(2,10)$ 제약이고 용량 0.5418에 대해 8/17의 실효 부호율을 쓴다. 위상 엔트로피라는 추상적 불변량이 IBM의 특허와 CD 규격서에 그대로 박혀 있는 셈이다.³

8. 수치적으로 쓸 때 조심할 것[편집]

생성 분할을 찾는 것이 진짜 일이다. 논문에서 “기호 동역학으로 환원하면”이라는 문장을 만나면, 그 앞에 분할을 구성하느라 몇 페이지가 들어갔는지 확인할 만하다. 대부분의 계에는 유한 생성 분할이 아예 없다.
분할이 틀리면 엔트로피가 과대평가된다. 임계점이나 접힘선을 지나지 않는 엉뚱한 경계로 자르면, 서로 다른 궤도가 같은 코드를 받는 대신 같은 궤도가 여러 코드를 받아 허용 단어 수가 부풀어 오른다. 시계열을 중앙값으로 이분해 만든 부호열의 엔트로피를 그대로 인용하는 것은 위험하다.
유한 길이 효과. 길이 $n$ 단어의 개수 $N(n)$ 에서 $\log N(n)/n$ 으로 엔트로피를 추정하면, 표본 수가 $e^{hn}$ 규모로 필요해 $n$ 을 조금만 키워도 통계가 말라 버린다. 전이행렬을 만들 수 있으면 스펙트럼 반경을 직접 계산하는 쪽이 언제나 낫다.
컴퓨터 보조 증명과의 궁합이 좋다. 구간 해석으로 “사각형 $N_i$ 의 상이 $N_j$ 를 가로질러 덮는다”는 덮음 관계를 엄밀하게 검증하면, 그 결과가 곧 전이행렬이고 그로부터 SFT의 존재가 정리로 따라온다. 부동소수점 그림을 보고 “말굽처럼 보인다”고 말하는 것과 질적으로 다른 결론이 여기서 나온다.
엔트로피는 위상적 양이지 물리적 양이 아니다. 자연측도에 대한 콜모고로프-시나이 엔트로피는 이보다 작을 수 있고, 두 값을 섞어 쓰면 곧바로 틀린다. 변분 원리에 따르면 위상 엔트로피는 모든 불변측도의 측도 엔트로피의 상한이다.

9. 관련 문서[편집]

sofic 은 “유한한”을 뜻하는 히브리어에서 벤저민 와이스가 만든 조어다. “유한형은 아닌데 유한한 것에서 유한 번에 나온다” 정도의 뉘앙스인데, 처음 보면 sonic 오타처럼 생겨서 검색이 잘 안 된다는 것이 이 용어의 유일한 실무적 단점이다. ↩
이 결과가 은근히 킹받는다. 매끄러운 사상, 매끄러운 다양체, 균등 쌍곡성까지 전부 갖춰 놓고 코드를 붙이려는 순간 조각의 경계가 프랙탈이 되어야만 한다는 것이다. 깔끔한 대수 구조를 얻는 대가로 기하 쪽에 지저분함을 몰아준다고 이해하면 마음이 편하다. ↩
그래서 이 바닥 논문은 정보이론 학회지와 동역학계 학회지에 같은 정리를 다른 언어로 싣는 일이 잦다. 한쪽은 “제약 채널의 용량”, 다른 쪽은 “부분이동의 위상 엔트로피”라고 부르는데 계산식은 글자 하나 다르지 않다. 학제간 연구의 모범 사례이자, 같은 것에 두 개의 이름을 붙여 놓고 20년쯤 서로 모르고 지낸 사례이기도 하다. ↩