\n Contains fulltext :\n 239187.pdf (Publisher’s version ) (Open Access)\n

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 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.

Omega numbers, as considered in algorithmic randomness, are by definition real numbers that are equal to the halting probability of a universal prefix-free Turing machine. Omega numbers are obviously left-r.e., i.e., are effectively approximable from below. Furthermore, among all left-r.e. real numbers in the appropriate range between 0 and 1, the Omega numbers admit well-known characterizations as the ones that are Martin-Löf random, as well as the ones such that any of their effective approximation from below is slower than any other effective approximation from below to any other real, up to a constant factor. In what follows, we obtain a further characterization of Omega numbers in terms of Theta numbers. Tadaki considered for a given prefix-free Turing machine and some natural number a the set of all strings that are compressed by this machine by at least a bits relative to their length, and he introduced Theta numbers as the weight of sets of this form. He showed that in the case of a universal prefix-free Turing machine any Theta number is an Omega number and he asked whether this implication can be reversed. We answer his question in the affirmative and thus obtain a new characterization of Omega numbers. In addition to the one-sided case of the set of all strings compressible by at least a certain number a of bits, we consider sets that comprise all strings that are compressible by at least a but no more than b bits, and we call the weight of such a set a two-sided Theta number. We demonstrate that in the case of a universal prefix-free Turing machine, for given a and all sufficiently large b the corresponding two-sided Theta number is again an Omega number. Conversely, any Omega number can be realized as two-sided Theta number for any pair of natural numbers a and b>a.

In the theory of algorithmic randomness, several notions of random sequence are defined via a game-theoretic approach, and the notions that received the most attention are perhaps Martin-Löf (ML) randomness and computable randomness. The latter notion was introduced by Schnorr and is rather natural: an infinite binary sequence is computably random if no total computable strategy succeeds on it by betting on bits in order. However, computably random sequences can have properties that one may consider to be incompatible with being random, in particular, there are computably random sequences that are highly compressible. The concept of ML randomness is much better behaved in this and other respects, on the other hand its definition in terms of martingales is considerably less natural. Muchnik, elaborating on ideas of Kolmogorov and Loveland, refined Schnorr’s model by also allowing non-monotonic strategies, i.e. strategies that do not bet on bits in order. The subsequent ‘non-monotonic’ notion of randomness, now called Kolmogorov–Loveland randomness, has been shown to be quite close to ML randomness, but whether these two classes coincide remains a fundamental open question. In order to get a better understanding of non-monotonic randomness notions, Miller and Nies introduced some interesting intermediate concepts, where one only allows non-adaptive strategies, i.e. strategies that can still bet non-monotonically, but such that the sequence of betting positions is known in advance (and computable). Recently, these notions were shown by Kastermans and Lempp to differ from ML randomness. We continue the study of the non-monotonic randomness notions introduced by Miller and Nies and obtain results about the Kolmogorov complexities of initial segments that may and may not occur for such sequences, where these results then imply a complete classification of these randomness notions by order of strength.

The six papers in this special issue arose from the conference CiE 2009: Mathematical Theory and Computational Practice, held at the Ruprecht-Karls-Universitat Heidelberg, Germany, in July 2009. CiE 2009 was the fifth meeting in the series of conferences associated with the Association for Computability in Europe.

As part of his groundbreaking work on algorithmic randomness, Solovay demonstrated in the 1970s the remarkable fact that there are computable upper bounds of prefix-free Kolmogorov complexity $K$ that are tight on infinitely many values (up to an additive constant). Such computable upper bounds are called Solovay functions. Recent work of Bienvenu and Downey~[STACS 2009, LIPIcs 3, pp 147-158] indicates that Solovay functions are deeply connected with central concepts of algorithmic randomness such as $Omega$ numbers, K-triviality, and Martin-Loef randomness. In what follows, among other results we answer two open problems posed by Bienvenu and Downey about the definition of $K$-triviality and about the Gacs-Miller-Yu characterization of Martin-Loef randomness. The former defines a sequence A to be K-trivial if K(A|n) <=^+ K(n), the latter asserts that a sequence A is Martin-Loef random iff C(A|n) >=^+ n-K(n). So both involve the noncomputable function K. As our main results we show that in both cases K(n) can be equivalently replaced by any Solovay function, and, what is more, that among all computable functions such a replacement is possible exactly for the Solovay functions. Moreover, similar statements hold for the larger class of all right-c.e. in place of the computable functions. These full characterizations, besides having significant theoretical interest on their own, will be useful as tools when working with K-trivial and Martin-Loef random sequences.

