맨위로가기

신탁 기계

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

1. 개요

신탁 기계는 튜링 기계에 "신탁"이라는 개념을 추가한 것이다. 신탁은 튜링 기계가 해결하기 어려운 문제에 대한 답을 즉시 제공하는 블랙 박스와 같은 역할을 한다. 신탁 기계는 작업 테이프, 읽기/쓰기 헤드, 제어 메커니즘 외에 신탁 테이프, 신탁 헤드, ASK 상태와 RESPONSE 상태를 갖는다. ASK 상태에서 신탁에 질의하면 한 단계 만에 문제의 해답을 얻을 수 있다. 신탁 기계는 계산 복잡도와 관련된 문제, 특히 P와 NP의 관계를 연구하는 데 사용되며, 암호학에서도 해시 함수의 보안을 증명하는 데 활용된다.

2. 정의

'''신탁 기계'''는 신탁이 달린 튜링 기계이다. 튜링 기계는 테이프에 입력값을 써서 신탁에 입력으로 전달한다. 신탁은 단 한 단계만에 계산을 마치고 테이프에서 입력값을 지우고 결과값을 쓴다. 가끔은 튜링 기계가 신탁 기계의 입력과 출력 용도로 두 개의 테이프를 가진다고 가정하기도 한다.

오라클 튜링 머신에 대한 많은 동등한 정의가 있으며, 아래에서 논의한다. 여기 제시된 정의는 판 멜케베이크/van Melkebeek영어 (2003)에서 가져온 것이다.

오라클 머신은 튜링 머신과 마찬가지로 다음을 포함한다.


  • '''작업 테이프''': 시작과 끝이 없는 일련의 셀로, 각각 B(빈칸) 또는 테이프 알파벳의 기호를 포함할 수 있다.
  • '''읽기/쓰기 헤드''': 작업 테이프의 단일 셀에 위치하며, 거기에 있는 데이터를 읽고, 새로운 데이터를 쓰고, 테이프를 따라 위치를 늘리거나 줄일 수 있다.
  • '''제어 메커니즘''': 유한한 수의 '''상태''' 중 하나에 있을 수 있으며, 현재 상태와 읽고 있는 데이터에 따라 다른 동작(데이터 읽기, 데이터 쓰기, 제어 메커니즘 이동 및 상태 변경)을 수행한다.


이러한 구성 요소 외에도 오라클 머신은 다음을 포함한다.

  • '''오라클 테이프''': 작업 테이프와 별개인 반무한 테이프이다. 오라클 테이프의 알파벳은 작업 테이프의 알파벳과 다를 수 있다.
  • '''오라클 헤드''': 읽기/쓰기 헤드처럼 오라클 테이프를 따라 왼쪽 또는 오른쪽으로 이동하여 기호를 읽고 쓸 수 있다.
  • 두 개의 특수 상태: ASK 상태와 RESPONSE 상태.


오라클 머신은 때때로 ASK 상태에 들어갈 수 있다. 이 경우 단일 계산 단계에서 다음 동작이 수행된다.

  • 오라클 테이프의 내용은 오라클의 계산 문제의 인스턴스로 간주된다.
  • 오라클과 상의하여 오라클 테이프의 내용이 해당 문제 인스턴스의 솔루션으로 바뀐다.
  • 오라클 헤드가 오라클 테이프의 첫 번째 칸으로 이동한다.
  • 오라클 머신의 상태가 RESPONSE로 변경된다.


따라서 ASK 상태로 변경하면 오라클 테이프에 기록된 문제 인스턴스의 솔루션을 한 단계로 얻게 된다.

신탁 기계는 오라클이 있는 튜링 머신이다. 튜링 머신은 오라클에 대한 입력을 자체 테이프에 쓰고, 오라클에게 그 실행을 지시한다. 1단계에서 오라클은 그것을 계산하고 입력을 지워 출력을 테이프에 쓴다. 경우에 따라 튜링 머신이 2개의 테이프를 갖는 것으로 묘사될 수 있으며, 하나는 오라클에 대한 입력, 다른 하나는 오라클로부터의 출력에 사용된다.

2. 1. 신탁(Oracle)

신탁은 결정 문제 또는 함수 문제와 같이, 어떤 문제를 해결할 수 있는 추상적인 실체이다. 신탁은 튜링 기계나 컴퓨터 프로그램일 필요는 없으며, 주어진 계산 문제의 모든 인스턴스에 대한 솔루션을 생성할 수 있는 "블랙 박스"로 간주된다.

  • 결정 문제의 경우, 신탁은 주어진 입력(자연수 또는 문자열)이 특정 집합에 속하는지("YES") 속하지 않는지("NO")를 판별한다.
  • 함수 문제의 경우, 신탁은 주어진 입력에 대한 함수의 결과값을 제공한다.


