查看“︁R (複雜度)”︁的源代码

在[[計算複雜度理論]]內，'''R'''代表可以用[[圖靈機]]解決的所有[[決定型問題]]問題，也就是所有[[遞歸語言]]的集合。R也等同於包含所有[[可計算函數]]的集合。

因為一個語言只要同時有識別者（recognizer，能在此語言的輸入為真時停止並且回傳的圖靈機）和反識別者（recognizer，能在此語言的輸入為假時停止並且回傳正確答案的圖靈機），我們就可以單純的把兩台機器擺在一起，等待其中一個回傳，來解決這個語言。所以，'''R'''這個類別等同於<math>RE \cap coRE</math>.

==外部連結==
{{CZoo|Class R|R#r}}

[[Category:複雜度]]

{{複雜度類}}