비결정론적 튜링 기계

비결정론적 튜링 기계(nondeterministic Turing machine, NTM)는 튜링 기계에서 특정 상태에서 움직일 수 있는 상태의 개수가 하나로 정해져 있지 않은 경우를 말한다. 이것은 비결정론적 유한 오토마타와 유사한 개념이다.

이동 가능성이 하나로 정해져 있는 결정론적 튜링 기계와는 반대로, 이 기계에서 이동할 수 있는 상태의 개수는 상황에 따라 다르며, 여러 개가 되거나 아예 없을 수도 있다.

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

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

비결정론적 튜링 기계는 형식적으로 다음과 같이 정의된다.

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

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

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

• 확률적 튜링 기계

• 비결정론적 Multitape 튜링 기계의 C++ 시뮬레이터 (자유 소프트웨어).