무어 기계

계산 이론에서 무어 기계 또는 무어 머신(Moore machine)은 현재 출력값이 현재 상태에 의해서만 결정되는 유한 상태 기계이다. 이는 출력값이 현재 상태와 입력값 모두에 의해 결정되는 밀리 기계와는 대조적이다. 다른 유한 상태 기계와 마찬가지로 무어 기계에서 입력은 일반적으로 다음 상태에 영향을 미친다. 따라서 입력은 간접적으로 후속 출력에 영향을 미칠 수 있지만 현재 또는 즉각적인 출력에는 영향을 미치지 않는다. 무어 기계는 1956년 논문 "순차 기계에 대한 사고 실험"에서 이 개념을 제시한 에드워드 F. 무어의 이름을 따서 명명되었다.^[1]

형식적 정의

무어 기계는 다음으로 구성된 6-튜플 $(S,s_{0},\Sigma ,O,\delta ,G)$ 로 정의할 수 있다.

상태의 유한 집합 $S$
$S$ 의 요소인 시작 상태(초기 상태라고도 함) $s_{0}$
입력 알파벳이라고 불리는 유한 집합 $\Sigma$
출력 알파벳이라고 불리는 유한 집합 $O$
상태와 입력 알파벳을 다음 상태로 매핑하는 전이 함수 $\delta :S\times \Sigma \rightarrow S$
각 상태를 출력 알파벳으로 매핑하는 출력 함수 $G:S\rightarrow O$

"시간에 따른 진화"는 이 추상화에서 상태 기계가 이산적인 "타이머 틱" $t_{0},t_{1},t_{2},...$ 에서 시간 변화 입력 기호를 참조하고 이상적인 순간에 내부 구성에 따라 반응하거나, 상태 기계가 다음 입력 기호(FIFO에서와 같이)를 기다리고 도착할 때마다 반응함으로써 실현된다.

무어 기계는 제한된 유형의 유한 상태 변환기로 간주될 수 있다.

시각적 표현

표

상태 전이표는 전이 관계 $\delta :S\times \Sigma \rightarrow S$ 의 모든 삼중항을 나열하는 표이다.

다이어그램

무어 기계의 상태도 또는 무어 다이어그램은 각 상태에 출력값을 연결하는 상태도이다.

밀리 기계와의 관계

무어 기계와 밀리 기계는 모두 유한 상태 기계의 한 유형이므로 동일한 표현력을 갖는다. 즉, 두 유형 모두 정규 언어를 구문 분석하는 데 사용할 수 있다.

무어 기계와 밀리 기계의 차이점은 후자에서 전이의 출력은 현재 상태와 현재 입력( $G$ 의 도메인으로 $S\times \Sigma$ )의 조합에 의해 결정된다는 점이다. 단순히 현재 상태( $G$ 의 도메인으로 $S$ )와는 다르다. 상태도로 표현하면 다음과 같다.

무어 기계의 경우 각 노드(상태)에는 출력값이 레이블로 지정된다.
밀리 기계의 경우 각 아크(전이)에는 출력값이 레이블로 지정된다.

모든 무어 기계 $M$ 은 동일한 상태와 전이, 그리고 출력 함수 $G(s,\sigma )=G_{M}(\delta _{M}(s,\sigma ))$ 를 가진 밀리 기계와 동등하다. 이 함수는 각 상태-입력 쌍 $(s,\sigma )$ 를 가져와 $G_{M}(\delta _{M}(s,\sigma ))$ 를 산출하며, 여기서 $G_{M}$ 은 $M$ 의 출력 함수이고 $\delta _{M}$ 은 $M$ 의 전이 함수이다.

