비결정론적 튜링 기계
위키백과 ― 우리 모두의 백과사전.
비결정론적 튜링 기계(nondeterministic Turing machine, NTM)는 튜링 기계에서 특정 상태에서 움직일 수 있는 상태의 갯수가 하나로 정해져 있지 않은 경우를 말한다. 이것은 비결정론적 유한 오토마타와 유사한 개념이다.
이동 가능성이 하나로 정해져 있는 결정론적 튜링 기계와는 반대로, 이 기계에서 이동할 수 있는 상태의 갯수는 상황에 따라 다르며, 여러 개가 되거나 아예 없을 수도 있다.
[편집] 정의
비결정론적 튜링 기계는 다음과 같이 표현된다.
각각의 기호는 다음을 의미한다.
- Q : 상태의 유한집합
- Σ : 심볼(테이프에 사용되는 알파벳)의 유한집합
: 초기상태
: 빈 심볼 (
)
: 최종 상태의 유한집합
: '전이함수'라 불리는 부분함수. L은 왼쪽 방향 시프트이고 R은 오른쪽 방향 시프트이다.
[편집] 같이보기
- 확률적 튜링 기계
[편집] 바깥고리
- 비결정론적 Multitape 튜링 기계의 C++ 시뮬레이터 (자유 소프트웨어).
오토마타 이론: 형식 언어 및 형식 문법 | |||
---|---|---|---|
촘스키 위계 | 형식 문법 | 형식 언어 | 최소한의 자동장치 |
Type-0 | (무제약) | 순환 열거 언어 | 튜링 기계 |
(무제약) | 순환 언어 | 판정자 | |
Type-1 | 문맥 의존 문법 | 문맥 의존 언어 | 선형유한 오토마타 |
Type-2 | 문맥 무관 문법 | 문맥 무관 언어 | 내리누름 오토마타 |
Type-3 | 정규 문법 | 정규 언어 | 유한 오토마타 |
각 언어 및 문법은 바로 윗 줄 언어 및 문법의 진부분집합이다. |