A set A of nonnegative integers is computably enumerable (c.e.), also called recursively enumerable (r.e.), if there is a computable method to list its elements. The class of sets B which contain the same information as A under Turing computability (</=T) is the (Turing) degree of A, and a degree is c.e. if it contains a c.e. set. The extension of embedding problem for the c.e. degrees R = (R, <, 0, 0') asks, given finite partially ordered sets P is a subset of Q with least and greatest elements, whether every embedding of P into can be extended to an embedding of Q into R. Many of the most significant theorems giving an algebraic insight into R have asserted either extension or nonextension of embeddings. We extend and unify these results and their proofs to produce complete and complementary criteria and techniques to analyze instances of extension and nonextension. We conclude that the full extension of embedding problem is decidable.
展开▼
