[使用图灵归约法无法确定一种语言

Question

我需要证明语言L(EVEN) = { M : |L(M)| is even }不确定。

换句话说，语言L(EVEN)是所有图灵机的集合，所有图灵机都接受基数相同的某种语言。

[这里，M是某些图灵机的编码，如果存在L(EVEN)的决策器，则将其作为输入传递。

我已经使用图灵缩减完成了与此类似的其他问题，可以在此处看到一个示例：

我的问题是，我无法提出一些先前证明无法确定的语言，这对于显示L <= L(EVEN)很有用。

到目前为止，我们在课堂上介绍的不确定语言如下：

- L(emptyset) = { M | M is a TM and |L(M)| = emptyset}  
- L(ACC) = { (M, x) | M is a TM, and M accepts input x}  
- L(HALT) = { (M, x) | M is a TM, and M halts on input x}  
- L(EQ) = { (M1, M2) | M1, M2 are TMs, and L(M1) == L(M2) }  
- L(∈ - HALT) = { M | M is a TM, M halts on input ∈ } 

我还可能使用这些语言的补语，因为在补语下可判定性是封闭的。如何使用与我所包含的示例问题类似的设置，使用这些不确定的语言之一来证明L（EVEN）也是不确定的？

Answer 1

假设我们有一个L（偶数）的决策者。然后，我们可以如下确定L（ACC）：

从输入M到L（ACC）的TM，构造一个TM M'，首先验证输入磁带是M的输入x，然后在x上运行M。这样构造的M'如果M接受x，则接受语言{x}，如果M不接受，则为空语言。

通过对M'的编码使用我们的L（EVEN）判定器，我们可以确定| L（M'）|是偶数（在这种情况下L（M'）为空，M不接受x）或奇数（在这种情况下L（M'）= {x}并且M接受x）。