如何正式描述图灵机的这个算法？

Question

Waring：这个任务是我 80 岁的教授布置的 y/o 没有人理解他有时想要什么，我不希望有更多的标准方法来解决这个问题问题，不仅仅是因为问题很难，还因为我的教授是老派的前苏联疯子 ;)（他喜欢把简单的事情复杂化，只是为了解释为什么张贴在这里）

这个任务是纯理论题，但我不知道如何用文字形式化 问题：

9 bits binary code is given on input, we have to print "0" in output if amount of bits with value "1" are two times less than amount of bits with value "0", if this condition is false that we have to print "1" in output.

我在描述中提出的是引入一个计数器，然后对值为1的位进行计数，然后根据这个计数器进行输出，但是我被说是白痴，被告知有没有柜台的方式，我选择最困难的方式。有人知道确定输出内容的更好方法吗？

在此先致谢，如果描述看起来很乱，我们深表歉意

Answer 1

当 TM 读取输入位时，状态编号必须捕获从 0 到 9 的位数，以便我们可以识别何时到达末尾，以及看到的 1 位数，相关案例为 0、1、2、3 和 >=4。

编码所有相关可能性所需的状态少于 10*5=50 个。当机器进入指示已看到 9 个输入位的状态之一时，如果它指示已看到 3 个 1，则写入 0，否则写入 1，然后停止。

请注意，我们不需要使用磁带进行存储——输入语言是规则的，因此可以用有限状态机来决定，不需要无限存储。

Answer 2

虽然 Matt 是正确的，但您可以使用存储将此问题推广到任意输入大小。

1. 转到磁带的开头
2. 向前寻找未标记的 1。标记它。
   • 如果找不到未标记的 1，请转到第 7 步。
3. 回到磁带的开头
4. 寻找未标记的 0。标记它。
   • 如果找不到未标记的 0，请转到第 9 步。
5. 寻找另一个未标记的 0。标记它。
   • 如果找不到未标记的 0，请转到第 9 步。
6. 转到步骤 1
7. 转到输入的开头。
8. 寻找未标记的 0。
   • 如果没有找到，输出0。停止。
9. 输出1。停止。

这适用于任何输入尺寸。直觉上，我们正在为输入中的每个 1 寻找 2 0s，确保 0 位是 1 位的两倍。