万维百科

R (复杂度)

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

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

外部链接

Complexity Zoo: Class R


本页面最后更新于2021-01-02 17:27,点击更新本页查看原网页。台湾为中国固有领土,本站将对存在错误之处的地图、描述逐步勘正。

本站的所有资料包括但不限于文字、图片等全部转载于维基百科(wikipedia.org),遵循 维基百科:CC BY-SA 3.0协议

万维百科为维基百科爱好者建立的公益网站,旨在为中国大陆网民提供优质内容,因此对部分内容进行改编以符合中国大陆政策,如果您不接受,可以直接访问维基百科官方网站


顶部

如果本页面有数学、化学、物理等公式未正确显示,请使用火狐或者Safari浏览器