R (複雜度)

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

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

外部連結

Complexity Zoo: Class R

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.