图灵机比较二进制

Question

我正在尝试使用图灵模拟编写，因此形式如下：
0 1 * r 0 0 0 * r 0 0 # * * 3 0 x * r 0 0 y * r 0

。一个程序，它采用两个由">"分隔的二进制值，例如 1010>111，如果左>右，则停止-是，如果左右，则停止-否为左>右。

我想比较解决方案，如果您有兴趣，请留下您的解决方案。

Answer 1

我可能使用的方法的一些伪代码：

从

1. LHS 和 RHS 中删除所有前导零，方法是将它们替换为一些符号 - （不是空白，但不是 0、1 或>）。

2. 检查以确保 LHS 和 RHS 中的剩余位数相同。如果没有，我们可以立即根据相对长度判断LHS是否>RHS。通过来回弹跳并将 0、1 更改为 0'、1' 来做到这一点，直到/除非您在一侧用完而没有标记您需要的一侧。

3. 如果我们仍在检查，现在的过程很简单：比较 LHS 和 RHS 的第一个数字;如果 LHS（1）> RHS（1），则 LHS> RHS;如果 LHS（1）

   （1），LHS

步骤#1是输入长度中的O（n），因为我们可以在从左到右的一次扫描中做到这一点。然后，我们可以回滚到磁带的开头。

步骤 #2 是 O（n^2），因为 TM 基本上是做 n 个步骤，n - 1 个步骤，...，2 个步骤

= n（n+1）/2 - 1 个步骤总共计算 LHS 和 RHS。

步骤 #3 是 O（n^2），因为 TM 基本上执行 n/2 步 n/2 次，总共大约 n^2/4 步。

因此，时间复杂度为 O（n^2），空间复杂度为 O（n）（我们使用输入作为暂存存储器）。