R (複雜度)

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

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

外部連結

Complexity Zoo: Class R