computer-science - 如何构建这个图灵机？

Question

我们如何构建 TM 使其接受（仅提供描述）：

a + b = c

一个 。b = c

输入的格式为 a#b#c。

a,b 和 c 属于 {0,1}* 并且是正二进制无符号整数。

我知道如果输入具有一元表示，我们可以构造 TM，但是如果它具有二进制表示，如何解决？

Answer 1

嗯，二进制加法和乘法比一元的情况要复杂一些，但并不难。补充：

1. 将两个最低位相加。如果总和为零或一，则这是结果的最低位。如果和为 2，则最低位为零，并且您有进位。
2. 继续下一个最低位。将两者和可能的进位相加。如果和为零或一，这是结果的当前位。如果和为 2，则当前位为零并且您有进位。如果总和为 3，则当前位为 1，并且您有进位。
3. 重复 2 直到处理完所有位。

对于乘法，您可以使用这样的方法。如果您真的必须详细进行，这将是在 TM 上编程的一些工作。