한 단계의 동작
헤드가 현재 칸의 기호를 읽으면 전이 규칙에 따라 그 칸에 기호를 쓰고 왼쪽이나 오른쪽으로 이동하며 상태를 바꾼다. 제자리 이동 허용 여부 같은 세부 규칙에는 여러 동등한 모형이 있다.
유한 제어와 테이프
제어 상태의 수는 유한하지만 테이프가 추가 기억 공간을 제공한다. 입력을 읽기만 하는 유한 오토마타와 달리 이전에 적은 기호를 다시 읽거나 고칠 수 있다. 제어 상태가 유한하다는 사실만으로 기억 공간도 유한한 것은 아니다.
이론적 공간의 의미
테이프를 제한 없이 사용할 수 있다는 것은 특정한 유한 메모리 상한을 모형에 미리 두지 않는다는 뜻이다. 유한 단계의 계산에서는 유한한 수의 칸만 방문한다. 실제 기계가 물리적으로 무한한 메모리를 갖는다는 주장은 아니다.
정지와 비용
입력에 대해 기계가 정지하는지, 정지한다면 몇 단계를 수행하고 몇 칸을 사용하는지를 구분해 연구할 수 있다. 계산 가능한 결과와 그 결과를 얻는 시간이나 공간의 효율은 서로 다른 질문이다.
관련 문서
유한 상태 기계 / 결정적 유한 오토마타 / 알고리즘 / 시간 복잡도 / 공간 복잡도 / 문자열 / 계산 이론