用于二进制数加法和比较的图灵机
Turing machine for addition and comparison of binary numbers
大家好！
出于学习目的，我正在尝试解决此 Exercise。有人可以指导我解决这 3 个问题吗？
就像我尝试了第一个问题，将 2 个由“+”分隔的二进制数相加。我尝试通过用相应数量的 1 或零表示每个数字来尝试 2 个数字加法，例如 5 = 1 1 1 1 1 或 0 0 0 0 0 然后将它们相加，结果也将采用与表示相同的格式，但如何添加或表示 2 个二进制文件并用 + 分隔它们，没有得到任何线索。图灵机的头部会不会从左边移动到加号然后左右移动+号？但是添加将如何执行。据我所知，TM 不能简单地添加二进制文件，我们必须制定一些逻辑来表示其二进制文件，就像简单添加 2 个数字的情况一样。比较 2 个二进制文件的情况是否相似？
此致
有两种方法可以解决加法问题。假设你的输入磁带是 ^a+b$ 的形式，其中 ^ 和 $ 是告诉你你已经到达输入的正面和背面的符号。
- 您可以每步增加
b 和减少 a 1，直到 a 为 0，此时 b 将是您的答案。这是假设您可以轻松编写可以递增和递减的 TM。
- 您可以实现完整的加法 TM，就像在纸上添加二进制数一样使用进位。
对于任一选项，您都需要代码来找到 a 和 b 的最低有效位。该问题指定最高有效位在前，因此您需要从 + 开始 a，从 $ 开始 b。
例如，假设我们要递增 1011$。我们将使用的算法是找到最不重要的未标记数字。如果是 0，请将其替换为 1。如果是 1，向左移动。
- 首先找到 $，将读头移到那里。向左移动读头。
- 你看到一个
1。向左移动读头。
- 你看到一个
1。向左移动读头。
- 你看到一个
0。写 1.
- Return 读头到 $.二进制数现在是
1111$.
要比较两个数字，您需要跟踪您已经查看了哪些值。这是通过使用 "marked" 个字符扩展字母表来完成的。例如，0 可以标记为 X，1 可以标记为 Y。 X 表示“这里有一个 0，但我已经看到了。
因此，为了平等起见，我们可以从 ^ 开始 a，从 = 开始 b。 （假设输入看起来像 ^a=b$。）算法是找到 a 和 b 的开始，比较每个的第一个未标记位。第一次达到不同的值时，停止并拒绝。如果你到达 = 和 $，停止并拒绝。
让我们看看输入^11=10$:
- 读头从 ^ 开始。
- 将头部向右移动，直到找到未标记的位。
- 读一篇
1。写Y。磁带显示 ^Y1=10$。我们所处的状态代表已阅读 1.
- 向右移动头部直到找到
=。
- 将头部向右移动，直到找到未标记的位。
- 读一篇
1。这与我们之前阅读的内容相符。写一个Y.
- 向左移动头部直到找到
^。
- 转到步骤 2。
- 这一次，我们将阅读
a中的1和b中的0。我们会停下来拒绝。
希望这有助于您入门。
我将从问题 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 可以首先通过确保两个二进制字符串都非空且不包含前导零（划掉它找到的任何内容）来清理输入。
做到 "greater than"，您可以轻松地做到以下几点：
检查第一个二进制数的长度（去除前导零后）是否大于、等于或小于第二个二进制数的长度（去除前导零后） .如果第一个比第二个长，接受。如果第一个比第二个短，则拒绝。否则，继续第 2 步。
像另一个问题一样检查相等性，但如果在任何时候第一个数字中有 1 而第二个数字中有 0，则接受。这是有效的，因为我们知道没有前导零，数字具有相同的位数，并且我们正在按重要性降序检查数字。如果发现其他不匹配或确定数字相等，则拒绝。
要加数字，题目说的是递增和递减，但我觉得只加进位不会太难。程序大纲是这样的：
- 从进位 = 0 开始。
- 转到第一个数字的最低有效位。转到状态 (dig=X, carry=0)
- 转到第二个数字的最低有效位。转到状态 (sum=(X+Y+carry)%2, carry=(X+Y+carry)/2)
- 找到第二个数字并记下总和数字。
- 返回并继续该过程，直到其中一个数字 运行 超出数字。
- 然后，继续任何仍然有数字的数字，只添加那些数字和进位。
- 最后，擦除原始输入并将总和向后复制到磁带的开头。
磁带可能经历的不同步骤的示例：
#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#
受 edX / MITx 课程 Paradox and Infinity 启发，以下程序展示了如何使用图灵机执行二进制加法，其中要添加的数字输入到图灵机和由空格分隔。
图灵机
- 使用第二个数字作为计数器
- 将第二个数字减一
- 将第一个数字加一
直到第二个数字变为0。
下面模拟图灵机的动画展示了13（二进制1101）和5（二进制101）是如何相加的产生 18（二进制 10010）。
大家好！
出于学习目的，我正在尝试解决此 Exercise。有人可以指导我解决这 3 个问题吗？
就像我尝试了第一个问题，将 2 个由“+”分隔的二进制数相加。我尝试通过用相应数量的 1 或零表示每个数字来尝试 2 个数字加法，例如 5 = 1 1 1 1 1 或 0 0 0 0 0 然后将它们相加，结果也将采用与表示相同的格式，但如何添加或表示 2 个二进制文件并用 + 分隔它们，没有得到任何线索。图灵机的头部会不会从左边移动到加号然后左右移动+号？但是添加将如何执行。据我所知，TM 不能简单地添加二进制文件，我们必须制定一些逻辑来表示其二进制文件，就像简单添加 2 个数字的情况一样。比较 2 个二进制文件的情况是否相似？ 此致
有两种方法可以解决加法问题。假设你的输入磁带是 ^a+b$ 的形式，其中 ^ 和 $ 是告诉你你已经到达输入的正面和背面的符号。
- 您可以每步增加
b和减少a1，直到a为 0，此时b将是您的答案。这是假设您可以轻松编写可以递增和递减的 TM。 - 您可以实现完整的加法 TM，就像在纸上添加二进制数一样使用进位。
对于任一选项，您都需要代码来找到 a 和 b 的最低有效位。该问题指定最高有效位在前，因此您需要从 + 开始 a，从 $ 开始 b。
例如，假设我们要递增 1011$。我们将使用的算法是找到最不重要的未标记数字。如果是 0，请将其替换为 1。如果是 1，向左移动。
- 首先找到 $，将读头移到那里。向左移动读头。
- 你看到一个
1。向左移动读头。 - 你看到一个
1。向左移动读头。 - 你看到一个
0。写1. - Return 读头到 $.二进制数现在是
1111$.
要比较两个数字，您需要跟踪您已经查看了哪些值。这是通过使用 "marked" 个字符扩展字母表来完成的。例如，0 可以标记为 X，1 可以标记为 Y。 X 表示“这里有一个 0，但我已经看到了。
因此，为了平等起见，我们可以从 ^ 开始 a，从 = 开始 b。 （假设输入看起来像 ^a=b$。）算法是找到 a 和 b 的开始，比较每个的第一个未标记位。第一次达到不同的值时，停止并拒绝。如果你到达 = 和 $，停止并拒绝。
让我们看看输入^11=10$:
- 读头从 ^ 开始。
- 将头部向右移动，直到找到未标记的位。
- 读一篇
1。写Y。磁带显示^Y1=10$。我们所处的状态代表已阅读1. - 向右移动头部直到找到
=。 - 将头部向右移动，直到找到未标记的位。
- 读一篇
1。这与我们之前阅读的内容相符。写一个Y. - 向左移动头部直到找到
^。 - 转到步骤 2。
- 这一次，我们将阅读
a中的1和b中的0。我们会停下来拒绝。
希望这有助于您入门。
我将从问题 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 可以首先通过确保两个二进制字符串都非空且不包含前导零（划掉它找到的任何内容）来清理输入。
做到 "greater than"，您可以轻松地做到以下几点：
检查第一个二进制数的长度（去除前导零后）是否大于、等于或小于第二个二进制数的长度（去除前导零后） .如果第一个比第二个长，接受。如果第一个比第二个短，则拒绝。否则，继续第 2 步。
像另一个问题一样检查相等性，但如果在任何时候第一个数字中有 1 而第二个数字中有 0，则接受。这是有效的，因为我们知道没有前导零，数字具有相同的位数，并且我们正在按重要性降序检查数字。如果发现其他不匹配或确定数字相等，则拒绝。
要加数字，题目说的是递增和递减，但我觉得只加进位不会太难。程序大纲是这样的：
- 从进位 = 0 开始。
- 转到第一个数字的最低有效位。转到状态 (dig=X, carry=0)
- 转到第二个数字的最低有效位。转到状态 (sum=(X+Y+carry)%2, carry=(X+Y+carry)/2)
- 找到第二个数字并记下总和数字。
- 返回并继续该过程，直到其中一个数字 运行 超出数字。
- 然后，继续任何仍然有数字的数字，只添加那些数字和进位。
- 最后，擦除原始输入并将总和向后复制到磁带的开头。
磁带可能经历的不同步骤的示例：
#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#
受 edX / MITx 课程 Paradox and Infinity 启发，以下程序展示了如何使用图灵机执行二进制加法，其中要添加的数字输入到图灵机和由空格分隔。
图灵机
- 使用第二个数字作为计数器
- 将第二个数字减一
- 将第一个数字加一
直到第二个数字变为0。
下面模拟图灵机的动画展示了13（二进制1101）和5（二进制101）是如何相加的产生 18（二进制 10010）。