用于二进制数加法和比较的图灵机

Question

今天是个好日子！

我正在尝试解决这个练习以达到学习目的。有人可以指导我解决这 3 个问题吗？

就像我尝试了第一个问题，将两个由“+”分隔的二进制数相加。我尝试通过用相应数量的 1 或零表示每个数字来进行 2 个数字加法，例如 5 = 1 1 1 1 1 或 0 0 0 0 0，然后将它们相加，结果也将采用与所表示的相同的格式，但如何添加或表示 2 个二进制文件并用 + 分隔它们，但没有得到任何线索。图灵机的头会从左边移动到+号，然后再向+号左右移动吗？但是添加将如何执行。就我所知而言，TM 不能简单地添加二进制数，我们必须制定一些逻辑来表示其二进制数，就像简单地添加 2 个数字的情况一样。比较两个二进制文件的情况是否相似？问候

Answer 1

以下程序受到edX / MITx 课程 Paradox and Infinity的启发，展示了如何使用图灵机执行二进制加法，其中要相加的数字被输入到图灵机并以空格分隔。

图灵机

• 使用第二个数字作为计数器
• 将第二个数字减一
• 将第一个数字加一

直到第二个数变为0。

下面的图灵机模拟动画展示了如何将 13（二进制1101）和 5（二进制101）相加得到 18（二进制10010）。

Answer 2

我将从问题 2 和问题 3 开始，因为它们实际上比问题 1 更容易。

我们假设我们有有效的输入（两侧都是非空二进制字符串，没有前导零），因此我们不需要进行任何输入验证。要检查数字是否相等，我们只需在 = 符号上来回跳动并一次划掉一位数字即可。如果我们发现任何一点不匹配，我们都会拒绝。如果左边还有一位数字而右边找不到，我们就会拒绝。如果左边的数字用完了，而右边还有一些，我们就会拒绝。否则，我们接受。

Q    T    Q'    T'    D

q0   0    q1    X     right    // read the next (or first) symbol
q0   1    q2    X     right    // of the first binary number, or
q0   =    q7    =     right    // recognize no next is available

q1   0    q1    0     right    // skip ahead to the = symbol while 
q1   1    q1    1     right    // using state to remember which
q1   =    q3    =     right    // symbol we need to look for
q2   0    q2    0     right
q2   1    q2    1     right
q2   =    q4    =     right

q3   X    q3    X     right    // skip any crossed-out symbols
q3   0    q5    X     left     // in the second binary number
q3   1,b  rej   1     left     // then, make sure the next
q4   X    q4    X,b   right    // available digit exists and
q4   0,b  rej   0,b   left     // matches the one remembered
q4   1    q5    X     left     // otherwise, reject

q5   X    q5    X     left     // find the = while ignoring
q5   =    q6    =     left     // any crossed-out symbols

q6   0    q6    0     left     // find the last crossed-out
q6   1    q6    1     left     // symbol in the first binary
q6   X    q0    X     right    // number, then move right
                               // and start over

q7   X    q7    X     right    // we ran out of symbols
q7   b    acc   b     left     // in the first binary number,
q7   0,1  rej   0,1   left     // make sure we already ran out
                               // in the second as well

该 TM 可以首先通过确保两个二进制字符串非空且不包含前导零（划掉它找到的任何内容）来清理输入。

做到“大于”，您可以轻松执行以下操作：

1. 检查第一个二进制数的长度（删除前导零后）是否大于、等于或小于第二个二进制数的长度（删除前导零后）。如果第一个比第二个长，则接受。如果第一个比第二个短，则拒绝。否则，继续步骤 2。

2. 与另一个问题一样检查是否相等，但如果在任何时候第一个数字为 1 而第二个数字为 0，请接受。这是可行的，因为我们知道没有前导零，数字具有相同的位数，并且我们按重要性降序检查数字。如果您发现其他不匹配或确定数字相等，则拒绝。

要添加数字，问题说要递增和递减，但我觉得仅添加进位不会变得更加困难。该过程的概要如下：

1. 从进位 = 0 开始。
2. 转到第一个数字的最低有效数字。进入状态（挖掘=X，进位=0）
3. 转到第二个数字的最低有效数字。进入状态(sum=(X+Y+进位)%2，进位=(X+Y+进位)/2)
4. 追随第二个数字并写下总和数字。
5. 返回并继续该过程，直到其中一个数字用完数字。
6. 然后，继续处理仍然有数字的数字，仅添加这些数字和进位。
7. 最后，擦除原始输入并将总和向后复制到磁带的开头。

磁带可能经历的不同步骤的示例：

#1011+101#
#101X+101#
#101X+10X#
#101X+10X=#
#101X+10X=0#
#10XX+10X=0#
#10XX+1XX=0#
#10XX+1XX=00#
#1XXX+1XX=00#
#1XXX+XXX=00#
#1XXX+XXX=000#
#XXXX+XXX=000#
#XXXX+XXX=0000#
#XXXX+XXX=00001#
#XXXX+XXX=0000#
#1XXX+XXX=0000#
#1XXX+XXX=000#
#10XX+XXX=000#
#10XX+XXX=00#
#100X+XXX=00#
#100X+XXX=0#
#1000+XXX=0#
#1000+XXX=#
#10000XXX=#
#10000XXX#
#10000XX#
#10000X#
#10000#