확률적 튜링 기계

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

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

계산 복잡도

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

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