Search

Given any 1-random set $X$ and any $r\in(0,1)$, we construct a set of intrinsic density $r$ which is computable from $r\oplus X$. For almost all $r$, this set will be the first known example of an intrinsic density $r$ set which cannot compute any $r$-Bernoulli random set. To achieve this, we shall formalize the {\tt into} and {\tt within} noncomputable coding methods which work well with intrinsic density., 15 pages, Included revisions suggested by Laurent Bienvenu, Denis Hirschfeldt, and an anonymous referee

This work contributes to the program of studying effective versions of “almost-everywhere” theorems in analysis and ergodic theory via algorithmic randomness. Consider the setting of Cantor space $\{0,1\}^{{\mathbb{N}}}$ with the uniform measure and the usual shift (erasing the first bit). We determine the level of randomness needed for a point so that multiple recurrence in the sense of Furstenberg into effectively closed sets $\mathcal{P}$ of positive measure holds for iterations starting at the point. This means that for each $k\in{\mathbb{N}}$ there is an $n$ such that $n,2n,\ldots ,kn$ shifts of the point all end up in $\mathcal{P}$ . We consider multiple recurrence into closed sets that possess various degrees of effectiveness: clopen, $\Pi ^{0}_{1}$ with computable measure, and $\Pi ^{0}_{1}$ . The notions of Kurtz, Schnorr, and Martin-Löf randomness, respectively, turn out to be sufficient. We obtain similar results for multiple recurrence with respect to the $k$ commuting shift operators on $\{0,1\}^{{\mathbb{N}}^{k}}$ .

In [3] a short proof is given that some strings have maximal plain Kolmogorov complexity but not maximal prefix-free complexity. The proof uses Levin's symmetry of information, Levin's formula relating plain and prefix complexity and Gacs' theorem that complexity of complexity given the string can be high. We argue that the proof technique and results mentioned above are useful to simplify existing proofs and to solve open questions. We present a short proof of Solovay's result [21] relating plain and prefix complexity: $K (x) = C (x) + CC (x) + O(CCC (x))$ and $C (x) = K (x) - KK (x) + O(KKK (x))$, (here $CC(x)$ denotes $C(C(x))$, etc.). We show that there exist $\omega$ such that $\liminf C(\omega_1\dots \omega_n) - C(n)$ is infinite and $\liminf K(\omega_1\dots \omega_n) - K(n)$ is finite, i.e. the infinitely often C-trivial reals are not the same as the infinitely often K-trivial reals (i.e. [1,Question 1]). Solovay showed that for infinitely many $x$ we have $|x| - C (x) \le O(1)$ and $|x| + K (|x|) - K (x) \ge \log^{(2)} |x| - O(\log^{(3)} |x|)$, (here $|x|$ denotes the length of $x$ and $\log^{(2)} = \log\log$, etc.). We show that this result holds for prefixes of some 2-random sequences. Finally, we generalize our proof technique and show that no monotone relation exists between expectation and probability bounded randomness deficiency (i.e. [6, Question 1])., Comment: 20 pages, 1 figure

A semi-measure is a generalization of a probability measure obtained by relaxing the additivity requirement to super-additivity. We introduce and study several randomness notions for left-c.e. semi-measures, a natural class of effectively approximable semi-measures induced by Turing functionals. Among the randomness notions we consider, the generalization of weak 2-randomness to left-c.e. semi-measures is the most compelling, as it best reflects Martin-L\"of randomness with respect to a computable measure. Additionally, we analyze a question of Shen, a positive answer to which would also have yielded a reasonable randomness notion for left-c.e. semi-measures. Unfortunately though, we find a negative answer, except for some special cases.

We give solutions to two of the questions in a paper by Brendle, Brooke-Taylor, Ng and Nies. Our examples derive from a 2014 construction by Khan and Miller as well as new direct constructions using martingales. At the same time, we introduce the concept of i.o. subuniformity and relate this concept to recursive measure theory. We prove that there are classes closed downwards under Turing reducibility that have recursive measure zero and that are not i.o. subuniform. This shows that there are examples of classes that cannot be covered with methods other than probabilistic ones. It is easily seen that every set of hyperimmune degree can cover the recursive sets. We prove that there are both examples of hyperimmune-free degree that can and that cannot compute such a cover.

