计算机理论中现在流行的一个最基本术语就是“停机问题”（the Halting Problem），其基本意思是：判断任意一个程序是否会在有限的时间之内结束运行的问题。这种解释一开始就隐含了一个主体上的混乱，“判断者”是谁？

这个问题实质源于数学和逻辑基本理论，也就是著名的希尔伯特第十问题（Hilbert's tenth problem）。1900年，德国数学家希尔伯特(David Hilbert 1862─1943)在巴黎第二届国际数学家大会上作了《数学问题》的著名讲演，提出了数学理论中的23个最困难的问题，其中的第10个问题是这样说的: Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.

注意希尔伯特的用词，作为一个大数学家和形式主义代表，他并没有用“数学方法”、“函数”或“形式方法”这样现成的术语，而是问：能否 “发明一种过程”（或“设计一种方法”）（To devise a process）去“判定”（determine）任何一个丢番图方程问题是否可解？因此，希尔伯特第十问题隐含着数学家的一种哲学上的反思，面对任何可定义的数学问题，数学的“确定性”能力究竟为何？用今天的表达方式就是：存在或不存在对任何可定义的数学问题可解的判定方法？

图灵理解了希尔伯特第十问题的真正要求，图灵具有对复杂机械过程的强大直觉能力（因此后来也成为了一个密码专家），他把人的进行计算的过程完全以符号化的形式表达出来，成为一种算法的机械模型——“图灵机”，图灵机最大的意义就是展示了算法的机械过程，虽然数学和图灵机都使用符号，但它们的组织性质完全不同，数学是纯粹的形式关系，算法则一定是实时（the Actual Time）过程，这样就把数学意义上的“可计算的”函数表达为“可计算的”机械过程，揭示了算法的“能行性”本质，在数学形式之外表达了算法关系，凸现了“算法”的特殊性质和地位，所以“丘奇－图灵论题”说，“能行可计算的”就是图灵机可计算的。

借助于对算法过程的构造性研究，图灵得到了对希尔伯特第十问题的结论，但不是通过一台机器的计算而得到一个确定性的答案，图灵只是肯定，这样的机器是设计不出来的，用今天的表达方式就是，不存在判定任何可定义的数学问题可解的方法。因此图灵是确定地否定了希尔伯特第十问题。希尔伯特第十问题的提出和图灵的否定性回答，现在统称为“判定问题”（Entscheidungsproblem）。

“判定问题”的提出和回答方式之间的关系和性质充满了复杂性，深刻地涉及对数学、逻辑、算法的本质和它们的关系的理解，有些已经成为了哲学上的困难问题，因此人们不断地从各种角度来解释，其中一个广泛的理解角度就是“悖论”方式，即众所周知的“停机问题”（the Halting Problem）。然而，图灵并没有在他的论文中提出“停机”这个术语，此术语可能来源于D.戴维斯，但戴维斯自己也没有确认：

Although Turing defined no instruction that would ever halt the machine, the problem that Turing is now attacking is studied more in the variation known as the Halting Problem. (The term originated in Martin Davis's 1958 book Computability and Unsolvability. 32) Can we define a Turing Machine that will determine whether another Turing Machine will either halt or go on forever? If we substitute the idea of circularity for halting, it's a similar problem. Can one Turing machine analyze another Turing Machine and determine its ultimate fate?－Charle Petzold’s “The Annotated Turing"

“停机问题”中的“停机”就是指计算机输出确定的答案而停机，注意，这个具有“停机”能力的机器就是能行可计算的机器，所以这里的“停机”并没有图灵机的工作中（circle－free）的那种特殊意义（http://blog.sciencenet.cn/home.php?mod=space&uid=2322490&do=blog&id=993665），“停机问题”通俗的理解，只是问计算机能不能计算所有的问题，从常识上可以理解，一方面，所有能行可计算的算法都是可以得到确定性的答案而停机的，另一方面，不存在可以解决所有问题的确定性算法，就是说这是两回事，并不冲突。

但“停机问题”对“判定问题”的替代却是采用逻辑悖论的方式设计的，就是设计一台计算机的自我指涉，即让一台计算机去判断自己能否得到正确的答案而停机，这实质只是把自指悖论变成了机器形式，最多只是解释了“停机问题”具有悖论性质，与图灵对希尔伯特问题的解决完全不同。图灵的解决是确定性的判断而不是归结到悖论——“‘判定问题’不可判断”，即“不存在对任何可定义的数学问题的判定方法”。

由于把“circle－free”换成了“停机”，就把“判定问题”偷换成了“停机问题”，如此就隐含了“所有的算法都具有不可判定的性质”，这是一个观念上的大错误，如果一台计算机或算法不能肯定自己，就推翻了“可计算性”这个概念本身，“‘停机问题’不可判定”意味着——“可计算的”机器不能肯定自己的“可计算性”！就是说，“停机问题”这种悖论式的解释“判定问题”的代价，只是将问题推进到一个更深的缠绕层次。

希尔伯特第十问题是由丢番图方程问题表达的，在数学界存在一种较狭义的理解方式，认为希尔伯特第十问题是1970年由马季亚谢维奇(Matijacevic, Y.)在普特南(Putnam,H. )、鲁宾孙(Robinson, J. B.)和戴维斯( Davis , M. D.)等人工作的基础上否定地解决了的，他们的工作证明了一个谓词是递归可枚举的，当且仅当该谓词是丢番图谓词，而递归可枚举集是不可判定的，故希尔伯特第十问题是不可解的。（参见博文：什么是“判定问题”？（4）－丢番图方程的两难问题，http://blog.sciencenet.cn/home.php?mod=space&uid=2322490&do=blog&quickforward=1&id=958109）

因此，马季亚谢维奇等人的工作只是成功地将丢番图方程问题归结到递归可枚举集，但递归可枚举集是不可判定的这个性质正是建立在“判定问题”的基础上，如果没有这个基础，马季亚谢维奇等人的工作也就没有意义。

希尔伯特第十问题的意义不仅仅是一个数学问题，也反映了数学和逻辑学基本问题后面一直存在着的哲学上的困难，所谓“数学的三次危机”等认识，不仅是数学上的，也是人类的知识、信息以及今天的人工智能所摆脱不了的本质性，在最终的意义上都源于人的不确定性本质，人就是在对自己的本质的不断深入认识中得到自己的存在意义的。