맨위로가기

확률적 튜링 기계

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

확률적 튜링 기계는 각 단계에서 두 가지 가능한 다음 동작 중 하나를 확률적으로 선택하는 비결정적 튜링 기계의 한 종류이다. 7-튜플로 정의되며, 전이 함수를 확률적으로 선택하는 과정은 동전 던지기와 유사하다. 확률적 튜링 기계는 오류를 발생시킬 수 있으며, 이러한 오류를 수용하기 위해 언어의 인식은 오류 확률을 사용하여 정의된다. 계산 복잡도 이론에서 확률적 튜링 기계는 RP, BPP, ZPP 등과 같은 다양한 복잡도 종류를 정의하는 데 사용되며, 무작위성이 계산 능력에 어떤 영향을 미치는지에 대한 연구에 활용된다.

더 읽어볼만한 페이지

  • 튜링 기계 - 튜링 완전
    튜링 완전은 계산 이론에서 시스템이 튜링 기계와 동등한 계산 능력을 갖춰 튜링 기계가 계산할 수 있는 모든 함수를 계산하고 범용 튜링 기계를 시뮬레이션할 수 있음을 의미하며, 튜링 동등이라고도 한다.
  • 튜링 기계 - 비결정론적 튜링 기계
    비결정론적 튜링 기계는 튜링 기계의 확장으로, 주어진 상태에서 여러 개의 가능한 다음 동작을 가질 수 있으며, P-NP 문제와 관련하여 계산 복잡도 이론에서 중요한 역할을 한다.
  • 확률적 알고리즘 - 알고리즘 정보 이론
    알고리즘 정보 이론은 콜모고로프 복잡성을 기반으로 객체의 정보량을 측정하는 척도를 제공하며, 최소 설명 길이 원리 등에 응용될 수 있다.
  • 확률적 알고리즘 - 몬테카를로 알고리즘
    몬테카를로 알고리즘은 정확한 답을 보장하지 않는 확률적 알고리즘으로, 단측 또는 양측 오류를 가지며 반복 실행으로 오류를 줄일 수 있고, 라스베가스 알고리즘과 함께 랜덤 알고리즘의 주요 분류를 이루며 다양한 분야에 응용된다.
  • 계산 모형 - 양자 컴퓨터
    양자 컴퓨터는 양자역학적 현상을 이용하여 정보를 처리하는 컴퓨터로, 큐비트를 통해 0과 1을 동시에 표현하여 특정 연산에서 기존 컴퓨터보다 빠른 속도를 보이며 암호 해독, 신약 개발 등 다양한 분야에 혁신을 가져올 것으로 기대된다.
  • 계산 모형 - 양자 회로
    양자 회로는 양자 컴퓨팅에서 양자 논리 게이트들을 연결한 회로로, 큐비트의 양자역학적 특성을 활용하여 계산을 수행하며 양자 계산의 핵심 요소로서 연구가 활발히 진행되고 있다.
확률적 튜링 기계
개요
유형튜링 기계
발명가데이나 스콧
발명일1964년
특징
결정론적 튜링 기계와의 관계결정론적 튜링 기계의 일반화
상태 전이확률 분포에 따라 상태를 전이
계산 복잡도BPP (복잡도)와 같은 복잡도 클래스 정의에 사용
작동 방식
기본 원리각 단계에서 확률적인 선택을 수행
확률적 전이 함수현재 상태와 입력 심볼에 따라 다음 상태와 출력을 결정하는 확률 분포
몬테카를로 알고리즘확률적 튜링 기계의 예시, 항상 답을 반환하지만 틀릴 수도 있음
라스베이거스 알고리즘확률적 튜링 기계의 예시, 항상 정답을 반환하지만 멈추지 않을 수도 있음
활용
복잡도 이론계산 복잡도 이론에서 확률적 알고리즘의 효율성을 분석하는 데 사용
양자 컴퓨팅양자 튜링 기계의 기반이 됨
기타
다른 이름확률 튜링 기계

2. 정의

