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

Question

今天是个好日子！

我正在尝试解决此练习以用于学习目的。有人可以指导我解决这三个问题吗？

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

标签： binaryautomatacomputation-theoryturing-machinesturing-complete

Answer 1

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

图灵机

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

直到第二个数字变为 0。

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