turing-machines - 乘法和模图灵机

Question

我需要帮助设计一台可以计算以下内容的图灵机f(x,y) = x*y mod 4。如何在二进制基础中解决这个问题，$x$并且$y$有两个位？

Answer 1

可能会稍微优化一下，但它可以解决问题：

假设 - 输入（仅）由两个二进制数组成（前导 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

粗略状态说明：

• 0 向右移动第一个数字（向右）
• 1 移动到第二个数字的右侧（并终止 - 添加 x） -
• 2 写第一个结果为零
• 3 写入第二个结果为零
• 4 移动到 x（向左）
• 5 移动到第一个数字的右侧（向左）
• 6 右数减一
• 7 递减 - 现在复制数字 - 移动到右边数字的左边数字
• 8 读取右数的左数
• 9 读取正确数字的正确数字
• 右数的右 10 位为 1 - 移动到结果的右侧以递增
• 11 增量结果
• 12 移动到 x
• 13 移动以读取正确数字的正确数字
• 14 移动到结果的左数以递增
• 15 增加正确的数字（注意 - 因为它是 mod 4，我们只是在翻转）
• 16 尝试减少左数时 - 右数为 0 - 检查是否为 00？
• 17 我们将左边的数字减少了 2，现在增加到总数 -1
• 18 当递增结果左位数为 0 - 结转
• 19 清理