Sipser 的 TOC 书中的定理 5.3 是关于 Regular_TM = {M | M 是图灵机 (TM)，L(M) 是常规语言}。为了达到矛盾，假设 TM R 是 Regular_TM 的决定者，然后 R 用于决定 Acceptance 问题，如打击 TM S 所示：
S = "On input (M,w) where M is a TM and w is a string:
1. Construct the code of TM M2 as follows:
M2 = "On input x:
(a) If x of the form 0^n1^n, accept.
(b) else, run M on w and if M accepts w, then accept."
2. Run R on (M2).
3. If R accepts, accept; if R rejects, reject."
我有两个问题。第一个是 M_2 中的 x 固定吗？如果不是，它来自哪里？
第二个问题。为什么我们关心 M2 中的 x。如果 R 真的是一个决策者，我们为什么要关心检查 x 是否在 0^n1^n 中。那么下面的 TM S' 有效吗？
S = "On input (M,w) where M is a TM and w is a string:
1. Construct the code of TM M2 as follows:
M2 = "On input x: //ignore x
(a) run M on w and if M accepts w, then accept else reject."
2. Run R on (M2).
3. If R accepts, accept; if R rejects, reject."