유한 상태와 전이

상태와 규칙을 함께 지정하기

세 상태 S={0,1,2}와 고정된 결정적 전이 함수 T:S→S를 생각합니다. 매 단계 sₜ₊₁=T(sₜ)입니다. 초기 상태만 같아도 T가 다르면 궤적은 달라집니다. 반대로 같은 T와 같은 상태를 다시 만나면 이후 궤적은 반드시 같습니다.

상태 번호는 이름입니다. 2가 1보다 두 배 크거나 두 정점 사이의 그림 길이가 이동 시간이 되는 것은 아닙니다. 이 실습은 매 전이를 이산 한 단계로 셉니다. 확률, 에너지, 연속 물리 시간은 모형에 포함되지 않습니다.

하나의 코드에 함수 전체 저장하기

세 입력 각각의 다음 상태가 0,1,2 중 하나이므로 전이 함수는 3³=27개입니다. 실습은

로 함수를 저장합니다. 코드 7은 T(0)=1,T(1)=2,T(2)=0이고 3-순환입니다. 코드 17은 T=(2,2,1)입니다. 정수 코드를 바꾸면 어떤 전이가 달라졌는지 수치 표와 화살표를 함께 읽으세요.

각 정점에는 나가는 화살표가 정확히 하나 있습니다. 자기 간선도 허용하며 고정점을 뜻합니다. 앞의 단순 방향 그래프 실습과 달리 여기에는 자기 간선을 허용합니다.

함수 합성과 궤적

T⁰는 항등 함수, T²=T∘T이고 일반적으로 sₙ=Tⁿ(s₀)입니다. 코드 7에서 0을 시작하면 0,1,2,0,1,2,…이므로 T⁵(0)=2입니다. 표의 첫 행 t=0은 아직 전이하지 않은 상태입니다. N번 전이하면 표에 N+1개 관측이 있습니다.

함수 합성은 결합법칙을 만족하므로 Tᵐ⁺ⁿ=Tᵐ∘Tⁿ입니다. 그러나 서로 다른 함수 U,T는 일반적으로 교환하지 않습니다. U∘T=T∘U를 추가 근거 없이 가정하지 마세요.

유한성이 반복을 보장한다

세 가능한 상태에서 네 관측 s₀,s₁,s₂,s₃를 만들면 비둘기집 원리에 의해 같은 상태가 두 번 나옵니다. sᵢ=sⱼ,i<j라면 결정성 때문에 모든 k≥0에서 sᵢ₊ₖ=sⱼ₊ₖ입니다. 이는 함수 적용과 귀납법으로 증명됩니다.

따라서 궤적은 유한 과도 구간과 주기 구간으로 나뉩니다. μ는 처음 순환에 들어가는 시점이고 λ≥1은 그 순환의 최소 양의 주기입니다.

관측한 N이 짧아도 실습은 전이 함수 전체를 따라 처음 반복이 나올 때까지 계산해 μ,λ를 구합니다. 화면에 표시한 N행만 보고 추측하는 것이 아닙니다.

과도 구간과 고정점

코드 17에서 시작 상태 0의 궤적은 0,2,1,2,1,…입니다. 0은 과도 상태이고 μ=1,λ=2입니다. 주기 2라고 첫 관측부터 두 단계마다 같아지는 것은 아닙니다.

코드 26은 모든 상태를 2로 보냅니다. 시작 0이면 0,2,2,…이고 μ=1,λ=1입니다. 처음부터 2에서 시작하면 μ=0,λ=1입니다. 고정점의 최소 양의 주기는 0이 아니라 1입니다. 같은 전이 함수도 초기 상태에 따라 과도 길이와 방문하는 순환이 달라질 수 있습니다.

모형의 가정이 바뀌면

시간마다 전이 함수가 바뀌거나 상태에 포함하지 않은 외부 입력이 있다면 같은 상태 번호가 같은 미래를 보장하지 않습니다. 난수 전이에서는 같은 상태를 재방문해도 실제 다음 표본은 달라질 수 있습니다. 외부 입력이나 시계를 상태에 포함하는 확대 모형이 가능한지 검토해야 합니다.

AI 에이전트의 워크플로, 프로토콜 검증, 유한 정밀도 계산의 반복을 분석할 때 이 관점이 유용합니다. 연속 신경망의 상태 공간이 무한하다면 이 작은 유한성 논증만으로 유한 주기 수렴을 주장할 수 없습니다. 유한 정밀도 구현도 난수·외부 입출력·시각 의존성을 포함해야 정확한 유한 상태 모형이 됩니다.

확인 문제와 답

1. 세 상태 결정계에서 최대 서로 다른 방문 상태 수는? 3입니다.
2. 코드 0에서 시작 2이면? 2,0,0,…이고 μ=1,λ=1입니다.
3. 같은 함수라도 초기 상태를 바꾸면 μ가 바뀔 수 있나요? 그렇습니다. 코드 26이 예입니다.
4. N=0이면 상태는? s₀이며 반복 횟수 0과 빈 상태 집합을 구분합니다.

추가 읽기: MIT Mathematics for Computer Science와 MIT Theory of Computation. 유한 결정계의 궤적 예제는 직접 구성했습니다.