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

Question

大家好！

我正在尝试解决这个练习，以便学习。可以有人指导我如何解决这三个问题吗？

例如，我尝试了第一个问题，即将由“+”分隔的2个二进制数相加。在此，我通过用各自数量的1或零来表示每个数字进行2个数字的相加，例如5 = 1 1 1 1 1 或 0 0 0 0 0，然后将它们相加，结果也将以与表示方式相同的格式呈现。但是如何添加或表示2个二进制数并将它们分开，却毫无头绪。图灵机的头部会从左边移动并到达加号，然后向加号的左右移动吗？但是该如何执行加法？就我的一点知识而言，TM不能简单地添加二进制数，我们必须制定某些逻辑来表示其二进制数，就像简单的2个数字相加的情况一样。比较2个二进制数也是如此。

谢谢。

- Muhammad Asif Raza

Answer 1

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

图灵机：

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

直到第二个数字变为0。

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

- Sandipan Dey

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. 转到第一个数字的最低有效位。 转到状态（dig=X，carry=0）
3. 到达第二个数字的最低有效位。 转到状态（sum=(X+Y+carry)%2，carry=(X+Y+carry)/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#

- Patrick87

Answer 3

有两种方法可以解决加法问题。假设您的输入磁带的格式为^a+b$，其中^和$是告诉您已经到达输入的前面和后面的符号。

1. 您可以每步将b增加1并将a减少1，直到a为0，在这一点上，b将是您的答案。这是假设您能够编写一个可以增加和减少的TM。
2. 您可以实现一个完整的加法TM，使用进位，就像在纸上添加二进制数字一样。

对于任何一种选项，您需要编写代码来找到a和b的最低有效位。该问题指定了最高有效位在首位，因此您将从+开始查找a和$开始查找b。

例如，假设我们想要增加1011$。 我们将使用的算法是找到最不重要的未标记数字。 如果它是0，则用1替换它。 如果是1，则向左移动。

1. 从找到$开始，将读取头向那里移动。 将读取头向左移动。
2. 您看到1。 向左移动读取头。
3. 您看到1。 向左移动读取头。
4. 您看到0。写入1。
5. 将读取头返回到$。 二进制数现在为1111$。

要比较两个数，您需要跟踪已经查看过的值。 这通过扩展带有“标记”字符的字母表来完成。例如，0可以标记为X，1可以标记为Y。 X表示“这里有一个0，但我已经看到了它。”

因此，对于相等性，我们可以从a的^开始，从b的=开始。（假设输入看起来像^a=b$。）算法是找到a和b的开头，比较每个未标记位的第一个位。第一次到达不同的值时，停止并拒绝。如果到达=和$，则停止并拒绝。

让我们看看输入^11=10$：

1. 读头从^开始。
2. 将读头向右移动，直到找到一个未标记的位。
3. 读取1。写入Y。磁带读取^Y1=10$。我们处于表示已读取1的状态。
4. 将读头向右移动，直到找到=。
5. 将读头向右移动，直到找到一个未标记的位。
6. 读取1。这与我们之前读取的位匹配。写入Y。
7. 将读头向左移动，直到找到^。
8. 返回步骤2。
9. 这次，在a中读取1并读取b中的0。我们将停机并拒绝。

希望这可以帮助您入门。

- Welbog

---

感谢@Welbog提供详细的答案。在第三个问题中，我们如何比较和读取第一个数字大于第二个数字时才能根据问题的要求接受或拒绝？谢谢。 - Muhammad Asif Raza

所以我们必须比较两边，例如比较10101 = 11111，我们逐个比较=左侧的每个数字，如果左侧数字小于右侧数字，则拒绝。在这个例子中，当进行第二次比较时，字符串被拒绝了。对吗？ - Muhammad Asif Raza