비결정론적 튜링 기계

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

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

정의

비결정론적 튜링 기계는 다음과 같이 표현된다.

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

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

• $Q$ : 상태의 유한집합
• $\Sigma$ : 심볼(테이프에 사용되는 알파벳)의 유한집합
• $\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$은 오른쪽 방향 시프트이다.

같이 보기

• 확률적 튜링 기계

외부 링크

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