recursion, metarecursion,および分解について

概要

論文の詳細を見る
This paper deals with several problems concerning the decomposition of recursively (metarecursively) enumerable sets, which has been extensively developed over the last few years. Here we present five results in this field: R 1. There are two recursively enumerable sets A, B such that, (i) A⊂B, (ii) A is recursive in B, and (iii) B-A is not recursively enumerable. R 2. There are recursively enumerable sets A, B, C, which satisfy the following conditions; (i) A and B∪C have the same degree, (ii) B∩C = φ, (iii) for arbitrary recursively enumerable sets A_0, A_1, it [numerical formula], then [numerical formula] , where A^^= denotes the degree of A. R 3. There are recursively enumerable sets A and B of the same degree such that B⊃A and such that B-A is not recursively enumerable. R 4. Let S be any non-hyperaithmetic Π: set. Then, there are Π: sets S_1, S_2, …, S_n such ahat (i) [numerical formula], (ii) [numerical formula], and (iii) there exists no hyperarithmetic set A such that S_j = S∩A, for any j. R 5. Each regular non-metarecursive metarecursively enumerable set is the disjoint union of two metarecursively enumerable sets of incomparable metadegrees.
明治大学の論文