신탁 기계(神託機械, oracle machine)는 계산 이론 및 복잡도 이론에서 사용되는 추상 기계의 한 종류이다. 일반적인 튜링 기계(Turing machine)에 '신탁'(oracle)이라는 블랙박스 장치를 추가한 형태로 구성된다. 이 신탁은 특정한 판정 문제(decision problem)를 단 한 번의 동작으로 해결할 수 있는 가상의 장치이며, 신탁이 해결할 수 있는 문제의 범위는 모든 복잡도 종류에 걸쳐 있기 때문에, 정지 문제(halting problem)와 같이 일반적인 튜링 기계로는 풀 수 없는 문제도 풀 수 있는 것으로 가정된다.
신탁 기계의 작동 방식은 다음과 같다. 튜링 기계가 테이프에 입력값을 기록하여 신탁에 전달하면, 신탁은 단 한 단계의 계산만으로 결과를 산출하고 테이프 위의 입력값을 지운 뒤 결과값을 기록한다. 일부 정의에서는 튜링 기계가 입력과 출력을 위해 두 개의 별도 테이프를 사용한다고 가정하기도 한다.
신탁 기계는 1939년 앨런 튜링(Alan Turing)이 박사 논문 "Systems of logic based on ordinals"에서 처음 도입한 개념이다. 튜링은 계산 가능성의 한계를 넘어서는 문제를 다루기 위한 이론적 도구로서 이 개념을 제시하였다. 이후 1975년 베이커(Baker), 길(Gill), 솔로베이(Solovay)의 연구 "Relativizations of the P =? NP Question"를 비롯한 여러 연구에서 신탁 기계는 복잡도 종류 간의 관계를 탐구하는 데 중요한 역할을 하였다.
신탁 기계는 정지 문제와 관련하여 흥미로운 역설을 보여준다. 정지 문제를 해결할 수 있는 신탁이 장착된 기계(초월 기계, hypercomputation)가 존재한다고 가정하더라도, 그 기계 자신의 정지 문제는 여전히 풀 수 없다. 즉, 어떤 신탁 기계도 자기 자신의 정지 여부를 판별할 수 없다는 점에서 원래의 정지 문제와 동일한 한계를 가진다. 이러한 사실은 기계들 간의 위계(hierarchy) 개념으로 이어지며, 이를 산술 위계(arithmetical hierarchy)라고 부른다.
신탁 기계는 주로 계산 복잡도 이론에서 P와 NP 문제의 관계 연구, 복잡도 클래스 간의 상대화(relativization) 연구, 암호학적 안전성 증명 등에 활용되는 이론적 도구이다. 실제 물리적으로 존재하는 기계가 아니라 순수하게 이론적인 추상 기계라는 점에 유의해야 한다.
