곱셈 및 모듈 튜링 머신

Question

아마도 약간 최적화 될 수 있지만 트릭을 수행합니다.

가정 - 입력은 빈 심볼 (_)으로 분리 된 두 이진 숫자 (0 대신 1 및 00 대신 01 및 01을 사용하여 0)로 구성됩니다. 결과는 x * y mod 4를 나타내는 선행의 이진수입니다.

전환 테이블 (상태 current_symbol new_symbol move_direction new_state) :

0 0 0 r 0
0 1 1 r 0
0 _ _ r 1
1 0 0 r 1
1 1 1 r 1
1 _ x r 2
2 _ 0 r 3 
3 _ 0 l 4
4 0 0 l 4
4 x x l 5
5 0 0 l 5
5 1 1 l 5
5 x x l 5
5 _ _ l 6
6 1 0 r 7
6 0 0 l 16
7 0 0 r 7
7 1 1 r 7
7 _ _ r 7
7 x x l 8
8 0 0 l 9
8 1 1 r 10
9 0 0 l 5
9 1 1 r 14
10 x x r 10
10 0 0 r 11
10 1 1 r 11
11 0 1 l 12
11 1 0 l 18
12 0 0 l 12
12 1 1 l 12
12 x x l 13
13 0 0 l 9
13 1 1 l 9
14 0 0 r 14
14 1 1 r 14
14 x x r 15
15 0 1 r 5
15 1 0 r 5
16 0 _ r 19
16 1 0 r 17
17 0 1 r 7
18 0 1 l 12
18 1 0 l 12
19 0 _ r 19
19 1 _ r 19
19 _ _ r 19
19 x _ r halt

거친 상태 설명 :

0 첫 번째 번호의 오른쪽으로 이동 (오른쪽으로 이동)
1 두 번째 숫자의 오른쪽으로 이동하고 종료 - x 추가) -
2 첫 번째 결과를 제로로 작성하십시오
3 두 번째 결과 제로를 쓰십시오
4 X로 이동 (왼쪽으로 이동)
5 첫 번째 번호의 오른쪽으로 이동 (왼쪽으로 이동)
6 올바른 숫자 감소
7 감소 - 이제 카피 번호 - 오른쪽 번호의 왼쪽 숫자로 이동
8 올바른 번호의 왼쪽 숫자를 읽습니다
9 올바른 번호의 오른쪽 숫자를 읽으십시오
오른쪽 번호의 오른쪽 숫자는 1입니다 - 결과의 오른쪽으로 이동하여 증가
11 증분 결과
12 x로 이동합니다
13 올바른 번호의 올바른 숫자를 읽으려면 이동합니다
14 결과의 왼쪽 숫자로 이동합니다
15 증분 오른쪽 번호 (참고 - 모드 4이기 때문에 우리는 단지 뒤집습니다)
16 왼쪽 숫자를 줄이려면 - 오른쪽 숫자는 0- 00을 확인하십시오.
17 우리는 왼쪽 숫자를 2로 줄였으며 이제 총 -1로 증가했습니다.
18 번 증가 결과 왼쪽 숫자가 0- 이월
19 청소