R (複雜度)

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

3 关系: 图灵机，递归语言，決定性問題。

图灵机

图灵机（），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。.

新！!: R (複雜度)和图灵机 · 查看更多 »

递归语言

在数学、逻辑和计算机科学中，递归语言或遞迴語言是也叫做可判定语言或图灵可判定语言的形式语言类型。所有递归语言的类经常被称为 R。这种语言类型在乔姆斯基层级中没有定义。.

新！!: R (複雜度)和递归语言 · 查看更多 »

決定性問題

在可計算性理論與計算複雜性理論中，所謂的決定性問題（Decision problem）是一個在某些形式系統回答是或否的問題。例如：「給兩個數字x與y，x是否可以整除y？」便是決定性問題，此問題可回答是或否，且依據其x與y的值。 決定性問題與功能性問題（Function problem，或複雜型問題）密切相關，功能性問題的答案內容，較簡單的是與非複雜許多。範例問題：「給予一個正整數x，則哪些數可整除x？」 另一個與上述兩類問題相關的是最佳化問題（Optimization problem），此問題關心的是尋找特定問題的最佳答案。 解決決定性問題的方法稱為決策程式或演算法。一個針對決定性問題的演算法將說明給予參數x和y的情況下如何決定x是否整除y。若是某些決定性問題可以被一些演算法所解決，則稱此問題可決定。 計算複雜度的領域中，分類可決定問題的依據在於此問題有多難被解決。在此標準下，所謂的難是以解決某問題最有效率的演算法所花費的計算資源為依據。在遞迴理論中，非決定性問題由圖靈度決定，指的是一種在任何解答中隱含的不可計算性量詞。 計算性理論的研究集中在決定性問題上。在與功能性問題的等值問題中，並沒有失去其普遍性。.

新！!: R (複雜度)和決定性問題 · 查看更多 »

联盟百科是组织像一个百科全书或字典中的概念图和语义网络。它给每一个概念及其关系的简单定义。

这是用作概念图的基础的大型在线心理地图。 它是免费使用，每篇文章或文档可以下载。 它是一个工具，资源或学习，研究，教育，学习或教学参考书，也可以由教师，教育工作者，学生或学生; 对于学术界：学校，小学，中学，高中，初中，大学，工科学历，大专，本科，硕士或博士学位; 对于论文，报告，项目，理念，文档，调查，汇总，或论文。 这里的定义是，说明中，描述，或每显著在其上需要的信息的含义，并且它们的相关概念，作为词汇列表。 可在中文, 英文, 西班牙文, 葡萄牙文, 日文, 法文, 德文, 意大利文, 波兰文, 荷兰文, 俄文, 阿拉伯文, 印地文, 瑞典文, 乌克兰文, 匈牙利文, 加泰罗尼亚文, 捷克文, 希伯来文, 丹麦文, 芬兰文, 印度尼西亚文, 挪威文, 罗马尼亚文, 土耳其文, 越南文, 한국어, 泰语, 希腊语, 保加利亚语, 克罗地亚语, 斯洛伐克语, 立陶宛语, 菲律宾人, 拉脱维亚语, 爱沙尼亚语 和 斯洛文尼亚语。 更多语言很快。

所有的信息是从维基百科提取它的知识共享 署名-相同方式共享 3.0协议下可用。

联盟百科不受维基媒体基金会的认可或附属。

Google Play、Android 和 Google Play 徽标均为 Google Inc. 的商标。

隐私政策