교대 튜링 기계

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

정의 

교대 튜링 기계는 다음과 같이 표현된다. 
  : 상태의 유한집합
  테이프 알파벳의 유한집합
  옮기기 함수 (L은 테이프를 왼쪽으로, R 은 헤드를 오른쪽으로)
  초기상태

  상태를 나타냄

M의 상태 가 일 때라면 허용  은 거부를 뜻한다.

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

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

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

복잡도 
  : 이 언어가 다항 시간에 결정할 수 있는 것
  이 언어가 다항 공간을 써서 결정할 수 있는 것
  이 언어가 지수 시간안에 결정할 수 있는 것

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

Chandra, Kozen, Stockmeyer는 아래의 정리를 증명했다.
 AP = PSPACE
 APSPACE = EXPTIME
 AEXPTIME = EXPSPACE
 
 
 
단,  이고

같이 보기 
 확률적 튜링 기계

계산 모형