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