徽标
联盟百科
通讯
下载应用,请到 Google Play
新! 在您的Android™设备上下载联盟百科!
自由
比浏览器更快的访问!
 

R (複雜度)和可计算函数

快捷方式: 差异相似杰卡德相似系数参考

R (複雜度)和可计算函数之间的区别

R (複雜度) vs. 可计算函数

在計算複雜度理論內,R代表可以用圖靈機解決的所有決定型問題問題。,也就是所有遞歸語言的集合。R也等同於包含所有可計算函數的集合。 因為一個語言只要同時有識別者(recognizer,能在此語言的輸入為真時停止並且回傳的圖靈機)和反識別者(recognizer,能在此語言的輸入為假時停止並且回傳正確答案的圖靈機),我們就可以單純的把兩台機器擺在一起,等待其中一個回傳,來解決這個語言。所以,R這個類別等同於RE \cap coRE. 在可计算性理论中,可计算函数(computable function)或图灵可计算函数是研究的基本对象。它们使我们直觉上的算法概念更加精确。使用可计算函数来讨论可计算性而不提及任何具体的计算模型,如图灵机或寄存器机。但是它们的定义必须提及某种特殊的计算模型。 在可计算函数的精确定义之前,数学家经常使用非正式术语可有效计算的。这个术语因此可以被认同为可计算函数。尽管这些函数被叫做有效的,它们可能极其困难。可行可计算性和计算复杂性研究可有效计算的函数。 依据邱奇-图灵论题,可计算函数精确的是使用给出无限数量的时间和存储空间的机器计算设备来计算的函数。等价的说,这个论题声称有算法的任何函数都是可计算的。 可以使用Blum公理来在可计算函数的集合上定义抽象计算复杂性理论。在计算复杂性理论中,确定一个可计算函数的复杂性的问题叫做功能性问题。.

之间R (複雜度)和可计算函数相似

R (複雜度)和可计算函数有(在联盟百科)2共同点: 图灵机递归语言

图灵机

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

R (複雜度)和图灵机 · 可计算函数和图灵机 · 查看更多 »

递归语言

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

R (複雜度)和递归语言 · 可计算函数和递归语言 · 查看更多 »

上面的列表回答下列问题

R (複雜度)和可计算函数之间的比较

R (複雜度)有3个关系,而可计算函数有25个。由于它们的共同之处2,杰卡德指数为7.14% = 2 / (3 + 25)。

参考

本文介绍R (複雜度)和可计算函数之间的关系。要访问该信息提取每篇文章,请访问:

嘿!我们在Facebook上吧! »