교대 튜링 기계

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

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

정의[편집]

교대 튜링 기계는 다음과 같이 표현된다.

  •  : 상태의 유한집합
  • 테이프 알파벳의 유한집합
  • 옮기기 함수 (L은 테이프를 왼쪽으로, R 은 헤드를 오른쪽으로)
  • 초기상태
  • 상태를 나타냄

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

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

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

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

복잡도[편집]

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

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

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

  • AP = PSPACE
  • APSPACE = EXPTIME
  • AEXPTIME = EXPSPACE

단, 이고

같이보기[편집]