Sage Journals: Discover world-class research

Abstract

A set is called r-closed left-r.e. iff every set r-reducible to it is also a left-r.e. set. It is shown that some but not all left-r.e. cohesive sets are many–one closed left-r.e. sets. Ascending reductions are many–one reductions via an ascending function; left-r.e. cohesive sets are also ascending closed left-r.e. sets. Furthermore, it is shown that there is a weakly 1-generic many–one closed left-r.e. set. We also consider initial segment complexity of closed left-r.e. sets. We show that initial segment complexity of ascending closed left-r.e. sets is of sublinear order. Furthermore, this is near optimal as for any non-decreasing unbounded recursive function g, there are ascending closed left-r.e. sets A whose plain complexity satisfies $C (A (0) A (1) \dots A (n)) ⩾ n / g (n)$ for all but finitely many n. The initial segment complexity of a conjunctively (or disjunctively) closed left-r.e. set satisfies, for all $ε > 0$ , for all but finitely many n, $C (A (0) A (1) \dots A (n)) ⩽ (2 + ε) log (n)$ .

Keywords

Left-r.e. sets reducibilities Kolmogorov complexity cohesive sets weakly 1-generic sets

Get full access to this article

View all access options for this article.

References

C.S.

Calude, Information and Randomness: An Algorithmic Perspective, 2nd edn, Springer, Berlin, 2002.

G.J.

Chaitin, Incompleteness theorems for random reals, Advances in Applied Mathematics 8(2) (1987), 119–146.

R.G.

Downey and

Hirschfeldt, Algorithmic Randomness and Complexity, Springer, New York, 2010.

R.M.

Friedberg, Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication, The Journal of Symbolic Logic 23 (1958), 309–316.

C.G.

Jockusch, Semirecursive sets and positive reducibility, Transactions of the American Mathematical Society 131 (1968), 420–436.

A.H.

Lachlan, On the lattice of recursively enumerable sets, Transactions of the American Mathematical Society 130 (1968), 1–37.

Li and

Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn, Graduate Texts in Computer Science, Springer, New York, 2008.

Myhill, Solution of a problem of Tarski, The Journal of Symbolic Logic 21(1) (1956), 49–51.

K.M.

Ng, Enumeration closed left-r.e. sets are recursively enumerable, Private Communication (2015).

10.

Nies, Computability and Randomness, Oxford Univ. Press, New York, 2009.

11.

Odifreddi, Classical Recursion Theory, Studies in Logic and the Foundations of Mathematics, Vol. 125, North-Holland, Amsterdam, 1989.

12.

Odifreddi, Classical Recursion Theory, Volume II, Studies in Logic and the Foundations of Mathematics, Vol. 143, Elsevier, Amsterdam, 1999.

13.

E.L.

Post, Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society 50 (1944), 284–316.

14.

R.W.

Robinson, Simplicity of recursively enumerable sets, The Journal of Symbolic Logic 32 (1967), 162–172.

15.

RogersJr., Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge, 1987.

16.

R.I.

Soare, Cohesive sets and recursively enumerable Dedekind cuts, Pacific Journal of Mathematics 31(1) (1969), 215–231.

17.

R.I.

Soare, Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Springer, Berlin, 1987.

18.

Stephan and

Teutsch, Things that can be made into themselves, Information and Computation 237 (2014), 174–186.

19.

A.K.

Zvonkin and

L.A.

Levin, The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms, Russian Mathematical Surveys 25(6) (1970), 83–124.

Closed left-r.e. sets

Abstract

Keywords

Get full access to this article

References