R (复杂度)

在计算复杂度理论内，R代表可以用图灵机解决的所有决定型问题问题。，也就是所有递归语言的集合。R也等同于包含所有可计算函数的集合。

因为一个语言只要同时有识别者（recognizer，能在此语言的输入为真时停止并且回传的图灵机）和反识别者（recognizer，能在此语言的输入为假时停止并且回传正确答案的图灵机），我们就可以单纯的把两台机器摆在一起，等待其中一个回传，来解决这个语言。所以，R这个类别等同于$RE\cap coRE$.

外部链接

Complexity Zoo: Class R