Loading AI tools
来自维基百科,自由的百科全书
在计算复杂度理论内,R代表可以用图灵机解决的所有决定型问题问题。,也就是所有递归语言的集合。R也等同于包含所有可计算函数的集合。
因为一个语言只要同时有识别者(recognizer,能在此语言的输入为真时停止并且回传的图灵机)和反识别者(recognizer,能在此语言的输入为假时停止并且回传正确答案的图灵机),我们就可以单纯的把两台机器摆在一起,等待其中一个回传,来解决这个语言。所以,R这个类别等同于.
Complexity Zoo: Class R
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.