R (複雜度) 在計算複雜度理論內R代表可以用圖靈機解決的所有決定型問題問題也就是所有遞歸語言的集合R也等同於包含所有可計算函數的集合 因為一個語言只要同時有識別者recognizer能在此語言的輸入為真時停止並且回傳的圖靈機和反識別者recognizer能在此語言的輸入為假時停止並且回傳正確答案的圖靈機我們就可以單純的把兩台機器擺在一起等待其中一個回傳來解決這個語言所以R這個類別等同於 R E  c o R E displaystyle REcap coRE