튜링 기계는 유한집합 하나를 가정하고, 이 기계는 정사각형의 긴 테이프를 조사하며 기계 상태와 정사각형에 적힌 기호에 따라 움직인다. 출력은 수동 상태로 정지한 뒤 번역된다. 튜링 기계는 작동원리가 계산이론에 뼈대를 두기에 만능 컴퓨터라 불린다.
튜링 기계의 작동은 다음과 같다. 각각의 순간에 이 기계는 내부 상태들의 유한집합 중 하나를 가정한다. "수동"을 나타내는 것을 제외한 이러한 상태들 중 어느 하나에서 이 기계는 정4각형으로 나누어진 무한히 긴 테이프를 조사하는데, 이들 정4각형 각각은 비어 있거나 또는 유한개의 기호 중 하나가 적혀 있다. 그 뒤 이 기계는 조사된 정4각형을 좌우로 움직여 주어진 순간과 그 다음 순간 사이에 또 다른 상태로 바꿀 수 있다. 이러한 모든 동작은 기계의 내부 상태와 주어진 순간에 조사된 정4각형에 적힌 기호에 따라 결정된다. 이 기계의 출력은 기계가 수동 상태에 도달하여 멈춘 뒤 그 테이프에 있는 기호들로부터 번역될 수 있다. 튜링 기계는 만능 컴퓨터라고도 알려져 있는데, 그 이유는 그것의 작동원리가 계산이론에 바탕을 두고 있기 때문이다. 1937년 발표된 튜링의 유명한 논문은 괴델의 정리를 바탕으로 하고 있으며, 튜링 기계의 고정된 유한과정으로는 풀 수 없는 몇몇의 수학 문제가 있음을 보였다.