判定问题(decision problem)

判定某类问题是否具有算法解,或者是否存在能行性的方法使得对该问题类中的每一个特例能在有限步内机械地判定它是否具有某种性质的问题。如果对某类问题已经获得这种能行的方法,就说这类问题是可判定的,或者说其判定问题是可能的;如能证明某类问题不可能存在这样的方法,就说这类问题不是能行可判定的。

判定问题有不同的表述。从语义方面看,判定问题是要确定一公式是否常真,即是否普遍有效,或是否可满足;从语法方面看,它是要确定某一公式是可证,还是可否证。

上述“是否有算法解”、“是否存在能行的方法”的说法中的“是”,指有算法解或有能行的方法,这是不成问题的,因为人们的直观至少在理论上可以判定一个解是算法解或一种方法是能行的方法,因而证明一个理论的判定问题可解,只需给出一个算法再证明算法为所求即可。对其中的“否”即不存在算法解或不存在能行的方法,则首先要把“算法”、“能行性”概念精确化,给出严格的数学定义,使它们的类成为明确的数学对象,从而能用严格的数学方法证明对某类问题它们不存在。

算法和能行性概念是在20世纪30年代中期严格化的(在研究判定问题的需要推动下,见算法、递归论),从那时起人们才得以解决大量的不可判定的问题。

判定问题成果举例:

1.可判定问题。1927年兰福德证明了自然数及有理数的线性序理论的判定问题可解;1929年普雷斯伯格证明了自然数的加法理论可判定;1940年,塔尔斯基证明了布尔代数的初等理论可判定;1948年,塔尔斯基证明了代数封闭域的初等理论可判定;1954年,什米莱夫证明了交换群的初等理论可判定;1968年,阿克斯证明了有限域的初等理论可判定。

2.不可判定问题。1936年,丘奇证明皮亚诺算术理论PA不可判定;同年,罗塞证明PA的任何无矛盾扩张都不可判定;1936年丘奇,1937年图灵证明一阶逻辑不可判定;1955年П.С.诺维科夫,1959年布恩证明群的字问题不可判定;1970年,马季亚谢维奇证明希尔伯特第10问题不可判定。

对可解的情形,有一个算法复杂性或可行性问题;对不可解问题,有一个可解度问题。

How to prove a problem is decidable or not?

The Post correspondence problem

The Post correspondence problem (PCP). Given a finite sequence of pairs (s1,t1),(s2,t2),...,(sk,tk)(s1,t1),(s2,t2),...,(sk,tk) such that all sisi and titi are binary strings of positive length, is there a sequence of indices i1,i2,...,ini1, i2, . . . , in with n ≥ 1 such that the concatenation of strings si1si2...sinsi1 si2 . . . sin equals ti1ti2...tinti1 ti2 . . . tin ?

Example: Here is an instance of the problem which we can solve successfully: the concrete correspondence problem instance is given by a sequence of three pairs

(s1, t1) (s2, t2) (s3,t3)
(1, 101) (10, 00) (011, 11)

A solution to the problem is the sequence of indices (1, 3, 2, 3) since s1s3s2s3 and t1t3t2t3 both equal 101110011

PCP is undecidable.
Note that the same number can occur in the sequence of indices. This means that the search space we are dealing with is infinite, which should give us some indi- cation that the problem is unsolvable.