乘法和模块图灵机

Question

我需要帮助设计一台将计算以下的图灵机 f(x,y) = x*y mod 4. 。如何在二进制基础上解决这个问题 $x$ 和 $y$ 有两个部分吗？

Answer 1

可能会略微优化，但它可以解决问题：

假设 - 输入由两个二进制编号组成（带有领先0，SO 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清理