我正在阅读《计算复杂性：现代方法》这本书，但我无法理解“遗忘图灵机”。
“遗忘图灵机”是这样一种图灵机，其头部的运动完全由“输入长度”决定。也就是说，该图灵机对其输入内容毫不知情。到目前为止都很好理解。
但其中一个练习要求证明以下定理：
很明显，被遗忘的 TM 不能在原始输入
我是否正确理解了这个问题？如何证明这个定理？
“遗忘图灵机”是这样一种图灵机，其头部的运动完全由“输入长度”决定。也就是说，该图灵机对其输入内容毫不知情。到目前为止都很好理解。
但其中一个练习要求证明以下定理：
If a language L is decidable in time T(n)
then there exists an oblivious TM that decides L in time O(T(n)^2).
很明显，被遗忘的 TM 不能在原始输入
L 上操作，而是在某个编码版本上操作。也就是说，定理的要点是将一个比特串编码为一个整数（即遗忘的 TM 的输入长度）。但是，如果想将可能的 L 输入集（比特串）编码为一个整数，由于长度为 n 的比特串有 2^n 个，很快就会遇到非常大的数字。我是否正确理解了这个问题？如何证明这个定理？