교대 튜링 기계

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

교대 튜링 기계(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 초기상태
  • g:Q\rightarrow\{\wedge,\vee,accept,reject\} 상태를 나타냄

M의 상태 q\in Qg(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)\ge\log(n) 이고 g(n)\ge\log(n)

같이보기[편집]