카운터 머신(Counter Machine)은 계산 이론 및 형식 언어 이론에서 사용되는 추상적인 계산 모델 중 하나로, 유한 개수의 정수형 카운터(레지스터)와 제한된 명령 집합을 이용해 계산을 수행한다. 가장 널리 알려진 형태는 미스키 카운터 머신(Minsky counter machine)이며, 이는 1961년 마빈 미스키(Marvin Minsky)가 제안한 M-머신(M-machine)과 동등한 모델이다.
정의
카운터 머신은 다음 요소들로 구성된다.
- 상태 집합(Q): 유한 개수의 제어 상태.
- 카운터 집합(C): n개의 정수형 카운터 $c_1, c_2, \dots, c_n$ (통상 $n \ge 1$). 각 카운터는 0 이상의 정수 값을 가진다.
- 명령 집합(Δ): 각 명령은 현재 상태와 선택된 카운터의 값에 따라 다음 중 하나를 수행한다.
- 증가(Incr): 선택된 카운터 $c_i$의 값을 1 증가시킨 후, 지정된 다음 상태로 전이.
- 감소(Decr): 선택된 카운터 $c_i$가 0보다 크면 값을 1 감소시키고 지정된 다음 상태로 전이; 0이면 전이되지 않는다(또는 별도 조건 전이).
- 조건 점프(Zero‑test): 선택된 카운터 $c_i$가 0인지 여부에 따라 두 개의 가능한 다음 상태 중 하나로 전이.
- 시작 상태와 초기 카운터 값: 보통 모든 카운터는 0으로 초기화된 상태에서 시작한다.
이러한 구성에 따라 카운터 머신은 입력에 대해 일련의 상태 변천과 카운터 조작을 수행하며, 최종 상태나 특정 카운터 값에 도달했을 때 계산을 종료한다.
역사·배경
- 미스키 카운터 머신은 1961년 마빈 미스키의 논문 “Recursive Unsolvability of Post’s Problem”에서 소개되었다. 그는 두 개의 카운터만으로도 튜링 머신과 동등한 계산 능력을 가질 수 있음을 증명하였다.
- 이후 Minsky machine, register machine, counter automaton 등으로도 불리며, 다양한 변형(예: 제한된 카운터 수, 제한된 명령어 종류 등)이 제안되었다.
계산 능력
- 카운터 머신은 카운터 수가 두 개 이상이면 튜링 완전성을 갖는다. 즉, 모든 튜링 기계가 수행할 수 있는 계산을 시뮬레이션할 수 있다.
- 카운터가 하나만 있을 경우에는 정규 언어와 같은 제한된 클래스만 인식한다.
주요 변형
| 변형 | 특징 | 계산 능력 |
|---|---|---|
| 이중 카운터 머신 | 두 개의 카운터만 사용 | 튜링 완전 |
| 제한된 카운터 머신 | 카운터 값에 상한을 두는 등 제한 | 일반적으로 비결정적이며 제한된 언어 인식 |
| 비결정적 카운터 머신 | 하나의 명령에 대해 여러 전이 가능 | 비결정적 튜링 머신과 동등 |
| 동시 증감 머신 | 한 명령에서 여러 카운터를 동시에 증감 | 동일한 계산 능력(튜링 완전) |
응용 분야
- 복잡도 이론: 카운터 머신을 이용해 특정 문제의 시간·공간 복잡도 하한을 증명한다.
- 형식 언어: 카운터 자동자(counter automaton)는 문맥 자유 언어와 같은 일부 언어 클래스를 기술하는 데 사용된다.
- 프로그램 검증: 제한된 카운터 머신 모델을 기반으로 프로그램의 정합성을 검증하는 도구가 개발되었다.
관련 개념
- 튜링 머신(Turing Machine)
- 레지스터 머신(Register Machine)
- 스택 머신(Pushdown Automaton)
- Minsky Machine
참고 문헌
- M. Minsky, Recursive Unsovlability of Post’s Problem, 1961.
- H. Sipser, Introduction to the Theory of Computation, 2nd ed., 2012.
- D. C. Kozen, Automata and Computability, 1997.
위 내용은 현재까지 확인된 학술 자료와 교육용 서적을 바탕으로 정리되었습니다.