Abstract Strong Turing Determinacy, or ${\mathrm {sTD}}$ , is the statement that for every set A of reals, if $\forall x\exists y\geq _T x (y\in A)$ , then there is a pointed set $P\subseteq A$ . We prove the following consequences of Turing Determinacy ( ${\mathrm {TD}}$ ) and ${\mathrm {sTD}}$ over ${\mathrm {ZF}}$ —the Zermelo–Fraenkel axiomatic set theory without the Axiom of Choice: (1) ${\mathrm {ZF}}+{\mathrm {TD}}$ implies $\mathrm {wDC}_{\mathbb {R}}$ —a weaker version of $\mathrm {DC}_{\mathbb {R}}$ . (2) ${\mathrm {ZF}}+{\mathrm {sTD}}$ implies that every set of reals is measurable and has Baire property. (3) ${\mathrm {ZF}}+{\mathrm {sTD}}$ implies that every uncountable set of reals has a perfect subset. (4) ${\mathrm {ZF}}+{\mathrm {sTD}}$ implies that for every set of reals A and every $\epsilon>0$ : (a) There is a closed set $F\subseteq A$ such that $\mathrm {Dim_H}(F)\geq \mathrm {Dim_H}(A)-\epsilon $ , where $\mathrm {Dim_H}$ is the Hausdorff dimension. (b) There is a closed set $F\subseteq A$ such that $\mathrm {Dim_P}(F)\geq \mathrm {Dim_P}(A)-\epsilon $ , where $\mathrm {Dim_P}$ is the packing dimension.

Abstract The current work includes a result announced in the year 2012 which was unproven for 10 years. The result shows that there is a co-r.e. tree with uncountably many infinite branches such that the nonisolated infinite branches of the constructed tree are all nonrecursive, generalised low, and hyperimmune-free and form a perfect tree. This article is the journal version of two conference articles from 2012 and 2022; the article contains the main result proved in 2022 and also the other major results from 2012.

Abstract We show that a computable function $f:\mathbb R\rightarrow \mathbb R$ has Luzin’s property (N) if and only if it reflects $\Pi ^1_1$ -randomness, if and only if it reflects $\Delta ^1_1({\mathcal {O}})$ -randomness, and if and only if it reflects ${\mathcal {O}}$ -Kurtz randomness, but reflecting Martin–Löf randomness or weak-2-randomness does not suffice. Here a function f is said to reflect a randomness notion R if whenever $f(x)$ is R-random, then x is R-random as well. If additionally f is known to have bounded variation, then we show f has Luzin’s (N) if and only if it reflects weak-2-randomness, and if and only if it reflects $\emptyset '$ -Kurtz randomness. This links classical real analysis with algorithmic randomness.

Abstract We prove that the continuous function ${\rm{\hat \Omega }}:2^\omega \to $ that is defined via $X \mapsto \mathop \sum \limits_n 2^{ - K\left( {Xn} \right)} $ for all $X \in {2^\omega }$ is differentiable exactly at the Martin-Löf random reals with the derivative having value 0; that it is nowhere monotonic; and that $\mathop \smallint \nolimits _0^1{\rm{\hat{\Omega }}}\left( X \right)\,{\rm{d}}X$ is a left-c.e. $wtt$ -complete real having effective Hausdorff dimension ${1 / 2}$ . We further investigate the algorithmic properties of ${\rm{\hat{\Omega }}}$ . For example, we show that the maximal value of ${\rm{\hat{\Omega }}}$ must be random, the minimal value must be Turing complete, and that ${\rm{\hat{\Omega }}}\left( X \right) \oplus X{ \ge _T}\emptyset \prime$ for every X. We also obtain some machine-dependent results, including that for every $\varepsilon > 0$ , there is a universal machine V such that ${{\rm{\hat{\Omega }}}_V}$ maps every real X having effective Hausdorff dimension greater than ε to a real of effective Hausdorff dimension 0 with the property that $X{ \le _{tt}}{{\rm{\hat{\Omega }}}_V}\left( X \right)$ ; and that there is a real X and a universal machine V such that ${{\rm{\Omega }}_V}\left( X \right)$ is rational.