Following a line of research that aims at relating the computation power and the initial segment complexity of a set, the work presented here investigates into the relations between Turing reducibility, defined in terms of computation power, and C-reducibility and H-reducibility, defined in terms of the complexity of initial segments. The global structures of all C-degrees and of all H-degrees are rich and allows to embed the lattice of the powerset of the natural numbers under inclusion. In particular, there are C-degrees, as well as H-degrees, that are different from the least degree and are the meet of two other degrees, whereas on the other hand there are pairs of sets that have a meet neither in the C-degrees nor in the H-degrees; these results answer questions in a survey by Nies and Miller. There are r.e. sets that form a minimal pair for C-reducibility and Sigma20sets that form a minimal pair for H-reducibility, which answers questions by Downey and Hirschfeldt. Furthermore, the following facts on the relation between C-degrees, H-degrees and Turing degrees hold. Every C-degree contains at most one Turing degree and this bound is sharp since there are C-degrees that do contain a Turing degree. For the comprising class of complex sets, neither the C-degree nor the H-degree of such a set can contain a Turing degree, in fact, the Turing degree of any complex set contains infinitely many C-degrees. Similarly the Turing degree of any set that computes the halting problem contains infinitely many H-degrees, while the H-degree of any 2-random set R is never contained in the Turing degree of R. By the latter, H-equivalence of Martin-Lof random sets does not imply their Turing equivalence. The structure of the Cdegrees contained in the Turing degree of a complex sets is rich and allows to embed any countable distributive lattice; a corresponding statement is true for the structure of H-degrees that are contained in the Turing degree of a set that computes the halting problem.

Following Lutz's approach to effective (constructive) dimension, we define a notion of dimension for individual sequences based on Schnorr's concept(s) of randomness. In contrast to computable randomness and Schnorr randomness, the dimension concepts defined via computable martingales and Schnorr tests coincide, that is, the Schnorr Hausdorff dimension of a sequence always equals its computable Hausdorff dimension. Furthermore, we give a machine characterisation of the Schnorr dimension, based on prefix-free machines whose domain has computable measure. Finally, we show that there exist computably enumerable sets that are Schnorr (computably) irregular: while every c.e. set has Schnorr Hausdorff dimension 0, there are c.e. sets of computable packing dimension 1, which is, from Barzdiņš' Theorem, an impossible property for the case of effective (constructive) dimension. In fact, we prove that every hyperimmune Turing degree contains a set of computable packing dimension 1.

Abstract. We present a comparatively simple way to construct Martin-Löf random and rec-random sets with certain additional properties, which works by diagonalizing against appropriate martingales. Reviewing the result of Gács and Kučera, for any given set X we construct a Martin-Löf random set from which X can be decoded effectively. By a variant of the basic construction we obtain a rec-random set that is weak truth-table autoreducible and we observe that there are Martin-Löf random sets that are computably enumerable self-reducible. The two latter results complement the known facts that no rec-random set is truth-table autoreducible and that no Martin-Löf random set is Turing-autoreducible [8, 24].

We observe that known results on the Kolmogorov complexity of prefixes of effectively stochastic sequences extend to corresponding random sequences. First, there are recursively random sequences such that for any nondecreasing and unbounded computable function f and for almost all n, the uniform complexity of the length n prefix of the sequence is bounded by f(n). Second, a similar result with bounds of the form f(n) log n holds for partially-recursive random sequences. Furthermore, we show that there is no Mises-Wald-Church stochastic sequence such that the prefixes of the sequence have Kolmogorov complexity O(log n). This result implies a sharp bound for the complexity of the prefixes of Mises-Wald-Church stochastic and of partially-recursive random sequences. As an immediate corollary to our results, we obtain the known separation of the classes of recursively random and of Mises-Wald-Church stochastic sequences.

Abstract It is shown that the class of Kolmogorov-Loveland stochastic sequences is not closed under selecting subsequences by monotonic computable selection rules. This result gives a strong negative answer to the question whether the Kolmogorov-Loveland stochastic sequences are closed under selecting sequences by Kolmogorov-Loveland selection rules, i.e., by not necessarily monotonic, partial computable selection rules. The following previously known results are obtained as corollaries. The Mises-Wald-Church stochastic sequences are not closed under computable permutations, hence in particular they form a strict superclass of the class of Kolmogorov-Loveland stochastic sequences. The Kolmogorov-Loveland selection rules are not closed under composition.

