computation-theory - 我如何证明语言 {w|M_w 接受 0x 如果它接受 1x} 不是递归的？

Question

我需要证明 L = {w|M_w 接受 1x 如果它接受 0x} 不是递归的

我相信这应该是赖斯定理的一个简单应用，它指出对于递归可枚举语言的任何非平凡属性 P，{w | M_w 是图灵机，L(M_w) 在 P} 中不是递归的。我对此有点不确定，因为我不太确定什么是财产；此外，我也不知道如何证明它是递归可枚举语言的具体属性。

标签： computation-theoryturing-machines

Answer 1

我对此有点不确定，因为我不太确定什么是财产；

就赖斯定理而言，属性是关于某种语言的任何逻辑陈述（命题、谓词等），对于该语言而言是真或假。如果陈述既不重言也不矛盾，则属性是非平凡的：也就是说，如果它对某些语言为真，但对其他语言不成立，则它是非平凡的。属性“|L| < 0”是矛盾的，因此是一个平凡的属性；"|L| >= 0" 是重言式的，因此是一个微不足道的属性；“|L| = 0”是一个重要的属性。

此外，我也不知道如何证明它是递归可枚举语言的具体属性。

递归可枚举语言也是“正义语言”，它们的属性也是“正义语言”的属性。它们是字符串的集合，它们的属性都涉及其中的字符串。不要纠结于语言的特定属性是否是递归可枚举语言的属性：它是。即使不是这样，使用莱斯定理的证明也不受影响：如果已知该属性不适用于递归可枚举语言并且是非平凡的，那么就知道该语言无论如何都不是递归的 - 莱斯定理不是甚至是必要的。