| 词条 | 判定问题 |
| 释义 | panding wenti 判定问题(卷名：哲学) decision problem 数理逻辑中的一个重要问题。它表现为寻求一种能行的方法、一种机械的程序或者算法，从而能够对某类问题中的任何一个在有穷步骤内确定是否具有某一特定的性质。例如，命题逻辑的任一公式是不是常真这个问题， 就可以在有穷步内按照一定的程序用真值表判定。如果对某类问题已经获得这种能行的方法，就说明这类问题是可判定的，或者说其判定问题是可解的；如能够证明某类问题不可能存在这样的方法，就说这类问题不是能行可判定的。判定问题有不同的陈述。从语义方面考虑，判定问题是要确定一公式是否常真，亦即是否普遍有效，或者可否满足；在语法方面，它是要确定某一公式是可证，还是可否证。 逻辑系统的判定问题 命题逻辑的任一公式是否常真以及是否可证都是能行可判定的。20世纪30年代美国数学家A.丘奇和英国的A.M.图林分别证明了谓词逻辑的判定问题是不可解的。对谓词逻辑公式可以用前束范式分类，前束范式是一公式，其中一切量词都未被否定地处于公式的最前方，谓词逻辑的每一公式都和一前束范式等值或者可以互推。有些前束范式类是可判定的，例如只含有全称量词的前束范式。1962年A.S.柯尔、E.F.摩尔和美籍华人学者王浩证明了不可判定的谓词逻辑公式都可以归约为凬ヨ凬式。这种不可判定的公式类型被称为归纳类。 在数学系统里，C.H.朗格弗德于1927年证明了自然数的线性序理论的判定问题是可解的。1929年，M.普利斯贝格证明了自然数的加法理论的判定问题是可解的。50年代初，A.塔尔斯基解决了初等几何理论的判定问题。1970年，苏联学者Ю.В.马季亚谢维奇证明了 D.希尔伯特所提出的23个著名数学问题中的第10个问题是不可解的。希尔伯特第10个问题是指寻找一个算法，用它能确定一任给的整系数多项式方程 p(x1，...，xn)=0是否有整数解。结果证明，这样的算法是不存在的。 证明一个理论的判定问题可解，只需给出一个算法，并证明这算法就是所要求的，问题就解决了。要证明一个理论的判定问题是不可解的，首先需要把算法（机械程序）概念精确化，并给出算法概念的严格的数学定义，使一切算法的类成为明确的数学对象，从而能用严格的数学方法证明对某个理论来说不存在解决它的判定问题的算法。判定问题的研究推动了对算法理论或称可计算性理论的研究，促进了递归函数论（见递归论）和图林机器理论的建立。 能行性和可行性 从计算复杂性方面对可解的判定问题的研究证明，一些理论虽然原则上是可判定的，但它的判定程序（算法）所需的计算步数太大，以致在实践上是不可行的。例如，就可判定的自然数的加法理论来说，已经证明，对于该理论的每一判定算法，都有长度（即符号数目）为 n的语句（公式），使得依据该算法判定此语句是否可证需要计算 22cn步（c为>0的常数）。假如取n=10，那末即使使用每秒运算一亿次的高速计算机作判定，也需要很多亿个世纪。一个重要的问题是:是否存在某些可判定的理论。而且其判定方法是快速的，在实践上是可行的。对于这个问题迄今未能作出肯定的或否定的回答。70年代以来，通过研究命题逻辑的判定方法的复杂性，发现了许多已知的组合型的判定问题都可化归为命题逻辑的判定问题，如果能找到判定命题逻辑中的公式是否为重言式的快速算法，则可随之而获得一大批判定问题的快速算法。但迄今这仍是悬案，既未能找到命题逻辑的快速判定算法，也未能证明不存在它的快速判定算法。 |
| 随便看 |
百科全书收录78206条中英文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。