A binary sequence $A=A(0)A(1)\ldots$ is called infinitely often (i.o.)~Turing-au\-to\-re\-duc\-ible if A~is reducible to itself via an oracle Turing machine that never queries its oracle at the current input, outputs either $A(x)$ or a don't-know symbol on any given input~x, and outputs $A(x)$ for infinitely many~x. If in addition the oracle Turing machine terminates on all inputs and oracles, A~is called i.o.~truth-table-autoreducible. We obtain the somewhat counterintuitive result that every Martin-L\"of random sequence, in fact even every rec-random or p-random sequence, is i.o.~truth-table-autoreducible. Furthermore, we investigate the question of how dense the set of guessed bits can be when i.o.~autoreducing a random sequence. We show that rec-random sequences are never i.o.~truth-table-autoreducible such that the set of guessed bits has positive constant density in the limit and that a similar assertion holds for Martin-L\"of random sequences and i.o.~Turing autoreducibility. On the other hand, we show that for any rational-valued computable function~r that goes nonascendingly to zero, any rec-random sequence is i.o.~truth-table-autoreducible such that on any prefix of length~m at least a fraction of~$r(m)$ of the m~bits in the prefix are guessed. We include a self-contained account of the hat problem, a puzzle that has received some attention outside of theoretical computer science. The hat problem asks for guessing bits of a finite sequence, thus illustrating the notion of i.o.~autoreducibility in a finite setting. The solution to the hat problem is then used as a module in the proofs of the positive results on i.o.~autoreducibility.

We give an abstract account of resource-bounded reducibilities as exemplified by the polynomially time- or logarithmically space-bounded reducibilities of Turing, truth-table, and many-one type. We introduce a small set of axioms that are satisfied for most of the specific resource-bounded reducibilities appearing in the literature. Some of the axioms are of a more algebraic nature, such as the requirement that the reducibility under consideration is a reflexive relation, while others are formulated in terms of recursion theory and, for example, are related to delayed computations of arbitrary recursive sets. The main technical result shown is that for any reducibility that satisfies these axioms, every countable distributive lattice can be embedded into any proper interval of the structure induced on the recursive sets. This extends a corresponding result for polynomially time-bounded reducibilities due to Ambos-Spies [Inform. and Control, 65 (1985), pp. 63--84], as well as a result on embeddings of partial orderings for axiomatically described reducibilities due to Mehlhorn [J. Comput. System Sci., 12 (1976), pp. 147--178].

In this paper we investigate effective versions of Hausdorff dimension which have been recently introduced by Lutz. We focus on dimension in the class E of sets computable in linear exponential time. We determine the dimension of various classes related to fundamental structural properties including different types of autoreducibility and immunity. By a new general invariance theorem for resource-bounded dimension we show that the class of p-m-complete sets for E has dimension 1 in E. Moreover, we show that there are p-m-lower spans in E of dimension /spl Hscr/(/spl beta/) for any rational /spl beta/ between 0 and 1, where /spl Hscr/(/spl beta/) is the binary entropy function. This leads to a new general completeness notion for E that properly extends Lutz's concept of weak completeness. Finally we characterize resource-bounded dimension in terms of martingales with restricted betting ratios and in terms of prediction functions.

We consider separations of reducibilities by random sets. First, we show a result on polynomial time-bounded reducibilities that query their oracle nonadaptively: for every p-random set R, there is a set that is reducible to R with k+1 queries but is not reducible to any other p-random set with at most k queries. This result solves an open problem stated in a recent survey paper by Lutz and Mayordomo [EATCS Bulletin, 68 (1999), pp. 64--80]. Second, we show that the separation result above can be transferred from the setting of polynomial time-bounds to a setting of rec-random sets and recursive reducibilities. This extends the main result of Book, Lutz, and Martin [Inform. and Comput., 120 (1995), pp. 49--54] who, by using different methods, showed a similar separation with respect to Martin-Löf-random sets. Moreover, in both settings we obtain similar separation results for truth-table versus bounded truth-table reducibility.

We characterize FIN-, EX-and BC-learning, as well as the corresponding notions of team learning, in terms of isolated branches on uniformly strongly recursive sequences of trees.Further, the more restrictive models of FIN-learning and strong-monotonic BC-learning can be characterized in terms of isolated branches on a single tree.We discuss learning with additional information where the learner receives an index for a strongly recursive tree such that the function to be learned is isolated on this tree.We show that EX-learning with this type of additional information is strictly more powerful than EX-learning.