Schnorr randomness and computable randomness are natural concepts of random sequences. However van Lambalgen’s Theorem fails for both randomnesses. In this paper we define truth-table Schnorr randomness and truth-table reducible randomness, for which we prove that van Lambalgen's Theorem holds. We also show that the classes of truth-table Schnorr random reals relative to a high set contain reals Turing equivalent to the high set. It follows that each high Schnorr random real is half of a real for which van Lambalgen's (...) Theorem fails. Moreover we establish the coincidence between triviality and lowness notions for truth-table Schnorr randomness. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim. (shrink)

We call an $\alpha \in \mathbb {R}$ regainingly approximable if there exists a computable nondecreasing sequence $(a_n)_n$ of rational numbers converging to $\alpha $ with $\alpha - a_n n}$ for infinitely many n. Similarly, there exist regainingly approximable sets whose initial segment complexity infinitely often reaches the maximum possible for c.e. sets. Finally, there is a uniform algorithm splitting regular real numbers into two regainingly approximable numbers that are still regular.

A Polish space is not always homeomorphic to a computably presented Polish space. In this article, we examine degrees of non-computability of presenting homeomorphic copies of compact Polish spaces. We show that there exists a $\mathbf {0}'$ -computable low $_3$ compact Polish space which is not homeomorphic to a computable one, and that, for any natural number $n\geq 2$, there exists a Polish space $X_n$ such that exactly the high $_{n}$ -degrees are required to present the homeomorphism type of $X_n$. (...) Along the way we investigate the computable aspects of Čech homology groups. We also show that no compact Polish space has a least presentation with respect to Turing reducibility. (shrink)

Say that a d.c.e. degree d is isolated by a c.e. degree b, if bMathematics Subject Classification (2000): 03D25, 03D30, 03D35 RID=""ID="" Key words or phrases: Computably (...) enumerable set – d.c.e. degree – Isolation – High/low hierarchy RID=""ID="" Ishmukhametov's research is supported by RFBR grant 01-01-00733, and Wu's research is supported by the Marsden Fund of New Zealand. Wu would like to thank his supervisor, Prof. Rod Downey, for his many helpful suggestions and comments. (shrink)

In [2], Jockusch and Shore have introduced a new hierarchy of sets and operators called the REA hierarchy. In this note we prove analogues of the Friedberg Jump Theorem and the Sacks Jump Theorem for many REA operators. MSC: 03D25, 03D55.

In this paper we define the concept of a system function language which is a language generated by a system function. We identify system function languages with recursively enumerable sets which are non-simple and co-infinite. We then define restricted system function languages and identify them with recursive sets which are co-infinite. Finally we state and prove some independence and dependence relationships between system function languages and some of the more well-known decision problems. MSC: 03D05, 03D20, 03D25.

We investigate the polynomial time isomorphic type structure of (the class of tally, polynomial time computable sets). We partition P T into six parts: D −, D^ − , C, S, F, F^, and study their p-isomorphic properties separately. The structures of , , and are obvious, where F, F^, and C are the class of tally finite sets, the class of tally co-finite sets, and the class of tally bi-dense sets respectively. The following results for the structures of and (...) will be proved, where D^ is the class of tally, co-dense, polynomial time computable sets and S is the class of tally, scatted (i.e., neither dense nor co-dense), polynomial time computable sets. 1. is a countable distributive lattice with the greatest element. 2. Infinitely many intervals in can be distinguished by first order formulas. 3. There exist infinitely many nontrivial automorphisms for . 4. is not distributive, but any interval in is a countable distributive lattice. RID=""ID="" Mathematics Subject Classification (2000): 03D15, 03D25, 03D30, 03D35, 06A06, 06B20 RID=""ID="" Key words or phrases: Computational complexity – Polynomial time – Degree structure – Lattice – Isomorphism RID=""ID="" Part of this work was done when the author was a PhD student at the University of Heidelberg under the direction of Professor Ambos-Spies. (shrink)

We show the existence of a high r. e. degree bounding only joins of minimal pairs and of a high2 nonbounding r. e. degree. MSC: 03D25.

We study for each computably bounded $\Pi ^0_1$ class P the set of degrees of c.e. paths in P. We show, amongst other results, that for every c.e. degree a there is a perfect $\Pi ^0_1$ class where all c.e. members have degree a. We also show that every $\Pi ^0_1$ set of c.e. indices is realized in some perfect $\Pi ^0_1$ class, and classify the sets of c.e. degrees which can be realized in some $\Pi ^0_1$ class as exactly (...) those with a computable representation. (shrink)

We introduce the computable FS-jump, an analog of the classical Friedman–Stanley jump in the context of equivalence relations on the natural numbers. We prove that the computable FS-jump is proper with respect to computable reducibility. We then study the effect of the computable FS-jump on computably enumerable equivalence relations (ceers).

We introduce a new hierarchy of computably enumerable degrees. This hierarchy is based on computable ordinal notations measuring complexity of approximation of${\rm{\Delta }}_2^0$functions. The hierarchy unifies and classifies the combinatorics of a number of diverse constructions in computability theory. It does so along the lines of the high degrees (Martin) and the array noncomputable degrees (Downey, Jockusch, and Stob). The hierarchy also gives a number of natural definability results in the c.e. degrees, including a definable antichain.

We review the current knowledge concerning strong jump-traceability. We cover the known results relating strong jump-traceability to randomness, and those relating it to degree theory. We also discuss the techniques used in working with strongly jump-traceable sets. We end with a section of open questions.

Given a reducibility ⩽r, we say that an infinite set A is r-introimmune if A is not r-reducible to any of its subsets B with |A\B| = ∞. We consider the many-one reducibility ⩽m and we prove the existence of a low1 m-introimmune set in Π01 and the existence of a low1 bi-m-introimmune set.

We show that there is a cuppable c.e. degree, all of whose cupping partners are high. In particular, not all cuppable degrees are${\operatorname {\mathrm {low}}}_3$-cuppable, or indeed${\operatorname {\mathrm {low}}}_n$cuppable for anyn, refuting a conjecture by Li. On the other hand, we show that one cannot improve highness to superhighness. We also show that the${\operatorname {\mathrm {low}}}_2$-cuppable degrees coincide with the array computable-cuppable degrees, giving a full understanding of the latter class.