1.停机问题
可计算性理论中的核心概念，由阿兰·图灵于1936年提出。
它研究能否通过算法判定任意计算机程序在给定输入下是否会在有限时间内停止运行。图灵证明该问题是不可判定的，即不存在通用算法可解此问题。
证明思路:
图灵的经典证明采用自我指涉反证法：假设存在停机判定机 H，构造一个新机D，令其在H(D,D）=1时陷入无限循环，否则停机。若 H 存在，则D(D）同时停机与不停机，产生矛盾。由此，停机问题不可判定。
2.希尔伯特第十问题
在1900年的巴黎国际数学家大会上，希尔伯特提出了23个未解难题，第十问题要求找到一种算法，输入任意丢番图方程（即多项式方程的未知数和系数均为整数），判断是否存在整数解。
20世纪中叶，随着可计算性理论的发展，数学家如马丁.戴维斯、希拉里·普特南、朱莉娅·罗宾逊等先后缩小了问题范围。1970年，马季亚谢维奇完成关键证明，展示了不存在这样的普遍算法。即：丢番图可解性问题是不可判定的，从而第十问题被解决为“否定”答案。
这一结论表明，存在明确的数学问题无法通过算法普遍解决，深化了人类对可计算性极限的理解。它与哥德尔不完备定理、图灵机等成果一道，奠定了现代理论计算机科学与数理逻辑的基础。
3.物理学量子多体系统的“谱隙问题”
一个量子系统的最低能态（基态）和激发态之间，是否存在一个“能量间隔”？
这个“间隔”，就叫谱隙。
结果证明：
不存在一个通用算法，可以判断所有量子多体系统是否有谱隙。
这个结果意味着：
你无法通过一个统一的“物理定律算法”，预测所有系统的性质。
4.数学一阶逻辑有效性问题
是否存在一个通用算法，输入任意一阶逻辑公式，就能判断它是不是在所有模型中都为真？
结论:不存在这样的通用算法。
这意味着如果一个公式是有效的，其证明必然是有限的。
也就是说：“真命题一定能被证明，但我们无法判断所有命题是否为真。”