| 波斯特问题 Post's problem 美国波斯特于1944年提出的关于不可解度问题。即在递归T度O和含K集的递归可枚举T度O′间，是否存在不同于它们的递归可枚举T度a?递归T度指含有一个递归集的任意T度。递归可枚举T度指含有一个递归可枚举集的任意T度，简记作r.e.T度。集合K=｛n｜Tn(n)停机｝，是递归可枚举的非递归集。所有递归集组成唯一的一个递归T度，记作O0它是唯一的最小度。令O′为含集合K的r.e.T度，它是所有r.e.T度中最大的。显然，O<O′。波斯特问题也可以这样叙述：是否存在一个r.e.T度a，使得O<a<O′?直到1956年，由弗列特伯格(Friedberg)和摩契尼克(Мучник)解决了这一问题。他们的结论是：存在两个递归可枚举但非递归的集A，B，使得A≤\\TB与B≤\\TA(这时称A与B是不可比较的)。于是令a=dT(A)(即含有A的T度)，b=dT(B)(即含有B的T度)，则有O<a<O′，O<b<O′。 |