확률론적 튜링 기계

이론 컴퓨터 과학에서, 확률론적 튜링 기계는 어떤 확률 분포에 따라 각 지점에서 이용 가능한 전이들 사이에서 선택하는 비결정론적 튜링 기계이다.결과적으로, 확률론적 튜링 기계는 결정론적 튜링 기계와 달리 확률적 결과를 가질 수 있다. 즉, 주어진 입력과 명령 상태 기계에서, 그것은 다른 실행 시간을 가질 수도 있고, 전혀 멈추지 않을 수도 있다. 더 나아가, 그것은 하나의 실행에서 입력을 받아들이고 다른 실행에서 동일한 입력을 거부할 수도 있다.

전이에 대한 동등한 확률의 경우, 확률론적 튜링 기계는 튜링 기계의 알파벳에서 쓰기 값이 균일하게 분포되는 추가 "쓰기" 명령을 가진 결정론적 튜링 기계로 정의될 수 있다(일반적으로 테이프에 "1" 또는 "0"을 쓸 수 있는 동등한 가능성).또 다른 일반적인 재구성은 단순히 "랜덤 테이프"라고 불리는 랜덤 비트로 가득 찬 테이프를 가진 결정론적 튜링 기계입니다.

양자 컴퓨터는 본질적으로 확률적인 또 다른 계산 모델이다.

묘사

확률론적 튜링 기계는 비결정론적 튜링 기계의 한 종류로, 각 단계가 "코인 플립"이며, 즉 각 단계에서 두 가지 가능한 다음 동작이 있고 튜링 기계는 확률적으로 어떤 움직임을 ^[1]취할지를 선택한다.

형식적 정의

확률론적 튜링 기계는 공식적으로 $M=(Q,\Sigma ,\Gamma ,q_{0},A,\delta _{1},\delta _{2})$ $M=(Q,\Sigma ,\Gamma ,q_{0},A,\delta _{1},\delta _{2})$ ( $M=(Q,\Sigma ,\Gamma ,q_{0},A,\delta _{1},\delta _{2})$ Q , $M=(Q,\Sigma ,\Gamma ,q_{0},A,\delta _{1},\delta _{2})$ 、 $M=(Q,\Sigma ,\Gamma ,q_{0},A,\delta _{1},\delta _{2})$ , A , $M=(Q,\Sigma ,\Gamma ,q_{0},A,\delta _{1},\delta _{2})$ 1, $M=(Q,\Sigma ,\Gamma ,q_{0},A,\delta _{1},\delta _{2})$ 2 $M=(Q,\Sigma ,\Gamma ,q_{0},A,\delta _{1},\delta _{2})$ ) ({ $displaystyle$ M = ( $Q$ , \ $Sigma$ , \ $Gamma$ , $q$ _ $0$ , $A$ , \ $delta _$ { $1 }$ ) 로 정의할 수 있습니다.

$(\displaystyle$ Q $)$ 는 $Q$ 유한한 상태의 집합입니다.
$σ$ \ $displaystyle$ \ $\Sigma$ Sigma $\Sigma$ }는 입력 알파벳입니다.
$γ(\displaystyle$ \Gamma $\Gamma$ )은 공백 기호 #를 포함한 테이프 $\Gamma$ 입니다.
$q_{0}\in Q$ 0 $({displaystyle q_{$ 0}\ $in$ Q $)$ 는 $q_{0}\in Q$ 초기 상태입니다.
$(\displaystyle$ A $\subseteq)$ 는 $A\subseteq Q$ 수용(최종) 상태의 집합입니다.
$R$ $Q\times$ \ $Gamma \to$ Q $\times$ \ $Gamma \times \{L,R\}$ 는 $\delta _{1}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}$ 첫 번째 확률론적 전이 함수이다. $L$ {\ $displaystyle$ L $L$ }은 튜링 머신의 테이프에서 왼쪽으로 한 셀, $R$ {\ $displaystyle$ R $}$ 은 $R$ 오른쪽으로 한 셀 이동입니다.
$R$ $Q\times$ \ $Gamma \to$ Q $\times$ \ $Gamma \times \{L,R\}$ 는 $\delta _{2}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}$ 두 번째 확률론적 전이 함수입니다.

