교대 튜링 기계

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

정의

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

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

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

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

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

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

${\rm {AP}}=\bigcup _{k>0}{\rm {ATIME}}(n^{k})$ : 이 언어가 다항 시간에 결정할 수 있는 것
${\rm {APSPACE}}=\bigcup _{k>0}{\rm {ASPACE}}(n^{k})$ 이 언어가 다항 공간을 써서 결정할 수 있는 것
${\rm {AEXPTIME}}=\bigcup _{k>0}{\rm {ATIME}}(k^{n})$ 이 언어가 지수 시간안에 결정할 수 있는 것

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

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

AP = PSPACE
APSPACE = EXPTIME
AEXPTIME = EXPSPACE
$\mathrm {ASPACE} (f(n))=\bigcup _{c>0}{\rm {DTIME}}(2^{cf(n)})={\rm {DTIME}}(2^{O(f(n))})$
$\mathrm {ATIME} (g(n))\subseteq {\rm {DSPACE}}(g(n))$
$\mathrm {NSPACE} (g(n))\subseteq \bigcup _{c>0}{\rm {ATIME}}(c\times g(n)^{2})$

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