One of the main lines of research in algorithmic randomness is that of lowness notions. Given a randomness notion R, we ask for which sequences A does relativization to A leave R unchanged (i.e., R^A = R)? Such sequences are call low for R. This question extends to a pair of randomness notions R and S, where S is weaker: for which A is S^A still weaker than R? In the last few years, many results have characterized the sequences that are low for randomness by their low computational strength. A few results have also given measure-theoretic characterizations of low sequences. For example, Kjos-Hanssen proved that A is low for Martin-L\"of randomness if and only if every A-c.e. open set of measure less than 1 can be covered by a c.e. open set of measure less than 1. In this paper, we give a series of results showing that a wide variety of lowness notions can be expressed in a similar way, i.e., via the ability to cover open sets of a certain type by open sets of some other type. This provides a unified framework that clarifies the study of lowness for randomness notions, and allows us to give simple proofs of a number of known results. We also use this framework to prove new results, including showing that the classes Low(MLR;SR) and Low(W2R;SR) coincide, answering a question of Nies. Other applications include characterizations of highness notions, a broadly applicable explanation for why low for randomness is the same as low for tests, and a simple proof that Low(W2R;S)=Low(MLR;S), where S is the class of Martin-L\"of, computable, or Schnorr random sequences. The final section gives characterizations of lowness notions using summable functions and convergent measure machines instead of open covers. We finish with a simple proof of a result of Nies, that Low(MLR) = Low(MLR; CR)., Comment: This is a revised version of the APAL paper. In particular, a full proof of Proposition 24 is added

Van Lambalgen's Theorem plays an important role in algorithmic randomness, especially when studying relative randomness. In this paper we extend van Lambalgen's Theorem by considering the join of infinitely many reals which are random relative to each other. In addition, we study computability of the reals in the range of Omega operators. It is known that $\Omega^{\phi'}$ is high. We extend this result to that $\Omega^{\phi^{(n)}}$ is $\textrm{high}_n$ . We also prove that there exists A such that, for each n, the real $\Omega^A_M$ is $\textrm{high}_n$ for some universal Turing machine M by using the extended van Lambalgen's Theorem.

We give two new characterizations of $K$ -triviality. We show that if for all $Y$ such that $\Omega$ is $Y$ -random, $\Omega$ is $(Y\oplusA)$ -random, then $A$ is $K$ -trivial. The other direction was proved by Stephan and Yu, giving us the first titular characterization of $K$ -triviality and answering a question of Yu. We also prove that if $A$ is $K$ -trivial, then for all $Y$ such that $\Omega$ is $Y$ -random, $(Y\oplus A)\equiv_{\textup{LR}}Y$ . This answers a question of Merkle and Yu. The other direction is immediate, so we have the second characterization of $K$ -triviality. ¶ The proof of the first characterization uses a new cupping result. We prove that if $A\nleq_{\textup{LR}}B$ , then for every set $X$ there is a $B$ -random set $Y$ such that $X$ is computable from $Y\oplus A$ .

International audience; Algorithmic randomness theory starts with a notion of an individual random object. To be reasonable, this notion should have some natural properties; in particular, an object should be random with respect to the image distribution F(P) (for some distribution P and some mapping F) if and only if it has a P-random F-preimage. This result (for computable distributions and mappings, and Martin-Löf randomness) was known for a long time (folklore); for layerwise computable mappings it was mentioned in Hoyrup and Rojas (2009, Proposition 5) (even for more general case of computable metric spaces). In this paper we provide a proof and discuss the related quantitative results and applications.

For $r \in [0,1]$, the Bernoulli measure $\mu_r$ on the Cantor space $\{0,1\}^{\mathbb{N}}$ assigns measure $r$ to the set of sequences with $1$ at a fixed position. In [5] it is shown that for $r,s \in [0,1]$, $\mu_s$ is continuously reducible to $\mu_r$ if any only if $r$ and $s$ satisfy certain purely number theoretic conditions (binomial reduciblility). We bring these results into the context of computability theory and Martin-Löf randomness and show that the continuous maps arising in [5] are truth-table functionals (tt-functionals) on $\{0,1\}^{\mathbb{N}}$. This allows us extend the characterization of continuous reductions between Bernoulli measures to include tt-functionals. It then follows from the conservation of randomness under tt-functionals that if $s$ is binomially reducible to $r$, then there is a tt-functional that maps every Martin-Löf random sequence for $\mu_s$ to a Martin-Löf random sequences for $\mu_r$. We are also able to show using results in [2] that the converse of this statement is not true.

We show that there exists a bitsequence that is not computably random for which its odd bits are computably random and its even bits are computably random relative to the odd bits. This implies that the uniform variant of van Lambalgen's theorem fails for computable randomness. (The other direction of van Lambalgen's theorem is known to hold in this case, and known to fail for the non-uniform variant.), 4 pages

