可计算性
可计算性（Computability）是指一个实际问题是否可以使用计算机来解决。从广义上讲如“为我烹制一个汉堡”这样的问题是无法用计算机来解决的（至少在目前）。而计算机本身的优势在于数值计算，因此可计算性通常指这一类问题是否可以用计算机解决。事实上，很多非数值问题（比如文字识别，图象处理等）都可以通过转化成为数值问题来交给计算机处理，但是一个可以使用计算机解决的问题应该被定义为“可以在有限步骤内被解决的问题”，故哥德巴赫猜想这样的问题是…
标签：#計算理論
共 25 篇文章
編號 (可計算性理論)
可計算性理論裡，編號（英語：numbering、indexing等）是將一個集合的元素（如函數、有理數、圖、或形式語言的字串）編上自然數號碼。可計算性以及相關的概念最先定義在自然數上，而利用編號，可將這些概念傳遞到上述的其他集合中作討論。 常見例子有一階邏輯的哥德爾編號以及偏可計算函數的。 定義和例子 集合S的一個編號是由\mathbb{N}到S的，滿的偏函數。編號\nu在數字i的取值（若有定義）一般以\nu_i表示（而不是常見的函數表…
不可判定问题列表
這是一個不可判定问题列表。 逻辑問題 大衛·希爾伯特的可判定性。 二階Λ演算的类型推论和型別檢查。 抽象電腦（Abstract machine）問題 停机问题（決定圖靈機是否停機） 決定圖靈機是否Busy beaver（最長運行的圖靈機有相用的停机问题） 死亡率问题（mortality problem） 萊斯定理指出所有partial方程的非凡屬性，決定機器計算partial方程與其屬性是否未決定。 矩陣問題 矩陣的致命問題：表達，一個…
可计算函数
在可计算性理论中，可计算函数（computable function）或图灵可计算函数是研究的基本对象。它们使我们直觉上的算法概念更加精确。使用可计算函数来讨论可计算性而不提及任何具体的计算模型，如图灵机或寄存器机。但是它们的定义必须提及某种特殊的计算模型。 在可计算函数的精确定义之前，数学家经常使用非正式术语可有效计算的。这个术语因此可以被认同为可计算函数。尽管这些函数被叫做有效的，它们可能极其困难。可行可计算性和计算复杂性研究可有效…
递归集合
在可计算性理论中，一个自然数的子集被称为递归的、可计算的或具可判定性，如果我们可以构造一个算法，使之能在有限时间内终止并判定一个给定元素是否属于这个集合。更一般的集合的类叫做递归可枚举集合。这些集合包括递归集合，对于这种集合，只需要存在一个算法，当某个元素位于这个集合中时，能够在有限时间内给出正确的判定结果，但是当元素不在这个集合中时，算法可能会永远运行下去（但不会给出错误答案）。 定义 自然数的子集 S 被称为递归的，如果存在一个全可…