不可判定问题

此条目需要补充更多来源。 (2018年3月12日)
请协助补充多方面可靠来源以改善这篇条目，无法查证的内容可能会因为异议提出而移除。
致使用者：请搜索一下条目的标题（来源搜索："不可判定问题" — 网页、新闻、书籍、学术、图像），以检查网络上是否存在该主题的更多可靠来源（判定指引）。

此条目可参照英语维基百科相应条目来扩充。
若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。

不可判定问题是可计算性理论和计算复杂性理论中定义的一类决定性问题，此类问题无法总是用单一算法得出正确的是/否的答案。停机问题是这类问题的一个代表：对于停机问题，没有算法能够正确判定任意程序是否会终止运行。^[1]

背景

决定性问题是一类根据从一个无限集合中选取的输入值，得出是或否的回答的问题。因此，根据传统定义，寻求答案为是的输入值之集合的问题，与决定性问题等价。

与哥德尔不完备定理的关系

不可判定问题举例

参见

^ sen., Luo; (1962-), Xu liu tong,; juan., Yang; bin., Wu; 罗森.; (1962-), 徐六通,; 杨娟.; 吴斌. Li san shu xue ji qi ying yong. 离散数学及其应用. Bei jing: Ji xie gong ye chu ban she. 2015. ISBN 9787111453826. OCLC 917593230.