We study the possible growth rates of the Kolmogorov complexity of initial segments of sequences that are random with respect to some computable measure on 2 ω , the so-called proper sequences. Our main results are as follows: (1) We show that the initial segment complexity of a proper sequence X is bounded from below by a computable function (that is, X is complex) if and only if X is random with respect to some computable, continuous measure. (2) We prove that a uniform version of the previous result fails to hold: there is a family of complex sequences that are random with respect to a single computable measure such that for every computable, continuous measure μ , some sequence in this family fails to be random with respect to μ . (3) We show that there are proper sequences with extremely slow-growing initial segment complexity, that is, there is a proper sequence the initial segment complexity of which is infinitely often below every computable function, and even a proper sequence the initial segment complexity of which is dominated by all computable functions. (4) We prove various facts about the Turing degrees of such sequences and show that they are useful in the study of certain classes of pathological measures on 2 ω , namely diminutive measures and trivial measures.

A Martin-Löf random sequence is an infinite binary sequence with the property that every initial segment σ has prefix-free Kolmogorov complexity K(σ) at least ∣σ∣ − c, for some constant c ϵ ω. Informally, initial segments of Martin-Löf randoms are highly complex in the sense that they are not compressible by more than a constant number of bits. However, all Martin-Löf randoms necessarily have contiguous substrings of arbitrarily low complexity. If we demand that all substrings of a sequence be uniformly complex, then we arrive at the notion of shift-complex sequences. In this paper, we collect some of the existing results on these sequences and contribute two new ones. Rumyantsev showed that the measure of oracles that compute shift-complex sequences is zero. We strengthen this result by proving that the Martin-Löf random sequences that do not compute shift-complex sequences are exactly the incomplete ones, in other words, the ones that do not compute the halting problem. In order to do so, we make use of the characterization by Franklin and Ng of the class of incomplete Martin-Löf randoms via a notion of randomness called difference randomness. Turning to the power of shift-complex sequences as oracles, we show that there are shift-complex sequences that do not compute Martin-Löf random (or even Kurtz random) sequences.

We consider the following problem for various infinite time machines. If a real is computable relative to large set of oracles such as a set of full measure or just of positive measure, a comeager set, or a nonmeager Borel set, is it already computable?We show that the answer is independent from $ZFC$ for ordinal time machines ($OTM$s) with and without ordinal parameters and give a positive answer for most other machines. For instance, we consider infinite time Turing machines ($ITTM$s), unresetting and resetting infinite time register machines ($wITRM$s, $ITRM$s), and $\alpha$-Turing machines ($\alpha$-$TM$s) for countable admissible ordinals $\alpha$.

Recently, the Dimension Problem for effective Hausdorff dimension was solved by J. Miller in [14], where the author constructs a Turing degree of non-integral Hausdorff dimension. In this article we settle the Dimension Problem for effective packing dimension by constructing a real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one (on the other hand, it is known via [10. 3. 7] that every real of strictly positive effective Hausdorff dimension computes reals whose effective packing dimensions are arbitrarily close to, but not necessarily equal to, one).

