수학자 힐베르트는 어떤 1차 논리의 논리식이 주어졌을 경우 이 논리식이 타당한지 여부를 결정하는 알고리즘이 존재하느냐 하는 문제를 제기했다. 튜링은 이 문제에 대한 답을 얻는 과정에서 가상의 기계 장치인 ‘튜링 기계’를 ⓐ고안하게 된다. 튜링 기계는 사람이 계산할 때 일어나는 사고 과정을 응용한 가상의 기계로 ㉠테이프, ㉡헤드, ㉢상태 기록기 등의 부품으로 ⓑ구성된다. 테이프는 좌우 양방향으로 무한히 많은 칸을 갖고 있다고 가정하며, 각 칸은 비어 있거나 한 개의 기호가 기록되어 있다. 헤드는 테이프에 기록된 기호를 읽거나 기호를 기록하는 장치인데, 테이프 위를 좌우로 한 칸씩 움직일 수 있다. 상태 기록기는 튜링 기계의 상태를 나타낸다.
