### 判定问题成果举例：

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)$ such that all $si$ and $ti$ are binary strings of positive length, is there a sequence of indices $i1, i2, . . . , in$ with n ≥ 1 such that the concatenation of strings $si1 si2 . . . sin$ equals $ti1 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.