각 단계에서 Turing 기계는 천이함수 $\delta _{1}$ 1(\ $displaystyle$ \ $delta _{1})$ 또는 $\delta _{1}$ 천이함수 $\delta _{2}$ 2(\ $displaystyle \delta$ _ ${2$ ^[2] 중 하나를 확률적으로 적용합니다.이 선택은 이전의 모든 선택과는 독립적으로 이루어집니다.이와 같이 계산의 각 단계에서 전이함수를 선택하는 과정은 코인 플립과 유사하다.

각 단계에서 전이 함수의 확률론적 선택은 튜링 기계에 오류를 발생시킨다. 즉, 튜링 기계가 받아들이도록 의도된 문자열은 어떤 경우에는 거부될 수 있고 어떤 경우에는 튜링 기계가 거부되도록 의도된 문자열이 받아들여질 수 있다.이를 수용하기 위해 다음과 같은 경우 확률론적 튜링 $기계$ M({ $displaystyle$ M $})$ 에 $M$ 의해 $언어$ L({ $displaystyle$ L})이 $L$ 오류 확률 $\epsilon$ {\ $displaystyle\epsilon}$ 로 $\epsilon$ 인식된다고 한다.

$w$ 의 $문자열$ w {\ $displaystyle$ L $}$ 는 $L$ Pr $w$ ${\text{Pr}}[M{\text{ accepts }}w]\geq 1-\epsilon$ 이 ${\text{Pr}}[M{\text{ accepts }}w]\geq 1-\epsilon$ w를 ${\text{Pr}}[M{\text{ accepts }}w]\geq 1-\epsilon$ ${\text{Pr}}[M{\text{ accepts }}w]\geq 1-\epsilon$ - ${\text{Pr}}[M{\text{ accepts }}w]\geq 1-\epsilon$ {\ 、（ \ $displaystyle$ { $Pr$ } ） [ $M$ { \ $text$ { accepts $}w$ ] \ $geq 1-$ \ $epsilon }$ 을 의미합니다.
$L에$ $문자열$ w {\ $displaystyle$ L $}$ 는 $L$ Pr $w$ ${\text{Pr}}[M{\text{ rejects }}w]\geq 1-\epsilon$ [ ${\text{Pr}}[M{\text{ rejects }}w]\geq 1-\epsilon$ ${\text{Pr}}[M{\text{ rejects }}w]\geq 1-\epsilon$ w ${\text{Pr}}[M{\text{ rejects }}w]\geq 1-\epsilon$ 1 ${\text{Pr}}[M{\text{ rejects }}w]\geq 1-\epsilon$ - ${\text{Pr}}[M{\text{ rejects }}w]\geq 1-\epsilon$ {\ 、 ${\text{Pr}}[M{\text{ rejects }}w]\geq 1-\epsilon$ 1 - ${\text{Pr}}[M{\text{ rejects }}w]\geq 1-\epsilon$ \ $displaystyle$ { $Pr$ } [ $M$ { \ $text$ { rejects $}w$ ] \ $geq 1-$ \ $epsilon }$ 을 의미합니다.

복잡도 클래스

컴퓨터 과학에서 해결되지 않은 문제:

있나P = BPP?

(컴퓨터 사이언스의 미해결 문제 증가)

확률론적 동전 던지기를 이용하여 도입된 오류의 결과 확률론적 튜링 기계에 의한 문자열 수용 개념을 다른 방법으로 정의할 수 있다.몇 가지 중요한 복잡도 클래스를 포함하는 그러한 개념 중 하나는 1/3의 오류 확률을 허용하는 것이다.예를 들어, 복잡도 클래스 BPP는 오차 확률이 1/3인 다항식 시간에 확률론적 튜링 기계에 의해 인식되는 언어의 클래스로 정의된다.이 수용 개념을 사용하여 정의된 또 다른 클래스는 BPL입니다.BPP는 BPP와 동일하지만 언어는 로그 공간에서 해결 가능해야 한다는 추가 제한이 있습니다.

수용의 다른 정의에서 발생하는 복잡도 클래스에는 RP, co-RP 및 ZPP가 있습니다.기계가 다항식 시간 대신 로그 공간으로 제한되면 유사한 RL, co-RL 및 ZPL 복잡도 클래스를 얻을 수 있습니다.양쪽 제한을 적용하면 RLP, co-RLP, BPLP 및 ZPLP가 산출됩니다.

확률론적 계산은 또한 검증 기계가 모든 강력한 프로버 기계에 의해 예측되고 속는 것을 피하기 위해 무작위성에 의존하는 대부분의 상호작용 증명 시스템 클래스의 정의에 중요하다.예를 들어 클래스 IP는 PSPACE와 동일하지만 검증자에서 랜덤성이 제거되면 NP만 남게 됩니다.NP는 알려져 있지 않지만 상당히 작은 클래스라고 널리 알려져 있습니다.

복잡성 이론의 중심 질문 중 하나는 무작위성이 힘을 더하는가 하는 것이다; 즉, 확률론적 튜링 기계에 의해 다항식 시간에 해결될 수 있는 문제가 있지만 결정론적 튜링 기계는 없는가?아니면 결정론적 튜링 기계가 기껏해야 다항식 감속으로 모든 확률론적 튜링 기계를 효율적으로 시뮬레이션할 수 있을까?결정론적 튜링 기계는 확률론적 튜링 기계의 특별한 경우에 불과하기 때문에 P b BPP로 알려져 있다.그러나 BPP p P인지는 불확실하며, 이는 BPP = P임을 의미한다.다항식 시간 대신 로그 공간에 대한 동일한 질문(L = BPLP?)은 더욱 널리 사실로 믿어진다.한편, 인터랙티브 증명 시스템에 제공하는 전력 랜덤성은 다항식 시간 프라이머리 테스트 및 로그 공간 그래프 연결성 테스트와 같은 어려운 문제에 대해 생성되는 단순한 알고리즘과 마찬가지로 랜덤성이 전력을 추가할 수 있음을 시사한다.

「」를 참조해 주세요.

랜덤화 알고리즘

메모들

^ Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). USA: Thomson Course Technology. p. 368. ISBN 978-0-534-95097-2.
^ Arora, Sanjeev; Barak, Boaz (2016). Computational Complexity: A Modern Approach. Cambridge University Press. p. 125. ISBN 978-0-521-42426-4.

레퍼런스

Arora, Sanjeev; Barak, Boaz (2016). Computational Complexity: A Modern Approach. Cambridge University Press. pp. 123–142. ISBN 978-0-521-42426-4.
Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). USA: Thomson Course Technology. pp. 368–380. ISBN 978-0-534-95097-2.

외부 링크

확률론적 튜링 기계에 관한 NIST 웹사이트

[1] Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). USA: Thomson Course Technology. p. 368. ISBN 978-0-534-95097-2.

[2] Arora, Sanjeev; Barak, Boaz (2016). Computational Complexity: A Modern Approach. Cambridge University Press. p. 125. ISBN 978-0-521-42426-4.

[1]

[2]

Search

확률론적 튜링 기계

네임스페이스

더

목차

묘사

형식적 정의

복잡도 클래스

「」를 참조해 주세요.

메모들

레퍼런스

외부 링크

Search

확률론적 튜링 기계

묘사

형식적 정의

복잡도 클래스

「 」를 참조해 주세요.

메모들

레퍼런스

외부 링크

「」를 참조해 주세요.