图灵机添加两个数字

Question

如何创建图灵机，它将计算两个用＃号隔开的二进制数字的总和，例如。 111＃101B，其中B是空白的？结果可以写在磁带的末尾。

Answer 1

1. 写一个图灵机将两个二进制数转换为一元（保持它们之间的空白）。
2. 写一个图灵机，用1代替空白，并从尾部切下一个数字。
3. 编写一个图灵机将一个一元数转换为二进制数。
4. 将这三台机器链接在一起。

Answer 2

你没有学过如何在小学增加数字。只是在这里实施相同的事情。用天真的方法，这是二次时间。

进一步的加速是可能的。