신탁 기계는 튜링 기계의 모든 일반적인 연산을 수행할 수 있으며, 신탁에 질의하여 해당 신탁에 대한 계산 문제의 모든 인스턴스에 대한 솔루션을 얻을 수도 있다. 예를 들어, 문제가 자연수 집합 ''A''에 대한 결정 문제인 경우 신탁 기계는 신탁에 자연수를 제공하고, 신탁은 해당 숫자가 ''A''의 요소인지 여부를 나타내는 "예" 또는 "아니요"로 응답한다.

2. 2. 신탁 기계의 작동 방식

신탁 기계는 튜링 기계와 유사하게 작동하며 작업 테이프, 읽기/쓰기 헤드, 제어 메커니즘을 포함한다. 이 외에도 신탁 기계는 신탁 테이프와 신탁 헤드, 그리고 ASK 상태와 RESPONSE 상태라는 두 가지 특수 상태를 가진다.

신탁 기계는 일반적인 튜링 기계의 연산 외에, ASK 상태에 진입하여 신탁에 질의를 할 수 있다. ASK 상태에 들어가면, 단일 계산 단계에서 다음과 같은 동작이 수행된다.

  • 오라클 테이프의 내용은 오라클의 계산 문제의 인스턴스로 간주된다.
  • 오라클과 상의하여 오라클 테이프의 내용이 해당 문제 인스턴스의 솔루션으로 바뀐다.
  • 오라클 헤드가 오라클 테이프의 첫 번째 칸으로 이동한다.
  • 오라클 기계의 상태가 RESPONSE로 변경된다.


이러한 과정을 통해 신탁 기계는 오라클 테이프에 기록된 문제 인스턴스의 솔루션을 한 단계로 얻게 된다.

2. 3. 대안적 정의

신탁 기계에 대한 여러 대안적인 정의들이 존재한다. 이러한 정의들은 주로 결정 문제를 해결하는 신탁에 특화되어 있다.

  • 일부 정의에서는 오라클 테이프에 답을 기록하는 대신 ASK 상태 외에 YES와 NO라는 두 개의 특수한 상태를 사용한다. 오라클에 질의하면, 오라클 테이프의 내용이 오라클 집합에 있으면 다음 상태가 YES로 선택되고, 내용이 오라클 집합에 없으면 NO로 선택된다.
  • 일부 정의에서는 별도의 오라클 테이프를 사용하지 않는다. 오라클 상태에 들어가면 테이프 기호가 지정된다. 오라클은 작업 테이프에 이 테이프 기호가 나타나는 횟수로 질의된다. 해당 숫자가 오라클 집합에 있으면 다음 상태는 YES 상태이고, 그렇지 않으면 다음 상태는 NO 상태이다.
  • 또 다른 대안적 정의에서는 오라클 테이프를 읽기 전용으로 만들고 ASK 및 RESPONSE 상태를 완전히 제거한다. 기계를 시작하기 전에 오라클 집합의 지시 함수가 기호 0과 1을 사용하여 오라클 테이프에 기록된다. 그런 다음 기계는 오라클 테이프에서 올바른 칸으로 이동하여 해당 값을 읽음으로써 오라클에 질의할 수 있다.


이러한 정의들은 튜링 계산 가능성의 관점에서는 동일하다. 즉, 주어진 오라클에 대해 함수가 이러한 정의 중 하나에서 오라클-계산 가능하다면, 모든 정의에서 오라클-계산 가능하다. 그러나 이러한 정의들은 계산 복잡성의 관점에서는 동일하지 않다. 오라클 테이프가 자체적인 알파벳을 가질 수 있는 van Melkebeek의 정의와 같은 정의는 일반적으로 필요하다.

3. 복잡도 클래스

결정 문제를 클래스 A의 알고리즘이 언어 L에 대한 오라클을 사용하여 해결할 수 있는 복잡도 클래스는 AL이라고 한다. 예를 들어, PSAT는 부울 만족 문제에 대한 오라클을 사용하여 다항 시간 내에 결정적 튜링 기계로 해결할 수 있는 문제의 클래스이다. 표기 AB는 언어 집합 B(또는 복잡도 클래스 B)로 확장될 수 있다.

:A^B = \bigcup_{L \in B} A^L

언어 L이 클래스 B에 대해 완전한 경우, A의 기계가 클래스 B의 완전성 정의에 사용된 환원을 실행할 수 있다면 AL=AB이다. 특히, SAT는 다항 시간 환원과 관련하여 NP-완전하므로 PSAT=PNP이다.

NP ⊆ PNP임이 이해되지만, NPNP, PNP, NP 및 P가 같은지에 대한 질문은 기껏해야 잠정적이다. 이들은 다르다고 믿어지며, 이는 다항 시간 계층의 정의로 이어진다.

