如何判断语言是否为R或RE或CoRE

Question

我有这三种语言，我不知道如何判断语言是R还是RE或coRE

L1={<M>| epsilon belongs to L(M)}
L2={<M><w>|M doesn't accept any prefix of w}
L3={<M>|there exists w where M accepts all the prefixes of w}

Answer 1

对于前两个，名为dovetailing的技术可以帮助您显示语言是可枚举的。对于L_1：给出所有图灵机的gödel编号，计算M1（eps）的步骤1，然后是M2（eps）的步骤1，然后是M1（eps）的步骤2,3M（eps）的1，M2的2 （eps），M1（eps）中的3 ...换句话说，坐标系的左下三角形具有“步数”和“图灵机数x”作为轴。

如果epsilon在L（Mx）中，那么它将在n个步骤中被接受。使用您的方法，当您到达坐标[x，n]时，您将检测到这一点。对于每个[x，n]都是如此，因此您可以用这种方式枚举所有机器。

由于一个单词只有一个有限数量的前缀，你也可以通过对每个前缀（不是顺序的，但也是交织的）遍历上面的坐标系统来为L2应用这个方法。因此L2也是可枚举的。

对于L3，存在w其中M接受w的所有前缀，那么对于仅包含w的第一个字母的字符串也是如此。因此，您只需要检查字母表中有限多个符号，就像L2一样。

至于三种语言的递归，请阅读例如处理你的L1的answer。