不可判定问题
不可判定问题是可计算性理论和计算复杂性理论中定义的一类决定性问题，此类问题无法总是用单一算法得出正确的是/否的答案。停机问题是这类问题的一个代表：对于停机问题，没有算法能够正确判定任意程序是否会终止运行。 背景 决定性问题是一类根据从一个无限集合中选取的输入值，得出是或否的回答的问题。因此，根据传统定义，寻求答案为是的输入值之集合的问题，与决定性问题等价。 与哥德尔不完备定理的关系 不可判定问题举例 参考资料
标签：#计算理论
共 10 篇文章
自指
是自指的一个符号。]] 自指（）是一种概念，涉及对自身或自身的属性、特征、行为进行指称。自指现象可以出现在语言、逻辑、数学、哲学、计算机程序设计、二阶控制论、语言学及幽默等多个领域。 在自然语言或形式语言中，自指是指句子、思想或公式直接或间接地提及自身。具体表达方式可以是直接自指、通过中介句子或公式、或通过某种编码实现。自指语句有时会导致悖论，例如说谎者悖论，也可能具有递归特性。 在哲学中，自指亦指代主体谈论或提及自身的能力，即能够用第…
柯氏复杂性
在算法信息论（计算机科学和数学的一个分支）中，一个对象比如一段文字的柯氏复杂性（亦作柯尔莫哥洛夫复杂性、描述复杂性、柯尔莫哥洛夫-复杂度、随机复杂度，或算法熵）是衡量描述这个对象所需要的信息量的一个尺度。柯氏复杂性是由安德雷·柯尔莫哥洛夫于1963年发现，所以用他的名字命名。 以下面的两个长度为64的字符串为例。 01010101010101010101010101010101010101010101010101010101010101…
波斯特对应问题
波斯特对应问题（）是美国数学家埃米尔·波斯特（）于1946年提出的一个不可判定问题。 问题 已知字母表A是包含至少两个字符的有限集合。A上的一个字符串是指由A中字符组成的一个有限序列。假设\alpha_{1}, \ldots, \alpha_{N}和\beta_{1}, \ldots, \beta_{N}是由A上的字符串所组成的两个相同长度的表。如果存在一个序列(i_k)_{1 \le k \le K}（K \ge 1，且对所有k都有 …
图灵焦油坑
图灵焦油坑（）是指功能过于灵活而难以学习和使用的程序设计语言或计算机接口。 1982年艾伦·佩利在《》中发明了这一术语： 凡是图灵完备的语言都可以写任意程序，因此不严格地来说各种编程语言是等价的。但理论上的能力在实践中的实用性往往并不相同。图灵焦油坑是指一个非常简单的抽象机，实现中的各种细节都要求用户自行处理。它的另一个极端是几乎不需要人为干涉就能执行所有任务的接口，但一旦需求轻微改变就需要调整源代码。 像Brainfuck这样深奥的编…
可计算性理论
在计算机科学中，可计算性理论（Computability theory）作为计算理论的一个分支，研究在不同的计算模型下哪些算法问题能够被解决。相对应的，计算理论的另一块主要内容，计算复杂性理论考虑一个问题怎样才能被有效的解决。 历史与递归论的联系 计算模型 图灵机和邱奇－图灵论题 图灵机的可计算性理论 我们考虑关于图灵机的可计算性理论。本节中，固定字符集是{0, 1}，\{0, 1\}^是所有有限长度字符串的集合。一个语言即是\{0, …
诺谟图
（Smith charts），用于表示阻抗与导线长度的关系]] 诺莫图（），也称列线图，是一种利用图像来进行计算（查图）的工具，是一个二维的图像，用来进行非精确的计算。其使用的坐标系不同于笛卡尔坐标系。用另一种方式来解释，诺谟图是一个带有坐标的二维函数图像，通过它，如果已知了第n-1个参数，就可以用来查得第n个参数，或者通过固定一些参数来研究固定参数和未固定参数之间的关系。就像计算尺一样，诺谟图是一种图形计算工具，其精度也取决于查图时的…
克莱尼–波斯特定理
克莱尼–波斯特定理（）是可計算性理論中關於不可解度的定理，声称存在且可从停机问题计算出一对互相不可计算的不可解度。 内容 存在不可解度 A,B，使 \mathbf0^\prime\ge_TA、\mathbf0^\prime\ge_TB 且 A,B 互不可计算。 相关定理 弗里德堡–穆奇尼克定理是克莱尼–波斯特定理的强化形式。 波斯特定理 克莱尼–波斯特定理 波斯纳–罗宾逊定理 * 跳躍逆轉定理 参考资料
弗里德堡–穆奇尼克定理
弗里德堡–穆奇尼克定理（）是可計算性理論中關於不可解度的定理，声称存在一对互相不可计算的递归可枚举不可解度。 内容 存在递归可枚举不可解度 A,B 互不可计算。 相关定理 波斯特定理 克莱尼–波斯特定理 波斯纳–罗宾逊定理 跳躍逆轉定理 参考资料
＃P
在计算复杂性理论中，#P（读作）是一组与NP中的判定性问题相关的计数问题。 外部連結 * [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Symbols#sharpp Complexity Zoo: Class #P]