Rod Downey

A longstanding question is to characterize the lattice of supersets (modulo finite sets), $\mathcal {L}^*(A)$ , of a low $_2$ computably enumerable (c.e.) set. The conjecture is that $\mathcal {L}^*(A)\cong {\mathcal E}^*$ . In spite of claims in the literature, this longstanding question/conjecture remains open. We contribute to this problem by solving one of the main test cases. We show that if c.e. A is low $_2$ then A has an atomless hyperhypersimple superset. In fact, if A is c.e. and low $_2$ , then for any $\Sigma _3$ -Boolean algebra B there is some c.e. $H\supseteq A$ such that $\mathcal {L}^*(H)\cong B$ .

We investigate the problem of punctual (fully primitive recursive) presentability of algebraic structures up to primitive recursive and computable isomorphism. We show that for mono-unary structures and undirected graphs, if a structure is not punctually categorical then it has infinitely many punctually non-isomorphic punctual presentations. We also show that the punctual degrees of any computably almost rigid structure as well as the order ( $$\mathbb {Z},<$$ Z , < ) are dense. Finally we characterise the Boolean algebras which have a punctually 1-decidable presentation that is computably isomorphic to a 1-decidable presentation.

Let K denote prefix-free Kolmogorov complexity, and let $K^A$ denote it relative to an oracle A. We show that for any n, $K^{\emptyset ^{(n)}}$ is definable purely in terms of the unrelativized notion K. It was already known that 2-randomness is definable in terms of K (and plain complexity C) as those reals which infinitely often have maximal complexity. We can use our characterization to show that n-randomness is definable purely in terms of K. To do this we extend a certain “limsup” formula from the literature, and apply Symmetry of Information. This extension entails a novel use of semilow sets, and a more precise analysis of the complexity of $\Delta _2^0$ sets of minimal descriptions.