비결정론적 튜링 기계

위키백과 ― 우리 모두의 백과사전.

이 문서는 en:Non-deterministic Turing machine에서 한국어로 번역 중입니다. 원문은 글 안에 주석 처리되어 있습니다. 같이 번역해 주세요.

전산학에서, 일반적인 (결정론적) 튜링 기계 (deterministic Turing machine, 줄여서 DTM)는 현재 상태에서 다음 상태로 천이(遷移)할때 다음 상태가 유일하게 결정된다. 정확히 말하자면, 현재 헤드가 위치한 테이프의 심볼이 s이고 현재 상태가 q라면 여기에서 다음 명령 (s', q', d)가 유일하게 결정된다. 이때 s'는 헤드가 테이프에 쓰는 심볼이며 q'는 컴퓨터의 다음 상태, d는 다음 단계에 테이프를 왼쪽으로 움직일지 오른쪽으로 움직일지 방향을 지정하는 것이다.

이에 반해 비결정론적 튜링 기계(non-deterministic Turing machine, 줄여서 NTM)는 다음 명령 (s', q', d)가 하나 이상이거나 아예 없을 수도 있다. 이것은 각 계산 단계마다 컴퓨터가 '가지치기'를 해서 각각 병렬적으로 계산을 한다고 상상하면 된다. 결정론적 튜링 기계는 유일한 계산 경로를 따르지만, 비결정론적 튜링 기계는 계산 경로가 트리 형태가 된다. 트리의 여러 가지(branch) 중의 한 곳에서 "accept" 상태가 되어 계산이 끝나면, 비결정론적 튜링 기계가 입력을 받아들인다(accept)고 한다. 엄밀한 정의는 다음과 같다.

k 개의 테이프를 가진 비결정론적 튜링 기계는 다음과 같이 표현된다.

$M=(Q, \Sigma, \iota, \sqcup, A, \delta)$

각각의 기호는 다음을 의미한다.

$Q$ : 상태의 유한집합
$Σ$ : 심볼(테이프에 사용되는 알파벳)의 유한집합
$\iota \in Q$ : 초기상태
$\sqcup$ : 빈 심볼 ( $\sqcup \in \Sigma$ )
$A \subseteq Q$ : 최종 상태의 유한집합
$\delta: Q \times \Sigma \rightarrow \mathcal{P} \left( Q \times \Sigma \times \{L,R\} \right)$ : '전이함수'라 불리는 부분함수. L은 왼쪽 방향 시프트이고 R은 오른쪽 방향 시프트이다.