상태
단계 수
테이프의 기호
진행 상황

현재 상태 읽기 쓰기 이동 다음 상태

튜링 기계에 대해 더 알아보기

튜링 기계 시뮬레이터

튜링 기계는 생각할 수 있는 가장 단순한 컴퓨터입니다. 헤드가 끝없는 테이프의 기호 하나를 읽고, 기호를 쓰고, 왼쪽이나 오른쪽으로 한 칸 움직이고 상태를 바꾸는 일을 짧은 규칙표에 따라 반복합니다. 앨런 튜링이 1936년에 고안했으며, 여러분의 컴퓨터가 하는 모든 일은 원리적으로 이런 방식으로 할 수 있습니다. 직접 규칙을 작성하거나 예제를 불러온 뒤 '실행'을 누르고, 테이프가 한 단계씩 바뀌는 모습을 지켜보세요. 아래에는 전체 기록을 보여 주는 다이어그램이 있습니다. 프로그램을 고르거나 직접 작성하고, 입력을 넣은 뒤 '실행'을 누르세요. '한 단계'를 누르면 규칙을 하나씩 따라갈 수 있고, '되돌리기'는 한 단계를 취소합니다. 프로그램의 각 줄은 하나의 규칙으로, 상태, 읽은 기호, 쓸 기호, 이동(L, R 또는 이동하지 않는 N), 다음 상태로 이루어집니다. 예: A 0 -> 1 R B. 빈칸에는 _를 쓰세요. 기계는 첫 번째 규칙의 상태로 입력의 첫 기호 위에서 시작하며, H, accept, reject에 도달하거나 맞는 규칙이 없으면 멈춥니다. 다이어그램은 매 단계 후의 테이프를 위에서 아래로 보여 줍니다.

작동 원리

  1. 예제 프로그램을 고르거나 A 0 -> 1 R B 같은 규칙을 한 줄에 하나씩 작성하고 입력을 넣으세요.
  2. '실행'을 눌러 헤드가 움직이는 모습을 보거나, '한 단계'를 눌러 규칙을 하나씩 따라가세요. '되돌리기'는 한 단계를 취소합니다.
  3. 타일에서 상태, 단계 수, 테이프의 기호를 읽고, 다이어그램에서 테이프의 기록을 확인하세요.

기계의 작동 원리

기계는 매 순간 몇 가지 상태 중 하나에 있고, 헤드는 테이프의 한 칸 위에 있습니다. 그 상태와 헤드 아래 기호에 해당하는 규칙은 세 가지를 알려 줍니다. 그 칸에 어떤 기호를 쓸지, 왼쪽이나 오른쪽으로 움직일지 아니면 가만히 있을지, 그리고 다음에 어떤 상태로 갈지입니다. 기계는 이것이 전부입니다. H, accept, reject 같은 정지 상태에 도달하거나 맞는 규칙이 없으면 멈춥니다. 이진수에 1을 더하는 프로그램은 이런 규칙 아홉 개만 있으면 됩니다.

바쁜 비버

빈 테이프에서 시작한 n상태 기계 중 멈추기 전에 1을 가장 많이 쓰는 기계는 무엇일까요? 티보르 라도(Tibor Radó)가 1962년에 이 질문을 던졌습니다. 그 챔피언들을 바쁜 비버라고 부르며, 이들은 컴퓨터가 계산할 수 있는 어떤 함수보다도 빠르게 커집니다. 2상태는 6단계에 1을 4개, 3상태는 1을 6개, 4상태는 107단계에 1을 13개 씁니다. 1989년에 발견된 5상태 챔피언은 47,176,870단계에 1을 4,098개 쓰며, 2024년 온라인 공동 작업이 컴퓨터로 검증한 수학을 이용해 멈추는 다른 5상태 기계 중 이보다 오래 실행되는 것은 없음을 증명했습니다.

자주 묻는 질문

규칙은 어떻게 작성하나요?

한 줄에 규칙 하나씩, 현재 상태, 읽는 기호, 쓸 기호, 이동(L, R 또는 N), 다음 상태를 씁니다. 예: A 0 -> 1 R B. 화살표와 쉼표는 써도 되고 안 써도 됩니다. 빈칸에는 _를, 주석에는 #을 쓰세요. 기계는 첫 번째 규칙의 상태에서 시작합니다. 다음 상태가 H나 halt이면 멈추고, accept와 reject이면 판정 결과와 함께 멈춥니다.

튜링 기계는 정말 무엇이든 계산할 수 있나요?

테이프와 시간만 충분하면 어떤 컴퓨터가 계산할 수 있는 것은 무엇이든 계산할 수 있습니다. 이것이 처치-튜링 논제입니다. 튜링 기계에는 메모리 한계가 없으므로 그런 의미에서 실제 어떤 컴퓨터보다 강력하지만, 훨씬 느립니다. 튜링 기계가 할 수 없는 것은 모든 질문에 답하는 일입니다. 튜링은 모든 프로그램과 입력에 대해 그것이 멈출지를 판정할 수 있는 기계는 없다는 것을 증명했습니다.

카운터는 왜 멈추지 않나요?

규칙이 결코 정지 상태로 이어지지 않기 때문입니다. 테이프 오른쪽 끝에 있는 이진수에 1을 더하고 되돌아오기를 계속하므로 수는 끝없이 커집니다. 튜링의 정지 문제에 따르면 모든 기계에 대해 멈출지를 알려 주는 일반적인 방법은 없습니다. 이 단순한 카운터는 보면 알 수 있지만, 상태가 여섯 개뿐인 기계 중에도 아직 아무도 답을 모르는 것이 있습니다.

5상태 바쁜 비버가 어떻게 여기서 4700만 단계를 실행할 수 있나요?

테이프는 양방향으로 늘어나는 압축된 배열로 저장되고, 가장 빠른 설정에서는 화면을 갱신하는 사이에 수십만 단계를 실행하므로, 최신 브라우저에서는 전체 실행이 몇 초면 끝납니다. 다이어그램에는 처음 400단계만 기록합니다. 4700만 줄짜리 그림은 어떤 화면에도 들어가지 않기 때문입니다.

서버로 전송되는 것이 있나요?

아니요. 프로그램은 브라우저에서 실행되며, 프로그램과 입력은 이 브라우저의 로컬 저장소에 남습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

편집기로 이동