부품들은 총 다섯 가지로 이루어져 있다. 그것은 무한히 많은 칸을 가진 테이프, 테이프에 기록되는 기호들(A, B, C… 등 유한 개), 테이프에 기록된 기호를 읽거나 쓰는 장치, 그 장치의 상태들(Q₁, Q₂ … 등 유한 개), 기계의 작동 규칙표이고, 기계마다 이 다섯 가지 부품이 구체적으로 정해진다.
기계의 작동 규칙은 다음과 같다. 우선 몇 개의 기호들을 테이프에 읽고 쓰게 될 것인지, 장치의 상태들이 몇 개나 되는지, 작동 규칙표는 무엇인지, 테이프의 시작 모습과 읽고 쓰는 장치의 시작 상태, 테이프의 시작 위치가 정해진다. 이렇게 정의된 기계가 작동 규칙표에 정의돼 있는 규칙대로 작동하면서 정해진 계산을 진행하게 되는 것이다.
작동 규칙에 표현되는 기계의 작동은 매우 간단한 일로만 제한된다. 테이프 칸의 기호를 읽고 쓰면서 테이프를 한 칸씩 좌우로 움직여 가는 일만 할 수 있다. 이러한 과정을 거치면서 기계의 상태가 매번 변경된다. |