확률적 튜링 기계

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

확률적 튜링 기계(Probabilistic Turing machine)는 비결정론적 튜링 기계의 하나로, 기계의 다음 상태가 확률적으로 정해지는 성질을 가진다.

확률적 튜링 기계는 일반적인 튜링 기계를 확장하여, '난수'라는 명령어를 추가한 것으로 구성할 수 있는데, 기계가 '난수' 명령어를 실행하면 테이프에는 0이나 1 중 하나가 균등한 확률로 적힌다. 또는 튜링 기계에 일반적인 테이프와 별도로 '난수 테이프'를 추가한 것으로도 구성할 수 있다.

계산 복잡도[편집]

계산 복잡도 이론에서는 확률적 튜링 기계를 이용한 복잡도 종류가 몇 가지 정의되어 있다.

  • RP는 항상 다항 시간 안에 실행되며, 문제의 답이 '0'일 때는 확률적 튜링 기계는 항상 '0'을 출력하지만, 답이 '1'일 때는 최소 확률 1/2로 '1'을 출력하는 문제들의 종류이다.
  • BPP는 항상 다항 시간 안에 실행되며, 답이 '0'일 때와 '1'일 때 모두 잘못된 답을 출력할 확률이 1/2보다 작은 문제들의 종류이다.
  • ZPP는 다항 시간 안에 실행되며 항상 맞는 답을 출력한다. ZPP는 RP과 co-RP의 교집합이다.