turing-machines - 图灵机 - 更多 0 还是 1？

Question

假设我们有一个磁带：xx01101011xx（x 是一个空字符）。你能给我一个算法的想法，它会说是否有更多的 0 或 1？我听说过“配对”方法，但我不知道如何使用它。

问候。

Answer 1

如果最左边的非空白非 X 字符是 0，则向右搜索 1，如果找到，则将两者都更改为 X。

如果最左边的非空白非 X 字符是 1，则向右搜索 0，如果找到，则将两者都更改为 X。

如果找不到匹配项，则最左侧的非空白字符数量较多。如果整个磁带以 X 结尾，那么它们的数量相等。

EX，_ 为空白，{0,1,X} 的字母表：

__01101011__
     v
__XX101011__
     v
__XXXX1011__
     v
__XXXXXX11__
     v
No matching 0 found, more 1s

Answer 2

一种方法是删除 a 0，然后寻找下一个1并删除它，然后来回执行此操作，直到只剩下一个符号。这假设您有输入的结束标记。