확률적 튜링 기계는 비결정적 튜링 기계의 일종으로, 각 비결정적 단계에서 "동전 던지기"와 같이 두 가지 가능한 다음 동작 중 하나를 확률적으로 선택한다.[1] 즉, 각 단계에서 튜링 기계는 확률적으로 다음 동작을 결정한다.

2. 1. 형식적 정의

확률적 튜링 기계는 다음과 같이 7개의 요소로 구성된 튜플 M=(Q, \Sigma, \Gamma, q_0, A, \delta_1, \delta_2)로 정의할 수 있다.

  • Q: 상태의 유한 집합
  • \Sigma: 입력 알파벳
  • \Gamma: 테이프 알파벳 (공백 기호 '''#''' 포함)
  • q_0 \in Q: 초기 상태
  • A \subseteq Q: 허용(최종) 상태 집합
  • \delta_1: Q \times \Gamma \to Q \times \Gamma \times \{L,R\} : 첫 번째 확률적 전이 함수. (L은 왼쪽, R은 오른쪽으로 한 칸 이동)
  • \delta_2: Q \times \Gamma \to Q \times \Gamma \times \{L,R\} : 두 번째 확률적 전이 함수.


각 단계에서 튜링 기계는 \delta_1 또는 \delta_2 전이 함수 중 하나를 확률적으로 적용한다.[2] 이 선택은 이전 선택과 독립적이며, 동전 던지기와 유사하다.

전이 함수의 확률적 선택으로 인해 튜링 기계에 오류가 발생할 수 있다. 즉, 허용되어야 할 문자열이 거부되거나, 거부되어야 할 문자열이 허용될 수 있다. 어떤 언어 L이 확률적 튜링 기계 M에 의해 "오류 확률 \epsilon으로" 인식된다는 것은 다음을 의미한다.

1. L에 속하는 문자열 w에 대해, \text{Pr}[M \text{ accepts } w] \geq 1 - \epsilon

2. L에 속하지 않는 문자열 w에 대해, \text{Pr}[M \text{ rejects } w] \geq 1 - \epsilon

2. 2. 오류 확률

각 단계에서 전이 함수의 확률적 선택은 튜링 기계에 오류를 발생시킨다. 즉, 튜링 기계가 허용하도록 되어 있는 문자열이 어떤 경우에는 거부될 수 있고, 튜링 기계가 거부하도록 되어 있는 문자열이 어떤 경우에는 허용될 수 있다.[2] 이를 수용하기 위해, 언어 L이 확률적 튜링 기계 M에 의해 "오류 확률 \epsilon으로" 인식된다고 말한다면, 다음과 같다.

# L에 있는 문자열 w는 \text{Pr}[M \text{ accepts } w] \geq 1 - \epsilon를 의미한다.

# L에 없는 문자열 w는 \text{Pr}[M \text{ rejects } w] \geq 1 - \epsilon를 의미한다.

3. 계산 복잡도

계산 복잡도 이론에서 확률적 튜링 기계는 여러 복잡도 종류를 정의하는 데 사용된다. 확률적 계산은 대부분의 대화형 증명 시스템 종류의 정의에 중요하며, 검증기 기계는 무작위성에 의존하여 예측과 속임수를 피한다. 예를 들어, IP 종류는 PSPACE와 같지만, 검증기에서 무작위성이 제거되면 NP만 남게 된다.[1]

복잡도 이론의 핵심 질문 중 하나는 무작위성이 계산 능력에 영향을 주는지 여부이다. 즉, 확률적 튜링 기계로는 다항 시간 내에 해결할 수 있지만, 결정적 튜링 기계로는 해결할 수 없는 문제가 있는지, 아니면 결정적 튜링 기계가 최대 다항식 속도 저하를 통해 모든 확률적 튜링 기계를 효율적으로 시뮬레이션할 수 있는지가 관건이다. 결정적 튜링 기계는 확률적 튜링 기계의 특수한 경우이므로 '''P''' ⊆ '''BPP'''임이 알려져 있다. 그러나 '''BPP''' ⊆ '''P'''인지 여부는 불확실하며, 널리 '''BPP''' = '''P'''로 추정된다. 로그 공간에 대한 동일한 질문 ('''L''' = '''BPLP'''인가?)은 다항 시간 대신 더 널리 사실이라고 여겨진다. 반면에, 무작위성이 대화형 증명 시스템에 부여하는 힘뿐만 아니라 다항 시간 소수성 검사 및 로그 공간 그래프 연결성 검사와 같은 어려운 문제에 대한 간단한 알고리즘은 무작위성이 계산 능력을 향상시킬 수 있음을 시사한다.[1]

