Extending the Cooper Minimal Pair Theorem  

作　　者：张再跃 

出　　处：《Journal of Computer Science & Technology》2001年第1期77-85,共9页计算机科学技术学报（英文版）

基　　金：This reserch is supported by the National Natural Science Foundation of China (No.19971090).

摘　　要：In the study of cappable and noncappable properties of the recursively enumerable (r.e.) degrees, Lempp suggested a conjecture which asserts that for all r.e. degrees a and b, if a ≮ b then there exists an r.e. degree c such that c ≮ a and c ≮ b and c is cappable. We shall prove in this paper that this conjecture holds under the condition that a is high. Working below a high r.e. degree h, we show that for any r.e. degree b with h ≮ b, there exist r.e. degrees aO and al such that a0, al ≮ b, aO,a1 ≮ h, and aO and a1 form a minimal pair.In the study of cappable and noncappable properties of the recursively enumerable (r.e.) degrees, Lempp suggested a conjecture which asserts that for all r.e. degrees a and b, if a ≮ b then there exists an r.e. degree c such that c ≮ a and c ≮ b and c is cappable. We shall prove in this paper that this conjecture holds under the condition that a is high. Working below a high r.e. degree h, we show that for any r.e. degree b with h ≮ b, there exist r.e. degrees aO and al such that a0, al ≮ b, aO,a1 ≮ h, and aO and a1 form a minimal pair.

关 键 词：recursively enumerable degree minimal pair 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]