신탁 기계

신탁 기계(神託機械, oracle machine)는 판정 문제를 연구하는 데 사용하는 추상 기계로, 일반적인 튜링 기계에 '신탁'(神託, oracle)이라는 블랙박스를 붙여놓은 것이라고 생각할 수 있다. 이때 신탁은 어떤 판정문제를 단 한번의 동작으로 풀 수 있는 장치이다. 신탁이 풀 수 있는 문제는 모든 복잡도 종류에 해당하기 때문에, 심지어 정지 문제 같은 컴퓨터로 풀 수 없는 문제도 풀 수 있다.

정의[편집]

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

신탁과 정지문제의 관계[편집]

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

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

참고 문헌[편집]

Turing, Alan (1939). “Systems of logic based on ordinals”. 《Proceedings of the London Mathematical Society》 (영어) 45.
Baker, T. P.; J. Gill, R. Solovay (1975). “Relativizations of the P =? NP Question”. 《SIAM Journal on Computing》 (영어) 4 (4): 431-442.
Bennett, C. H.; J. Gill (1981). “Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1”. 《SIAM Journal on Computing》 (영어) 10 (1): 96–113.
Papadimitriou, C. (1994). 《Computational Complexity》 (영어). Addison-Wesley.
Sipser, Michael. 《Introduction to the Theory of Computation》 (영어). PWS Publishing. ISBN 0-534-94728-X.