Minecraft 레드스톤 튜링 기계

마인크래프트 레드스톤으로 튜링 머신 구현하기

튜링 머신은 셀로 나뉜 무한한 테이프, 읽기/쓰기 헤드, 그리고 프로그램 역할을 하는 전이 테이블로 구성됩니다. 마인크래프트에서는 이러한 구성 요소를 0~15까지 16단계의 신호 강도를 가진 신호 전송 시스템인 '레드스톤'으로 시뮬레이션합니다. 레드스톤 가루는 블록 하나당 신호 강도가 1씩 감소하며 최대 15블록까지 신호를 전달합니다.

주요 레드스톤 부품:

• 레드스톤 토치: 신호를 반전시킵니다 (NOT 게이트).
• 레버: 안정적이고 지속적인 전원을 공급합니다.
• 버튼: 고정된 길이의 펄스를 생성합니다.
• 반복기: 신호 강도를 증폭하고 단방향 흐름을 강제하며 1~4틱의 지연을 추가합니다.
• 비교기: 신호 강도를 비교하거나 감산합니다.

이러한 부품들을 조합하면 NOT(토치), AND(두 반복기가 토치로 입력), OR(선 합류), NAND/NOR(다양한 조합) 등의 논리 게이트를 구성할 수 있습니다. 이 머신은 0, 1, 공백(ε), 예약 상태의 4가지 기호 알파벳을 사용합니다.

테이프 메모리 셀

각 셀은 4비트(값 0~15)를 저장하며, 활성화되면 신호를 지속적으로 출력합니다. 예를 들어 셀에 0101이 저장될 수 있습니다. 왼쪽의 버튼은 셀을 초기화합니다. 추가 비트는 향후 확장성을 위해 마련된 여유 공간입니다.

전체 테이프는 이러한 셀 8개로 구성되어 총 32비트의 저장 공간을 제공합니다.

헤드 이동 레지스터

이 레지스터는 테이프 위 읽기/쓰기 헤드의 위치를 추적합니다. 켜진 램프가 현재 활성화된 셀을 나타냅니다. 오른쪽의 버튼은 이동(좌, 우)과 초기화(헤드를 가장 왼쪽 램프로 복귀)를 제어합니다. 가장 왼쪽의 선택적 램프는 이동이 완료되었음을 알려주어 실행 루프의 타이밍 지연을 최소화하는 데 도움을 줍니다.

레지스터는 비트 시프트 연산을 처리하여 헤드를 테이프 위아래로 이동시킵니다.

프로그램 셀

각 프로그램 셀은 10비트의 명령어 데이터를 저장합니다:

• 기록할 값 4비트.
• 헤드 오프셋 2비트(10 = 왼쪽 이동, 01 = 오른쪽 이동).
• 다음 머신 상태 4비트.

연산은 기록 → 이동 → 상태 전이의 엄격한 순서를 따릅니다. 전체 프로그램은 20개의 셀을 사용하며, 4개 상태 × 4개 기호(ε 및 정지 상태 포함)를 커버합니다.

2진수-10진수 변환기

이 모듈은 2진수 주소를 10진수 형식으로 변환하여 테이프 셀을 정확히 타겟팅합니다. 입력은 오른쪽에서 들어오며(예: 2진수 10은 왼쪽에서 10진수 2로 출력), 메모리 주소 지정을 간소화합니다.

실행 주기

고정된 타이밍 지연(연산당 2초)은 명시적인 완료 신호 없이도 모든 것을 동기화 상태로 유지합니다:

• 현재 테이프 셀에서 기호를 읽습니다.
• 현재 상태와 기호를 기반으로 전이 규칙을 조회합니다.
• 전이 테이블에서 새 값을 기록합니다.
• 헤드를 왼쪽 또는 오른쪽으로 이동시킵니다.
• 다음 머신 상태로 업데이트합니다.
• 정지 상태에 도달하면 중지하고, 그렇지 않으면 주기를 반복합니다.

주황색 배선은 프로그램 모듈에서 실행 루프로 정지 신호를 전달합니다.

전체 아키텍처

완성된 구조물은 다음을 통합합니다:

• 20개의 프로그램 명령어 셀.
• 8개의 테이프 메모리 셀.
• 헤드 이동 레지스터.
• 동기화된 실행 주기.
• 2진수-10진수 주소 변환기.

실제 데모로, 이 머신은 테이프에 저장된 숫자를 성공적으로 1씩 증가시킬 수 있습니다.

핵심 요약

• 레드스톤은 표준 논리 게이트와 0~15 신호 강도를 활용해 튜링 머신 논리를 정확하게 시뮬레이션합니다.
• 4비트 메모리 셀은 확장성을 높이기 위한 내장형 중복성을 포함합니다.
• 고정된 타이밍 지연은 피드백 신호의 필요성을 제거하여 실행 루프를 간소화합니다.
• 4개 기호 알파벳과 4개 내부 상태는 20가지 가능한 전이를 생성합니다.
• 이 구조물은 2진수 증가 연산과 같은 특정 용도에서 완전히 작동합니다.

— Editorial Team