그러나 모든 밀리 기계를 동등한 무어 기계로 변환할 수 있는 것은 아니다. 일부는 시간적으로 출력이 시프트된 거의 동등한 무어 기계로만 변환할 수 있다. 이는 입력/출력 쌍을 형성하기 위해 상태 레이블이 전이 레이블과 짝을 이루는 방식 때문이다. 상태 $s_{i}$ 에서 상태 $s_{j}$ 로의 전이 $s_{i}\rightarrow s_{j}$ 를 고려하자. 전이 $s_{i}\rightarrow s_{j}$ 를 유발하는 입력은 에지 $(s_{i},s_{j})$ 에 레이블로 지정된다. 해당 입력에 해당하는 출력은 상태 $s_{i}$ 의 레이블이다.^[2] 이것이 전이의 원본 상태임을 주목하라. 따라서 각 입력에 대해 출력은 입력이 수신되기 전에 이미 고정되어 있으며 현재 상태에만 의존한다. 이것은 E. 무어의 원래 정의이다. 전이 $s_{i}\rightarrow s_{j}$ 에 대한 출력으로 상태 $s_{j}$ 의 레이블을 사용하는 것은 흔한 실수이다.

예시

입력/출력 수에 따른 유형.

단순

단순 무어 기계는 하나의 입력과 하나의 출력을 갖는다.

윤곽선 검출기 (XOR 사용)
이진 가산기
클록 동기 순차 시스템 (전역 클록 신호가 변경될 때만 상태가 변경되는 제한된 형태의 무어 기계)

대부분의 디지털 전자 시스템은 클록 동기 순차 시스템으로 설계된다. 클록 동기 순차 시스템은 전역 클록 신호가 변경될 때만 상태가 변경되는 제한된 형태의 무어 기계이다. 일반적으로 현재 상태는 플립플롭에 저장되며, 전역 클록 신호는 플립플롭의 "클록" 입력에 연결된다. 클록 동기 순차 시스템은 메타 안정성 문제를 해결하는 한 가지 방법이다. 일반적인 전자 무어 기계에는 현재 상태를 출력(람다)으로 디코딩하는 조합 논리 체인이 포함된다. 현재 상태가 변경되는 즉시 이러한 변경은 해당 체인을 통해 파급되며 거의 즉시 출력이 업데이트된다. 이러한 변경이 체인을 통해 파급되는 짧은 기간 동안 출력에 글리치가 발생하지 않도록 보장하는 설계 기술이 있지만, 대부분의 시스템은 이 짧은 전이 시간 동안의 글리치가 무시되거나 관련이 없도록 설계된다. 그러면 무어 기계가 다시 상태를 변경할 때까지 출력은 무기한으로 동일하게 유지된다(LED는 계속 밝게 켜지고, 모터에는 전원이 계속 연결되며, 솔레노이드는 계속 에너지가 공급되는 등).

예제

순차 네트워크에는 하나의 입력과 하나의 출력이 있다. 출력은 적어도 두 개의 0과 두 개의 1이 입력으로 발생하면 1이 되고 그 이후로 계속 1로 유지된다.

위 설명에 대한 9개의 상태를 가진 무어 기계는 오른쪽에 표시되어 있다. 초기 상태는 상태 A이고 최종 상태는 상태 I이다. 이 예제의 상태 표는 다음과 같다.

현재 상태	입력	다음 상태	출력
A	0	D	0
A	1	B	0
B	0	E	0
B	1	C	0
C	0	F	0
C	1	C	0
D	0	G	0
D	1	E	0
E	0	H	0
E	1	F	0
F	0	I	0
F	1	F	0
G	0	G	0
G	1	H	0
H	0	H	0
H	1	I	0
I	0	I	1
I	1	I	1

복잡

더 복잡한 무어 기계는 여러 입력과 여러 출력을 가질 수 있다.

사고 실험

무어의 1956년 논문 "순차 기계에 대한 사고 실험"에서,^[1] $(n;m;p)$ 오토마타(또는 기계) $S$ 는 $n$ 개의 상태, $m$ 개의 입력 기호, $p$ 개의 출력 기호를 갖는 것으로 정의된다. $S$ 의 구조와 $S$ 를 이용한 실험에 대해 9가지 정리가 증명되었다. 나중에 " $S$ 기계"는 "무어 기계"로 알려졌다.

논문 말미의 "추가 문제" 섹션에서 다음 작업이 언급되었다.

