对Introduction to the Theory of Computation 3rd Theorem 9.20 的一些理解

  • 证明中,通过枚举所有的P时间内运行的图灵机,然后利用对角化方法,来构造集合$A$,使得对于某一个$M_i$和某一个选定的$n$,要么$M_i$识别$1^n$,但是$A$不包含长度为n的字符串,要么$M_i$不识别$1^n$,但是$A$包含某一个长度为n的字符串。并且,为了使得$M_i$与$n$可以一一对应,要求所选取的$n$单调增长
  • 按照文中描述的方法,构造似乎可以成立。但是,有一个重要的地方作者没有提及——无论集合$A$是否构造好,我们都应该可以运行任意一台$M_i$,$M_i$行为要保持一致
  • 在我们运行$M_i$来构造集合$A$ 的过程中,每次$M_i$查询orcale,orcale都会因为长度为$n$ 的字符串尚未被决定是否加进去集合$A$而回答NO,不过,如果我们决定长度为$n$的字符串是否加进去集合$A$中后,orcale会如实回答。那么,在长度为n的字符串被决定是否加进去集合$A$之前和之后,orcale对某些字符串的回答不一致是否会导致$M_i$ 的行为改变,从而本来$M_i$不识别$1^n$,现在却识别了$1^n$,或者相反
  • 可以证明,无论$A$是否构造好,$M_i$的行为还是会保持一致
  • 一开始,长度为$n$的字符串还没有加进去时,orcale都是回答NO,所以:
    • 如果$M_i$不识别$1^n$,我们就给$A$加进去一个$M_i$没有询问到长度为n的字符串,从而,虽然集合$A$现在有了长度为$n$的字符串,但是,对于输入$1^n$,$M_i$对orcale的询问的答案依然全部是NO——因为输入确定,$M_i$确定,所以$M_i$究竟会询问orcale哪些字符串也是确定的——只要我们保证对询问的回答是一致的
    • 如果$M_i$识别$1^n$,那么我们根本就不会给集合$A$加进去长度为$n$的字符串,那么,对于输入$1^n$,orcale对$M_i$的询问的结果依然全部是NO
  • 这个证明要成立还有一个很重要的地方,图灵机是可数个的,因为对于每一台$M_i$,我们都使用独特的$n$,那么,如果图灵机有不可数个,这个一一对应关系就无法建立。