오라클 기계는 오라클 A에 대한 PA와 NPA의 관계를 고려하여 복잡도 클래스 P와 NP의 관계를 조사하는 데 유용하다. 특히, PA=NPA 및 PB≠NPB인 언어 A와 B가 존재한다는 것이 밝혀졌다. P = NP 질문이 양쪽 모두 상대화된다는 사실은 이 질문에 답하는 것이 어렵다는 증거로 받아들여지는데, 그 이유는 ''상대화''(즉, 오라클 추가의 영향을 받지 않음)되는 증명 기술은 P = NP 질문에 답하지 않을 것이기 때문이다. 대부분의 증명 기술은 상대화된다.

모든 가능한 오라클(무한 집합) 중에서 오라클이 무작위로 선택되는 경우를 고려할 수 있다. 이 경우, 확률 1로 PA≠NPA임이 밝혀졌다. 질문이 거의 모든 오라클에 대해 참이면, 그것은 ''임의 오라클''에 대해 참이라고 한다. 이러한 용어 선택은 임의 오라클이 확률 0 또는 1로만 명제를 지원한다는 사실에 의해 정당화된다. 이는 P≠NP에 대한 약한 증거일 뿐인데, 명제는 임의 오라클에 대해서는 참이지만 일반 튜링 기계에 대해서는 거짓일 수 있기 때문이다. 예를 들어, 임의 오라클 A에 대해 IPA≠PSPACEA이지만 IP = PSPACE이다.

4. 신탁과 정지 문제

정지 문제와 같이 컴퓨터로 풀 수 없는 문제도 풀 수 있는 신탁이 존재한다고 가정할 수도 있다. 이런 문제를 해결할 수 있는 신탁이 달린 기계는 초월 기계라고 부른다.

흥미롭게도 정지문제의 역설은 초월기계에도 그대로 적용된다. 즉, 특정한 튜링 기계가 특정한 입력에 대해 멈출지 여부를 판별할 수는 있지만 동일한 정지신탁이 달린 기계가 멈출지 여부는 판별할 수 없다. 이런 사실에서 기계들에 대한 위계(hierarchy)를 생각할 수 있으며, 이것을 산술 위계(arithmetical hierarchy)라고 한다.

정지 문제에 대한 오라클을 가진 기계는 특정 튜링 기계가 특정 입력에 대해 정지할지 여부를 결정할 수 있지만, 일반적으로 자신과 동등한 기계가 정지할지 여부는 결정할 수 없다. 이는 각각 더 강력한 정지 오라클과 훨씬 더 어려운 정지 문제를 가진 기계의 계층 구조를 만든다.

이러한 기계의 계층 구조는 ''산술적 계층''을 정의하는 데 사용될 수 있다.

계산 불가능하다고 여겨지는 계산을 수행하는 오라클 머신을 상정하는 경우도 있다. 예를 들어 튜링 머신의 정지 문제나 그것과 등가인 문제를 풀 수 있는 오라클 머신이다. 이러한 오라클이 부가된 기계를 하이퍼컴퓨터라고 부른다.

5. 암호학적 응용

암호학에서 오라클은 해시 함수가 사용되는 암호 프로토콜의 보안에 대한 주장을 하기 위해 사용된다. 프로토콜에 대한 보안 축소(보안 증명)는 해시 함수 대신 랜덤 오라클이 각 질의에 대해 무작위로 일관되게 응답하는 경우에 제공된다. 오라클은 해시 함수와 마찬가지로 공격자를 포함한 모든 당사자가 사용할 수 있다고 가정한다. 이러한 증명은 공격자가 보안 축소의 핵심인 어려운 문제를 해결하지 않는 한, 프로토콜을 깨기 위해 해시 함수의 흥미로운 속성을 사용해야 함을 보여준다. 즉, 해시 함수를 블랙 박스(즉, 랜덤 오라클)로 취급할 수 없다.

최근 컴퓨터 과학에서 신탁 기계의 응용으로 암호 분야가 있다. 질문에 대해 무작위적이지만 일관된 답변을 반환하는 (동일한 질문에는 동일한 답변을 반환하는) 랜덤 오라클이 있다고 가정할 때, 매우 안전한 일방향 함수로 사용할 수 있다. 즉, 랜덤 오라클의 출력을 얻더라도, 무차별 대입 방식으로 입력값을 시도해 보지 않는 한 입력을 찾아내는 프로그램을 만들 수 없다. 이를 통해 매우 강력한 암호를 만들 수 있지만, 실제로는 랜덤 오라클 대신 의사 난수 생성기가 사용된다. 그러나 의사 난수 생성기는 랜덤 오라클만큼 안전하지 않다.

6. 한국의 관점 및 추가 정보


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

문의하기 : help@durumis.com