튜링 기계 작동 원리

튜링 기계는 테이프 (TAPE), 읽기 및 쓰기 헤드 (HEAD), 상태 레지스터 (STATEREGISTER), 전송 함수 (TRANSITIONFUNCTION) 등의 부분으로 구성됩니다.

1, 테이프 (TAPE): 테이프는 길이가 무한한 1 차원 밴드로, 각각 하나의 기호를 보관할 수 있는 일련의 인접한 격자로 나누어져 있으며, 일반적으로 특수 공백 기호가 포함된 유한 알파벳에서 나옵니다.

2, 읽기 및 쓰기 헤드 (HEAD): 읽기 및 쓰기 헤드는 테이프 위에서 좌우로 한 번에 한 칸씩 이동할 수 있습니다. 현재 가리키는 격자의 기호를 읽고 규칙에 따라 해당 격자의 기호를 변경할 수 있습니다.

3, 상태 레지스터: 상태 레지스터는 튜링 기계의 현재 상태를 기록하는 데 사용되며, 상태 수는 제한되어 있으며, 하나 이상의 상태가 가동 중지 상태로 지정되어 계산이 끝났음을 나타냅니다.

4, 변환 함수 (TRANSITIONFUNCTION): 이동 방향 (왼쪽 또는 오른쪽), 기록되는 기호, 상태 레지스터의 다음 등 현재 상태와 읽기 및 쓰기 헤드가 읽는 기호를 기준으로 읽기 및 쓰기 헤드의 다음 동작을 결정하는 규칙 세트입니다 튜링기는 영국의 수학자이자 논리학자 알란 튜링이 제안한 추상적인 계산 모델이다.