튜링 머신

앨런 튜링은 1936년 “On Computable Numbers, with an Application to the Entscheidungsproblem(계산 가능한 수와 결정 문제에의 응용)”이란 논문에서 자기 이름을 딴 튜링 머신을 제시합니다. 이 논문의 목적은 힐베르트가 제시한 세 번째 과제, 즉 결정 가능성 문제에 대해 부정적인 답을 제시하는 것이었습니다. 즉, 임의의 수학적 명제가 증명 가능한지 여부를 일반적으로 판단할 수 있는 방법은 존재하지 않는다고 증명한 것입니다.

여기에서는 튜링의 증명에 대해 자세하게 설명하지 않겠습니다. 이미 훌륭한 참고 자료가 많기 때문입니다. 그중에서도 저는 찰스 페초드(Charles Petzold)의 책 <The Annotated Turing(주석이 달린 튜링)>을 추천합니다.

튜링은 증명 과정에서 프로그램을 숫자로 표현할 수 있는 방법이 필요했습니다. 이를 위해 그는 자신의 기계를 시뮬레이션하는 프로그램을 작성했는데, 자세한 이야기는 조금 뒤에 다시 하겠습니다.