Abstract We prove the following two basis theorems for ${\rm{\Sigma }}_2^1$ -sets of reals: (1) Every nonthin ${\rm{\Sigma }}_2^1$ -set has a perfect ${\rm{\Delta }}_2^1$ -subset if and only if it has a nonthin ${\rm{\Delta }}_2^1$ -subset, and this is equivalent to the statement that there is a nonconstructible real. (2) Every uncountable ${\rm{\Sigma }}_2^1$ -set has an uncountable ${\rm{\Delta }}_2^1$ -subset if and only if either every real is constructible or $\omega _1^L$ is countable. We also apply the method that proves (2) to show that if there is a nonconstructible real, then there is a perfect ${\rm{\Pi }}_2^1$ -set with no nonempty ${\rm{\Pi }}_2^1$ -thin subset, strengthening a result of Harrington [4].

Abstract Let an oracle be called low for prefix-free complexity on a set in case access to the oracle improves the prefix-free complexities of the members of the set at most by an additive constant. Let an oracle be called weakly low for prefix-free complexity on a set in case the oracle is low for prefix-free complexity on an infinite subset of the given set. Furthermore, let an oracle be called low and weakly for prefix-free complexity along a sequence in case the oracle is low and weakly low, respectively, for prefix-free complexity on the set of initial segments of the sequence. Our two main results are the following characterizations. An oracle is low for prefix-free complexity if and only if it is low for prefix-free complexity along some sequences if and only if it is low for prefix-free complexity along all sequences. An oracle is weakly low for prefix-free complexity if and only if it is weakly low for prefix-free complexity along some sequence if and only if it is weakly low for prefix-free complexity along almost all sequences. As a tool for proving these results, we show that prefix-free complexity differs from its expected value with respect to an oracle chosen uniformly at random at most by an additive constant, and that similar results hold for related notions such as a priori probability. Furthermore, we demonstrate that on every infinite set almost all oracles are weakly low but are not low for prefix-free complexity, while by Shoenfield absoluteness there is an infinite set on which uncountably many oracles are low for prefix-free complexity. Finally, we obtain no-gap results, introduce weakly low reducibility, or WLK-reducibility for short, and show that all its degrees except the greatest one are countable.

Abstract We study the strengths of various notions of higher randomness: (i) strong ${\rm{\Pi }}_1^1$ randomness is separated from ${\rm{\Pi }}_1^1$ randomness; (ii) the hyperdegrees of ${\rm{\Pi }}_1^1$ random reals are closed downwards (except for the trivial degree); (iii) the reals z in $NC{R_{{\rm{\Pi }}_1^1}}$ are precisely those satisfying $z \in {L_{\omega _1^z}}$ and (iv) lowness for ${\rm{\Delta }}_1^1$ randomness is strictly weaker than that for ${\rm{\Pi }}_1^1$ randomness.

Abstract We prove that every Turing degree a bounding some non-GL2 degree is recursively enumerable in and above (r.e.a.) some 1-generic degree.

Abstract We study the problem of existence of maximal chains in the Turing degrees. We show that: 1. ZF + DC + “There exists no maximal chain in the Turing degrees” is equiconsistent with ZFC + “There exists an inaccessible cardinal” 2. For all a ∈ 2ω, (ω1)L[a] = ω1 if and only if there exists a [a] maximal chain in the Turing degrees. As a corollary, ZFC + “There exists an inaccessible cardinal” is equiconsistent with ZFC + “There is no (bold face) maximal chain of Turing degrees”.

Abstract We prove that there exists a noncomputable c.e. real which is low for weak 2-randomness, a definition of randomness due to Kurtz, and that all reals which are low for weak 2-randomness are low for Martin-Löf randomness.

Abstract We show that the structure of recursively enumerable degrees is not a Σ1-elementary substructure of , where (n > 1) is the structure of n-r.e. degrees in the Ershov hierarchy.

Abstract We prove that for any locally countable partial order ℙ = (2ε, ≤p, there exists a nonmeasurable antichain in ℙ. Some applications of the result are also presented.

Abstract Let [NB]1 denote the ideal generated by nonbounding c.e. degrees and NCup the ideal of noncuppable c.e. degrees. We show that both [NB]1 ∩ NCup and the ideal generated by nonbounding and noncuppable degrees are new, in the sense that they are different from M, [NB]1 and NCup—the only three known definable ideals so far.

Abstract. We prove that there is no sw-complete c.e. real, negatively answering a question in [6].