我需要帮助设计一个图灵机来计算以下 f(x,y) = x*y mod 4
.如何在二进制基础中解决此问题 $x$
和 $y$
有两个位?
最佳答案
可能会稍微优化,但它确实有效:
假设 - 输入(仅)由两个二进制数组成(前导 0,因此 01 代替 1 和 00 代替 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
粗略状态说明:
关于turing-machines - 乘法和模图灵机,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19836596/