We study pairs of reals that are mutually Martin-Löf random with respect to a common, not necessarily computable probability measure. We show that a generalized version of van Lambalgen’s theorem holds for noncomputable probability measures, too. We study, for a given real $A$ , the independence spectrum of $A$ , the set of all $B$ such that there exists a probability measure $\mu$ so that $\mu\{A,B\}=0$ and $(A,B)$ is $(\mu\times\mu)$ -random. We prove that if $A$ is computably enumerable (c.e.), then no $\Delta^{0}_{2}$ -set is in the independence spectrum of $A$ . We obtain applications of this fact to PA degrees. In particular, we show that if $A$ is c.e. and $P$ is of PA degree so that $P\ngeq_{\mathrm {T}}A$ , then $A\oplus P\geq _{\mathrm {T}}\emptyset'$ .

We show that if a set $A$ is computable from every superlow 1-random set, then $A$ is strongly jump-traceable. This theorem shows that the computably enumerable (c.e.) strongly jump-traceable sets are exactly the c.e.\ sets computable from every superlow 1-random set. We also prove the analogous result for superhighness: a c.e.\ set is strongly jump-traceable if and only if it is computable from every superhigh 1-random set. Finally, we show that for each cost function $c$ with the limit condition there is a 1-random $\Delta^0_2$ set $Y$ such that every c.e.\ set $A \le_T Y$ obeys $c$. To do so, we connect cost function strength and the strength of randomness notions. This result gives a full correspondence between obedience of cost functions and being computable from $\Delta^0_2$ 1-random sets., Comment: 41 pages

The study of mass problems and Muchnik degrees was originally motivated by Kolmogorov's non-rigorous 1932 interpretation of intuitionism as a calculus of problems. The purpose of this paper is to summarize recent investigations into the lattice of Muchnik degrees of nonempty effectively closed sets in Euclidean space. Let $\mathcal{E}_\mathrm{w}$ be this lattice. We show that $\mathcal{E}_\mathrm{w}$ provides an elegant and useful framework for the classification of certain foundationally interesting problems which are algorithmically unsolvable. We exhibit some specific degrees in $\mathcal{E}_\mathrm{w}$ which are associated with such problems. In addition, we present some structural results concerning the lattice $\mathcal{E}_\mathrm{w}$. One of these results answers a question which arises naturally from the Kolmogorov interpretation. Finally, we show how $\mathcal{E}_\mathrm{w}$ can be applied in symbolic dynamics, toward the classification of tiling problems and $\boldsymbol{Z}^d$-subshifts of finite type.

The weakly random reals contain not only the Schnorr random reals as a subclass but also the weakly 1-generic reals and therefore the n-generic reals for every n. While the class of Schnorr random reals does not overlap with any of these classes of generic reals, their degrees may. In this paper, we describe the extent to which this is possible for the Turing, weak truth-table, and truth-table degrees and then extend our analysis to the Schnorr random and hyperimmune reals.

We study the Turing degrees which contain a real of effective packing dimension one. Downey and Greenberg showed that a c.e. degree has effective packing dimension one if and only if it is not c.e. traceable. In this paper, we show that this characterization fails in general. We construct a real $A\leq_T\emptyset''$ which is hyperimmune-free and not c.e. traceable such that every real $\alpha\leq_T A$ has effective packing dimension 0. We construct a real $B\leq_T\emptyset'$ which is not c.e. traceable such that every real $\alpha\leq_T B$ has effective packing dimension 0.

The stable Ramsey's theorem for pairs has been the subject of numerous investigations in mathematical logic. We introduce a weaker form of it by restricting from the class of all stable colorings to subclasses of it that are non-null in a certain effective measure-theoretic sense. We show that the sets that can compute infinite homogeneous sets for non-null many computable stable colorings and the sets that can compute infinite homogeneous sets for all computable stable colorings agree below $\emp'$ but not in general. We also answer the analogs of two well known questions about the stable Ramsey's theorem by showing that our weaker principle does not imply $\mathsf{COH}$ or $\mathsf{WKL}_0$ in the context of reverse mathematics., Comment: Accepted for publication in Notre Dame Journal of Formal Logic