오라클 머신 편집하기

오라클 머신은 추상화된 블랙박스를 통해 단일연산으로 특정한 결정문제를 풀 수 있는 기계를 의미한다. 이를 풀어서 해석해보면, 오라클 머신은 계산이론에서 1) 예/아니오로 대답할 수 있는 결정 문제를 연구하는 데 사용되는 2) 추상기계이다. 스무고개를 상상해보자. 스무고개에서 풀 수 있는 모든 문제는 예/아니오의 결정문제로 환원될 수 있다. 추상기계라는 말은 실제로 있는 장치가 아닌, 단지 상상속의 기계라는 의미이다. 어떤 종류의 문제를 질문하면 바로 예/아니오로 답을 주는 이상적인, 그러나 이론적 증명에만 사용하는 수학적인 [[컴퓨터]] 모델로, 현재 컴퓨터라는 장치가 수학적으로 가능하다는 것을 보여준 튜링머신이 바로 추상기계다.<ref>박충식, 〈[http://www.econovill.com/news/articleView.html?idxno=346578 (박충식의 인공지능으로 보는 세상) 오라클 머신 또는 신탁 기계]〉, 《이코노빌》, 2018-09-25</ref> 일반적으로 오라클 머신은 튜링머신(turing machine)에 오라클이라는 블랙박스를 붙여놓은 것이라고 할 수 있다. 이때 오라클, 즉 신탁은 어떤 판정 문제를 단 한 번의 동작으로 풀 수 있는 장치이다.<ref name="위키">〈[https://ko.wikipedia.org/wiki/%EC%8B%A0%ED%83%81_%EA%B8%B0%EA%B3%84 신탁 기계]〉, 《위키백과》</ref> 신탁이 풀 수 있는 문제는 모든 복잡도 조율에 해당하기 때문에 심지어는 정지문제와 같이 컴퓨터로 풀 수 없는 문제까지도 풀 수 있다.