먼저 튜링 머신에 대해 이야기하자면, 튜링 머신은 끝없이 긴 종이테이프로 구성된 매우 단순한 구조입니다. 이 테이프는 오래된 영화 필름처럼 칸칸이 나뉘어 있고, 좌우로만 움직일 수 있도록 설계된 플랫폼 위에 얹혀 있습니다. 테이프는 수평으로 놓여져 있으며 자유롭게 좌우로 미끄러질 수 있습니다. 테이프를 놓은 플랫폼 위에는 테이프 한 칸 크기의 정사각형 창이 한 개 있습니다.

이것이 전부입니다. 이 기계는 그 외에 아무런 복잡한 구조도 갖고 있지 않습니다. 사실상 무한한 메모리를 가진 장치이며, 그 메모리를 특정 창에 위치시켜 읽을 수 있게 하는 기능만 있습니다. 이제 필요한 것은 중앙 처리 장치인데, 그 역할은 이 튜링 머신을 조작하는 사람이 맡습니다.