R (複雜度)

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

外部連接[编辑]

Complexity Zoo: Class R