직접적으로 이어지는 또 다른 문제는 정리 8과 9에서 주어진 경계를 개선하는 것이다.

무어의 정리 8은 다음과 같이 정식화되었다.

임의의 $(n;m;p)$ 기계 $S$ 가 주어지고, 그 두 상태가 서로 구별될 수 있다면, 실험 종료 시 $S$ 의 상태를 결정하는 길이 ${\tfrac {n(n-1)}{2}}$ 의 실험이 존재한다.

1957년, A. A. 카라추바는 무어의 "정리 8" 실험 길이의 경계 개선 문제를 완전히 해결한 다음 두 정리를 증명했다.

정리 A. $S$ 가 $(n;m;p)$ 기계이고, 그 두 상태가 서로 구별될 수 있다면, 실험 종료 시 $S$ 의 상태를 결정할 수 있는 최대 길이 ${\tfrac {(n-1)(n-2)}{2}}+1$ 의 분기 실험이 존재한다.

정리 B. 두 상태가 서로 구별될 수 있는 $(n;m;p)$ 기계가 존재하며, 실험 종료 시 기계의 상태를 확립하는 가장 짧은 실험의 길이는 ${\tfrac {(n-1)(n-2)}{2}}+1$ 과 같다.

정리 A와 B는 4학년 학생 A. A. 카라추바의 "오토마타 이론의 한 문제에 대하여"라는 졸업 논문의 기초로 사용되었으며, 이 논문은 1958년 모스크바 국립 대학교 역학 및 수학 학부 학생 작품 경연대회에서 추천서를 받아 특별히 언급되었다. 카라추바의 논문은 1958년 12월 17일에 Uspekhi Mat. Nauk 저널에 제출되었고 1960년 6월에 그곳에 출판되었다.^[3]

현재(2011년)까지 카라추바의 실험 길이에 대한 결과는 오토마타 이론과 계산 복잡도 이론의 유사한 문제 모두에서 유일한 정확한 비선형 결과이다.

같이 보기

각주

1 2 Moore, Edward F (1956). 《Gedanken-experiments on Sequential Machines》. 《Automata Studies, Annals of Mathematical Studies》 (Princeton, N.J.: Princeton University Press). 129–153쪽.
↑ Lee, Edward Ashford; Seshia, Sanjit Arunkumar (2013). 《Introduction to Embedded Systems》 1.08판. UC Berkeley: Lulu.com. ISBN 9780557708574. 2014년 7월 1일에 확인함.
↑ Karatsuba, A. A. (1960). 《Solution of one problem from the theory of finite automata》. 《Uspekhi Mat. Nauk》. 157–159쪽.

추가 자료

Conway, J.H. (1971). 《Regular algebra and finite machines》. London: Chapman and Hall. ISBN 0-412-10620-5. Zbl 0231.94041.
Moore E. F. Gedanken-experiments on Sequential Machines. Automata Studies, Annals of Mathematical Studies, 34, 129–153. Princeton University Press, Princeton, N.J.(1956).
Karatsuba A. A. Solution of one problem from the theory of finite automata. Usp. Mat. Nauk, 15:3, 157–159 (1960).
Karatsuba A. A. Experimente mit Automaten (German) Elektron. Informationsverarb. Kybernetik, 11, 611–612 (1975).
Karatsuba A. A. 연구 목록.

외부 링크

위키미디어 공용에 무어 기계 관련 미디어 분류가 있습니다.

[gedanken-1] 1 2 Moore, Edward F (1956). 《Gedanken-experiments on Sequential Machines》. 《Automata Studies, Annals of Mathematical Studies》 (Princeton, N.J.: Princeton University Press). 129–153쪽.

[2] Lee, Edward Ashford; Seshia, Sanjit Arunkumar (2013). 《Introduction to Embedded Systems》 1.08판. UC Berkeley: Lulu.com. ISBN 9780557708574. 2014년 7월 1일에 확인함.

[3] Karatsuba, A. A. (1960). 《Solution of one problem from the theory of finite automata》. 《Uspekhi Mat. Nauk》. 157–159쪽.

[1]

[2]

[3]