比浏览器更快的访问！
21 关系: 停机问题，可计算函数，可计算性理论，可數集，复杂性类，字母表 (计算机科学)，定义域，形式语言，像 (數學)，函数，图灵机，值域，算法，补集，计算模型，邱奇-图灵论题，配对函数，递归可枚举语言，递归论，递归集合，施普林格科学+商业媒体。
停机问题
停机问题（）是逻辑数学中可计算性理论的一个问题。通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。 艾伦·图灵在1936年用對角論證法证明了，不存在解决停机问题的通用算法。这个证明的关键在于对计算机和程序的数学定义，这被称为图灵机。停机问题在图灵机上是不可判定问题。这是最早提出的决定性问题之一。 用数学语言描述，则其本质问题为: 给定一个图灵机T，和一个任意语言集合S，是否T会最终停机于每一个 s \in S。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可数的（countable）S 也是可停机的。 停机问题包含了自我指涉，本质是一阶逻辑的不自洽性和不完备性，类似的命题有理发师悖论、全能悖论等。.
新！!: 递归可枚举集合和停机问题 · 查看更多 »
可计算函数
在可计算性理论中，可计算函数（computable function）或图灵可计算函数是研究的基本对象。它们使我们直觉上的算法概念更加精确。使用可计算函数来讨论可计算性而不提及任何具体的计算模型，如图灵机或寄存器机。但是它们的定义必须提及某种特殊的计算模型。 在可计算函数的精确定义之前，数学家经常使用非正式术语可有效计算的。这个术语因此可以被认同为可计算函数。尽管这些函数被叫做有效的，它们可能极其困难。可行可计算性和计算复杂性研究可有效计算的函数。 依据邱奇-图灵论题，可计算函数精确的是使用给出无限数量的时间和存储空间的机器计算设备来计算的函数。等价的说，这个论题声称有算法的任何函数都是可计算的。 可以使用Blum公理来在可计算函数的集合上定义抽象计算复杂性理论。在计算复杂性理论中，确定一个可计算函数的复杂性的问题叫做功能性问题。.
新！!: 递归可枚举集合和可计算函数 · 查看更多 »
可计算性理论
在计算机科学中，可计算性理论（Computability theory）作为计算理论的一个分支，研究在不同的计算模型下哪些算法问题能够被解决。相对应的，计算理论的另一块主要内容，计算复杂性理论考虑一个问题怎样才能被有效的解决。.
新！!: 递归可枚举集合和可计算性理论 · 查看更多 »
可數集
在数学上，可数集，或称可列集、可数无穷集合，是与自然数集的某个子集具有相同基數（等势）的集合。在这个意义下不是可数集的集合称为不可数集。这个术语是康托尔创造的。可数集的元素，正如其名，是“可以计数”的：尽管计数永远无法终止，集合中每一个特定的元素都将对应一个自然数。 “可数集”这个术语也可以代表能和自然数集本身一一对应的集合。例子参见两个定义的差别在于有限集合在前者中算作可数集，而在后者中不算作可数集。 为了避免歧义，前一种意义上的可数有时称为至多可数，参见.
新！!: 递归可枚举集合和可數集 · 查看更多 »
复杂性类
在計算複雜度理論中，一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下--： 例如'''NP'''類就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題（Function problem）的集合，例如'''FP'''。 許多複雜度類可被描述它的數學邏輯（mathematical logic）特徵化，請見可描述的複雜度（descriptive complexity）。 而Blum公理用於不需實際計算模型就可定義複雜度類的情況。.
新！!: 递归可枚举集合和复杂性类 · 查看更多 »
字母表 (计算机科学)
在计算机科学中，字母表是字符或数字的有限集合。最常见的字母表是二元字母表。有限字符串是来自字母表的字符的有限序列；例如二元字符串是来自字母表的字符构成的字符串。字符的无限序列也可以用来自一个字母表的元素来构造。 给定一个字母表\Sigma，我们写\Sigma^*来指示在字母表\Sigma上的所有有限字符串的集合。这里的^*指示Kleene星号算子。我们写\Sigma^\infty(偶尔\Sigma^\N或\Sigma^\omega）来指示在字母表\Sigma上的所有无限序列的集合。 例如，如果我们使用二元字母表，则字符串ε, 0, 1, 00, 01, 10, 11, 000,等都将在这个字母表的Kleene闭包中（这里的ε表示空串）。 字母表在形式语言、自动机和半自动机理论中是重要。自动机如确定有限状态自动机（DFA）要求在形式定义中有字母表。.
新！!: 递归可枚举集合和字母表 (计算机科学) · 查看更多 »
定义域
定义域（Domain），是函数自变量所有可取值的集合。给定函数f:A\rightarrow B，其中A被称为是f的定义域，记作D_。f映射到陪域中的所有值的集合称为f的值域，记作f(A)或R_。 例如，函数f(x).
新！!: 递归可枚举集合和定义域 · 查看更多 »
形式语言
在数学、逻辑和计算机科学中，形式语言（Formal language）是用精确的数学或机器可处理的公式定义的语言。 如语言学中语言一样，形式语言一般有两个方面: 语法和语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论，它只研究语言的语法而不致力于它的语义。在形式语言理论中，形式语言是一个字母表上的某些有限长字符串的集合。一个形式语言可以包含无限多个字符串。.
新！!: 递归可枚举集合和形式语言 · 查看更多 »
像 (數學)
在数学中，像是一個跟函数相關的用語。.
新！!: 递归可枚举集合和像 (數學) · 查看更多 »
函数
函數在數學中為兩集合間的一種對應關係：輸入值集合中的每項元素皆能對應唯一一項輸出值集合中的元素。例如實數x對應到其平方x2的關係就是一個函數，若以3作為此函數的輸入值，所得的輸出值便是9。 為方便起見，一般做法是以符號f,g,h等等來指代一個函數。若函數f以x作為輸入值，則其輸出值一般寫作f(x)，讀作f of x。上述的平方函數關係寫成數學式記為f(x).
新！!: 递归可枚举集合和函数 · 查看更多 »
图灵机
图灵机（），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。.
新！!: 递归可枚举集合和图灵机 · 查看更多 »
值域
在数学中，函数的值域（Range）是由定义域中一切元素所能產生的所有函數值的集合。有时候也称为函数的像。 给定函数f: A\rightarrow B，集合f(A)被称为是f的值域，记为R_。值域不应跟陪域B相混淆。一般来说，值域只是陪域的一个子集。.
新！!: 递归可枚举集合和值域 · 查看更多 »
算法
-- 算法（algorithm），在數學（算學）和電腦科學之中，為任何良定义的具體計算步驟的一个序列，常用於計算、和自動推理。精確而言，算法是一個表示爲有限長列表的。算法應包含清晰定義的指令用於計算函數。 算法中的指令描述的是一個計算，當其時能從一個初始狀態和初始輸入（可能爲空）開始，經過一系列有限而清晰定義的狀態最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化算法在内的一些算法，包含了一些隨機輸入。 形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，並在其后尝试定义或者中成形。这些尝试包括库尔特·哥德尔、雅克·埃尔布朗和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算，1936年的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前，依然常有直覺想法難以定義爲形式化算法的情況。.
新！!: 递归可枚举集合和算法 · 查看更多 »
补集
在集合论和数学的其他分支中，存在--的两种定义：--和--。.
新！!: 递归可枚举集合和补集 · 查看更多 »
计算模型
计算模型（computational model）是计算科学中的一个数学模型，它使用大量的計算資源来用计算机模拟研究一个复杂系统的行为。被研究的系统通常是一个复杂的非線性系统，这种系统不易取得简单、直观的解析解。相比于推导数学分析来解决问题，它是通过在计算机中调整系统参数并研究实验结果的差异来完成模型。模型的操作理论可以从这些实验来推断/推导。 常见的计算模型有天气预报模型、地球模拟器模型、飛行模擬器模型、分子蛋白质折叠模型和神经网络模型。.
新！!: 递归可枚举集合和计算模型 · 查看更多 »
邱奇-图灵论题
#重定向 邱奇－图灵论题.
新！!: 递归可枚举集合和邱奇-图灵论题 · 查看更多 »
配对函数
在数学中，配对函数是唯一编码两个自然数到一个单一的自然数的过程。 在集合论中可以用任何配对函数来证明整数和有理数有同自然数相同的基数。在理论计算机科学中用它们把定义在自然数的向量上的函数 f:Nk → N 编码成一个新函数 g:N → N。.
新！!: 递归可枚举集合和配对函数 · 查看更多 »
递归可枚举语言
在数学、逻辑和计算机科学中，递归可枚举语言是也叫做部分可判定语言或图灵可识别语言的形式语言类型。它在形式语言的乔姆斯基层级中叫做类型-0语言。所有递归可枚举语言的类叫做RE。.
新！!: 递归可枚举集合和递归可枚举语言 · 查看更多 »
递归论
递归论或可计算性理论，是一个数理逻辑分支。它起源于可计算函数和图灵度的研究。它的领域增长为包括一般性的可计算性和可定义性的研究。在这些领域中，这门理论同证明论和能行描述集合论（effective descriptive set theory）有所重叠。 数理逻辑中的可计算性理论家经常研究相对可计算性、可归约性概念和程度结构的理论。相对于计算机科学家，他们研究次递归层次，可行的计算和公用于可计算性理论研究的形式语言。在这两个社区之间有着相当大的知识和方法上的重叠，而没有明显的界限。.
新！!: 递归可枚举集合和递归论 · 查看更多 »
递归集合
在可计算性理论中，一个自然数的子集被称为递归的、可计算的或具可判定性，如果我们可以构造一个算法，使之能在有限时间内终止并判定一个给定元素是否属于这个集合。更一般的集合的类叫做递归可枚举集合。这些集合包括递归集合，对于这种集合，只需要存在一个算法，当某个元素位于这个集合中时，能够在有限时间内给出正确的判定结果，但是当元素不在这个集合中时，算法可能会永远运行下去（但不会给出错误答案）。.
新！!: 递归可枚举集合和递归集合 · 查看更多 »
施普林格科学+商业媒体
施普林格科学+商业媒体（Springer Science+Business Media）或施普林格（Springer，），在柏林成立，是一个总部位于德国的世界性出版公司，它出版教科书、学术参考书以及同行评论性杂志，专--于科学、技术、数学以及医学领域。在科学、技术与医学领域中，施普林格是最大的书籍出版者，以及第二大世界性杂志出版者（最大的是爱思唯尔）。施普林格拥有超过60个出版社，每年出版1,900种杂志，5,500种新书，营业额为9.24亿欧元（2006年），雇有超过5,000名员工 。施普林格在柏林、海德堡、多德雷赫特（位于荷兰）与纽约设有主办事处。施普林格亚洲总部设在香港。2005年8月，施普林格在北京成立代表处。.
新！!: 递归可枚举集合和施普林格科学+商业媒体 · 查看更多 »
