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

Question

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

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

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，然后停止。

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