罗素悖论 - 理发师悖论 Barber Paradox

一个小镇上的理发师，只给那些不给自己理头发的人理发
那么就会出现一个问题，如果这个理发师给自己理发（假设物理上做得到）那么他就违反了他的 slogan，因为他自己是理头发的人，他不能给理头发的人理头发
如果这个理发师不给自己理头发，那么他也违反了自己的slogan，他不给自己理头发但是他理应给自己理头发

图灵机的循环

由于我们知道图灵机能表述为一个 string (即用其的7元组进行各部分编码得)，那么我们是不是可以用另一个图灵机来处理这个图灵机？
再根据理发师悖论，我们就有了一个很叛逆的图灵机：
图灵机 TM 只接受任意不接受任意自己描述的字符串的 TM1TM_1
那么，这个特殊的 TM 可以接受其自身的描述字符串吗？
很遗憾根据悖论，这里是不行的

可决定集合

假设我们有一个语言 LAccL_{Acc} 包含了所有的 tuple (⟨M⟩,x)(\langle M\rangle, x), 其中 MM 是一个 TM, xx 是一个 string, 且 MM 接受 xx
这在生活中很常见：我们写的任何代码都是一个图灵机，那么 interpreter 就是可决定集合，它接受所有了可以解决问题的代码
这一类图灵机我们称为 全图灵机，且事实上存在，但是它并不能决定 LAccL_{Acc}

不可定集合的互相推导

一个简单的思路，就是我们用反证法假设 LAccL_{Acc} 是可以决定的，那么我们如果能找到一个确实不可定的语言，就可以证伪

图灵归纳 Turing Reduction

从 string A 到 B 的 turing reduction 写作 A≤TBA\le_T B 定义为 在拥有一个可决定 B 的 TM 的情况下，我们可以决定 A
这种机器的特性说明：

  1. 如果 B 可定则 A 可定
  2. 如果 A 不可定则 B 不可定 （这里是 contra-positive）
    那么我们就可以用这类思路来从 barber paradox 定义的语言 LBarberL_{Barber} 来证明其他语言，例如 LAccL_{Acc} 是不可定的，我们只要证明存在一个 图灵机 使得能将输入 ⟨M⟩,x\langle M\rangle, x 转变为输出之后被 barber 图灵机使用 （这里的思路是 barber 的输入是其自身 ⟨M⟩,⟨M⟩\langle M \rangle, \langle M\rangle 即二者相同
    turing_reduction.jpeg