|
应该复习一下为什么可计算理论只需要考虑判定性问题。设 f 是 x |-> y 的函数，其中 x, y 是 {0,1} 上的字符串，令
L' = { (x, n, b) : |f(x)| > n 且 b = f(x)[n] },
则 L' 在可计算意义下等同于 f ，其中有序对采用通常的编码。
令 x 为一个特殊疑问句，问：
你对 x 的答案的 UTF-8 编码有至少 1 个字节吗？
你对 x 的答案的 UTF-8 编码的第 1 个字节的第 1 位是 0 吗？
...
你对 x 的答案的 UTF-8 编码的第 1 个字节的第 8 位是 0 吗？
你对 x 的答案的 UTF-8 编码有至少 2 个字节吗？
...
对于随机化问题，可以先去随机化。 |
