비 결정적 튜링 머신
비 결정적 튜링 머신에서는 모든 상태와 기호에 대해 TM이 가질 수있는 작업 그룹이 있습니다. 따라서 여기서 전환은 결정적이지 않습니다. 비 결정적 Turing Machine의 계산은 시작 구성에서 도달 할 수있는 구성 트리입니다.
허용 구성 인 트리 노드가 하나 이상 있으면 입력이 허용되고 그렇지 않으면 허용되지 않습니다. 계산 트리의 모든 분기가 모든 입력에서 중단되는 경우 비 결정적 튜링 머신은Decider 일부 입력에 대해 모든 분기가 거부되면 입력도 거부됩니다.
비 결정적 튜링 머신은 공식적으로 6- 튜플 (Q, X, ∑, δ, q 0 , B, F)로 정의 할 수 있습니다.
Q 유한 한 상태 집합입니다.
X 테이프 알파벳입니다
∑ 입력 알파벳입니다.
δ 전환 함수입니다.
δ : Q × X → P (Q × X × {왼쪽 이동, 오른쪽 이동}).
q0 초기 상태입니다.
B 빈 기호입니다.
F 최종 상태의 집합입니다.