튜링 머신 (Turing Machine) : 두 개의 숫자로 이루어진 모드를 취 하시겠습니까?

Question

mod (3,7) = 3 및 mod (7,3) = 1과 같이 두 개의 음수가 아닌 숫자를 입력하고 mod 연산을 수행하는 튜링 기계를 설계하십시오. TM의 입력과 출력에 대한 가정과 형식을 명확하게 지정하십시오.

Answer 1

입력은 단락 기호로 구분 된 양의 정수 X와 Y입니다. 출력은 단일 숫자 Z입니다. TM은 단면 단일 테이프입니다.

먼저 오른쪽으로 이동하여 구분 기호를 찾으십시오. 그런 다음 X의 끝과 Y의 시작 사이에서 앞뒤로 튀어 나와 기호 쌍을 표시합니다. Y를 다 떨어지기 전에 X가 부족하면 X < Y와 X mod Y = X; 구분 기호와 그 이후의 모든 내용을 지우고 모든 테이프 기호를 단항 기호로 변경하고 halt-accept하십시오. X 이전에 Y가 부족한 경우 X에서 표시된 기호를 지워진/구분 기호로 변경하고 Y의 표시된 기호를 단항 기호로 복원 한 다음 X = Y이므로 X mod Y = (X - Y) mod Y).

는 여기 2 모드 3가 처리됩니다 방법은 다음과 같습니다

#110111# 
#1a0b11# 
#aa0bb1# 
#aa##### 
#11##### 

여기에 3 모드 2가 처리됩니다 방법은 다음과 같습니다

#111011# 
#11a0b1# 
#1aa0bb# 
#100011# 
#a000b1# 
#a###### 
#1######