교대 튜링 기계

교대 튜링 기계(Alternating Turing machine, ATM)는 비결정론적 튜링 기계에 몇가지 조건이 추가된 기계이다.

정의

교대 튜링 기계는 다음과 같이 표현된다. $M=(Q,\Gamma ,\delta ,q_0,g)$

• $Q$ : 상태의 유한집합
• $\Gamma$ 테이프 알파벳의 유한집합
• $\delta :Q\times \Gamma \to 𝒫(Q\times \Gamma \times \{L,R\})$ 옮기기 함수 (L은 테이프를 왼쪽으로, R 은 헤드를 오른쪽으로)
• $q_0\in Q$ 초기상태

• $g:Q\to \{\wedge ,\vee ,accept,reject\}$ 상태를 나타냄

M의 상태 $q\in Q$가 $g(q)=accept$일 때라면 허용 $g(q)=reject$ 은 거부를 뜻한다.

$g(q)=\wedge$는 거기서 한번에 접근할 수 있는 모든 다른 구성이 허용일때만 허용을, 그런 구성중 하나라도 거부이면 거부를 뜻한다.

$g(q)=\vee$ 거기서 한번에 접근할 수 있는 모든 구성이 거부일때만 거부를, 그런 구성중 하나라도 허용이면 허용을 뜻한다.

M은 입력열 w를 초기 구성 M이 허용일 때 입력을 허용하고 거부일 때 입력을 거부한다. 이 기계는 형식 언어로 된 길이 n의 입력을 시간단위 n 만에 처리한다.

복잡도

• $\mathrm{A}\mathrm{P}=\bigcup _{k>0}\mathrm{A}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(n^k)$ : 이 언어가 다항 시간에 결정할 수 있는 것
• $\mathrm{A}\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}=\bigcup _{k>0}\mathrm{A}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(n^k)$ 이 언어가 다항 공간을 써서 결정할 수 있는 것
• $\mathrm{A}\mathrm{E}\mathrm{X}\mathrm{P}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}=\bigcup _{k>0}\mathrm{A}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(k^n)$ 이 언어가 지수 시간안에 결정할 수 있는 것

이것은 P, PSPACE, EXPTIME의 정의와 비슷하다.

Chandra, Kozen, Stockmeyer는 아래의 정리를 증명했다.

• AP = PSPACE
• APSPACE = EXPTIME
• AEXPTIME = EXPSPACE
• $\mathrm{A}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(f(n))=\bigcup _{c>0}\mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(2^{cf(n)})=\mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(2^{O(f(n))})$
• $\mathrm{A}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(g(n))\subseteq \mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(g(n))$
• $\mathrm{N}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(g(n))\subseteq \bigcup _{c>0}\mathrm{A}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(c\times g(n{)}^2)$

단, $f(n)\ge \log (n)$ 이고 $g(n)\ge \log (n)$

같이 보기

• 확률적 튜링 기계