克莱恩星无法分辨

Question

我知道，如果L是可判定的，我们可以通过构造一个图灵机来证明L*也是可判定的，但是我很难解决这个问题:如果L是不可判定的，那么L*也是不可判定的。这句话是真的还是假的？

Answer 1

这是假的。让我成为任何不可理喻的语言。定义R为L，并将长度为1的所有字符串添加到其中(如果不是L的一部分)。根据定义，r包含字母表上长度为1的所有字符串。此外，由于L是不可判定的，因此R也必须如此(不可判定语言和有限语言的结合也是不可判定的；参见下面的注释)。但是R*包含字母表上的所有字符串，这是一种可判定的语言(实际上，它是规则的)。为了明确起见，我们刚刚展示了如何从任何无法判断的语言构造另一种语言，这是索赔的反例。

若要证明不可判定语言与有限语言的结合必然是不可判定的，则假定L并R是可判定的，其中L不可判定，R是有限的。也就是说，有一个TM决定L联合R的成员资格，我们知道有一个TM决定L相交R，因为如果R是有限的，那么它与其他任何事物的交集也是有限的。但L= (L union R) But减号R)并(L相交R)：

1. L-并R是L或R中的一切
2. 集合减R是L中的一切，而不是R中的。
3. 联合(L相交R)是L中的一切。

由于可判定语言在固定的差异和结合下是封闭的，这意味着L必须是可判定的，这是一个矛盾。因此，对于不可判定的L和有限的R，L并R是不可判定的。