3. 1. 주요 복잡도 종류


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


확률적 동전 던지기를 활용함으로써 발생하는 오류로 인해, 확률적 튜링 기계가 문자열을 받아들이는 개념은 다양한 방식으로 정의될 수 있다. 여러 중요한 복잡도 종류를 포함하는 그러한 개념 중 하나는 오류 확률 1/3을 허용하는 것이다. 예를 들어, 복잡도 종류 '''BPP'''는 오류 확률이 1/3인 다항 시간 내에 확률적 튜링 기계에 의해 인식되는 언어들의 집합으로 정의된다. 이러한 받아들임의 개념을 사용하여 정의된 또 다른 종류는 '''BPL'''이며, 이는 '''BPP'''와 동일하지만 언어가 로그 성장 공간 복잡도에서 해결 가능해야 한다는 추가적인 제한을 둔다.

받아들임의 다른 정의에서 파생된 복잡도 종류는 '''RP''', '''co-RP''', 그리고 '''ZPP'''를 포함한다. 기계가 다항 시간 대신 로그 공간으로 제한되면, 유사한 '''RL''', '''co-RL''', 그리고 '''ZPL''' 복잡도 종류가 얻어진다. 두 가지 제약 조건을 모두 적용하면 '''RLP''', '''co-RLP''', '''BPLP''', 그리고 '''ZPLP'''가 생성된다.

3. 2. 무작위성의 역할

계산 복잡도 이론에서 확률적 튜링 기계를 이용한 여러 복잡도 종류가 정의되어 있다. 이러한 복잡도 종류들은 확률적 튜링 기계가 문자열을 받아들이는 개념, 즉 오류 확률에 따라 다양하게 정의될 수 있다.

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


오류 확률 1/3을 허용하는 복잡도 종류인 '''BPP'''는 다항 시간 내에 확률적 튜링 기계에 의해 인식되는 언어들의 집합으로 정의된다. '''BPL'''은 '''BPP'''와 동일하지만, 언어가 로그 성장 공간 복잡도에서 해결 가능해야 한다는 추가적인 제한이 있다.

이 외에도 '''RP''', '''co-RP''', '''ZPP''' 등의 복잡도 종류가 있으며, 기계가 다항 시간 대신 로그 공간으로 제한되면 '''RL''', '''co-RL''', '''ZPL''' 복잡도 종류가 얻어진다. 두 가지 제약 조건을 모두 적용하면 '''RLP''', '''co-RLP''', '''BPLP''', '''ZPLP'''가 생성된다.

확률적 계산은 대화형 증명 시스템 종류의 정의에도 중요하게 활용된다. 예를 들어, '''IP'''는 '''PSPACE'''와 같지만, 검증기에서 무작위성이 제거되면 '''NP'''만 남게 된다.

복잡도 이론의 핵심 질문 중 하나는 무작위성이 계산 능력에 영향을 미치는지 여부이다. 즉, 확률적 튜링 기계로는 다항 시간 내에 해결할 수 있지만 결정적 튜링 기계로는 해결할 수 없는 문제가 있는지, 아니면 결정적 튜링 기계가 모든 확률적 튜링 기계를 효율적으로 시뮬레이션할 수 있는지가 중요한 문제이다. '''P''' ⊆ '''BPP'''임은 알려져 있지만, '''BPP''' ⊆ '''P'''인지 여부는 아직 밝혀지지 않았다.

참조

[1] 서적 Introduction to the Theory of Computation Thomson Course Technology
[2] 서적 Computational Complexity: A Modern Approach Cambridge University Press 2016


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com