Tag: Alan Turing

停机问题：程序能预测自己吗？ 问题：给定程序 P 和输入 x，你能判断 P(x) 是否会停机，还是永远运行下去吗？ 由阿兰·图灵于 1936 年提出 被证明为不可判定——不存在通用算法能解决所有情况 本质是自指问题：程序能分析另一个程序（甚至是自己）吗？ 图灵的思想实验 假设：H(P, x) 判断 P(x) 是否停机 定义下面的Python函数： def D(P): if H(P, P): while True: pass # 无限循环 …