使用图灵约简证明一种语言是不可判定的

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到TM for L(ACC)，构造一个TM M‘，它首先验证输入磁带是输入x到M，然后在x上运行M。这样构造的M’如果M接受x，则接受语言{x}，如果M不接受，则接受空语言。

通过在M‘的编码上使用我们对L(偶数)的判定，我们可以判断| L(M') |是偶数(在这种情况下，L(M')是空的，M不接受x)还是奇数(在这种情况下，L(M’)= {x}，M接受x)。