튜링 기계 시뮬레이터

(지금 상태, 지금 읽은 기호) 한 쌍마다 「어떤 기호를 쓰고, 어느 상태로 가고, 머리를 어느 쪽으로 움직이는가(왼쪽 L·오른쪽 R·제자리 S)」를 정해 둔 전이표 하나로 완전히 정의됩니다. 계산 이론에서는 이것이 "계산 가능"이라는 개념 자체를 정의하는 기준 모델로 쓰입니다.

전이표를 잘못 설계하면(또는 원래 정지하지 않는 계산이면) 튜링 기계는 영원히 멈추지 않을 수 있습니다. 임의의 튜링 기계가 정지할지 미리 판정하는 일반적인 방법은 없다는 것이 "정지 문제는 결정 불가능하다"는 유명한 결과입니다. 그래서 시뮬레이터는 실행이 끝나지 않아도 프로그램이 멈추도록 스텝 수 상한을 반드시 둡니다.

머리가 원래 테이프 범위를 벗어나면 그쪽에 빈칸 기호를 채워 테이프를 늘립니다. 튜링 기계의 테이프는 원래 양방향으로 무한하다고 정의되므로, 이 확장은 그 무한 테이프를 필요한 만큼만 흉내 내는 것입니다.

그 (상태, 기호) 조합에 대한 규칙이 없으면 그 자리에서 실행을 멈춥니다("정지 상태에 도달해서"가 아니라 "갈 곳이 없어서" 멈추는 것이라 구분해서 보여줍니다). 전이표를 일부러 다 채우지 않고 "이 경우엔 정의되지 않은 동작"으로 두는 것도 흔한 설계입니다.

단항 증가는 1을 나열한 수(예: "111") 오른쪽 끝에 1을 하나 더 붙입니다. 이진수 1 증가는 오른쪽 끝까지 이동한 뒤 자리올림을 하며 왼쪽으로 돌아옵니다("1011"→"1100" 등). 비트반전은 테이프의 모든 0과 1을 서로 바꿉니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고 입력값은 이 기기에만 남습니다.