图灵机比较二进制

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）< RHS（1），LHS < RHS。如果LHS（1）= RHS（1），则删除这两个，然后再重复第3步。如果所有的数字都没有了，那么这些数字是相等的，你停下来 - 不。

步骤＃1在输入长度为O（n），因为我们可以从左到右进行一次扫描。然后我们可以回滚到磁带的开头。由于TM基本上执行n个步骤，n-1个步骤，...，2个步骤= n（n + 1）/ 2 - 1个步骤，所以步骤＃2是O（n^2） LHS和RHS。

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

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