Search

We apply Context-free Grammars (CFG) to measure the structural information content of a symbolic music string. CFGs are appropriate to this domain because they highlight hierarchical patterns, and their dictionary of rules can be used for compression. We adapt this approach to estimate the conditional Kolmogorov complexity of a string with a concise CFG of another string. Thus, a related string may be compressed with the production rules for the first string. We then define an information distance between two symbolic music strings, and show that this measure can separate genres, composers and musical styles. Next, we adapt our approach to a model-selection problem, expressing the model as a CFG with restricted size, generated from a set of representative strings. We show that a well-generated CFG for a composer identifies characteristic patterns that can significantly compress other pieces from the same composer, while not being useful on pieces from different composers. We identify further opportunities of this approach, including using CFGs for generating new music in the style of a composer. [ABSTRACT FROM AUTHOR]

Recently, a connection has been established between two branches of computability theory, namely between algorithmic randomness and algorithmic learning theory. Learning-theoretical characterizations of several notions of randomness were discovered. We study such characterizations based on the asymptotic density of positive answers. In particular, this note provides a new learning-theoretic definition of weak 2-randomness, solving the problem posed by (Zaffora Blando, Rev. Symb. Log. 2019). The note also highlights the close connection between these characterizations and the problem of convergence on random sequences. [ABSTRACT FROM AUTHOR]

Numerous learning tasks can be described as the process of extrapolating patterns from observed data. One of the driving intuitions behind the theory of algorithmic randomness is that randomness amounts to the absence of any effectively detectable patterns: it is thus natural to regard randomness as antithetical to inductive learning. Osherson and Weinstein [11] draw upon the identification of randomness with unlearnability to introduce a learning-theoretic framework (in the spirit of formal learning theory) for modelling algorithmic randomness. They define two success criteria—specifying under what conditions a pattern may be said to have been detected by a computable learning function—and prove that the collections of data sequences on which these criteria cannot be satisfied correspond to the set of weak 1-randoms and the set of weak 2-randoms, respectively. This learning-theoretic approach affords an intuitive perspective on algorithmic randomness, and it invites the question of whether restricting attention to learning-theoretic success criteria comes at an expressivity cost. In other words, is the framework expressive enough to capture most core algorithmic randomness notions and, in particular, Martin-Löf randomness—arguably, the most prominent algorithmic randomness notion in the literature? In this article, we answer the latter question in the affirmative by providing a learning-theoretic characterisation of Martin-Löf randomness. We then show that Schnorr randomness, another central algorithmic randomness notion, also admits a learning-theoretic characterisation in this setting. [ABSTRACT FROM AUTHOR]

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 FROM AUTHOR]

We investigate the strength of a randomness notion ${\cal R}$ as a set-existence principle in second-order arithmetic: for each Z there is an X that is ${\cal R}$ -random relative to Z. We show that the equivalence between 2-randomness and being infinitely often C -incompressible is provable in $RC{A_0}$. We verify that $RC{A_0}$ proves the basic implications among randomness notions: 2-random $\Rightarrow$ weakly 2-random $\Rightarrow$ Martin-Löf random $\Rightarrow$ computably random $\Rightarrow$ Schnorr random. Also, over $RC{A_0}$ the existence of computable randoms is equivalent to the existence of Schnorr randoms. We show that the existence of balanced randoms is equivalent to the existence of Martin-Löf randoms, and we describe a sense in which this result is nearly optimal. [ABSTRACT FROM AUTHOR]

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 FROM AUTHOR]

The article discusses avoiding effective packing dimension 1 below arraynoncomputable computably enumerable (c.e.) degrees. It discusses research work showing that there is a Turing degree with nonzero effective packing dimension, but which does not contain any set of effective packing dimension 1. It shows the existence of such a degree below every c.e. array noncomputable degree, and hence that they occur below precisely those of the c.e. degrees which are array noncomputable.

In this paper, we prove that if a c.e. Turing degree d is non-low, then there are two left-c.e. reals β , β in d, such that, if β is wtt-reducible to a left-c.e. real α, then β is not computable Lipschitz (cl-) reducible to α. As a corollary, d contains a left-c.e. real which is not cl-reducible to any complex (wtt-complete) left-c.e. real. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Miller (J Symb Log 69(3):907-913, , ) and independently Nies et al. (J Symb Log 70(2):515-535, ) gave a complexity characterization of 2-random sequences in terms of plain Kolmogorov complexity $${C(\cdot)}$$ : they are sequences that have infinitely many initial segments with O(1)-maximal plain complexity (among the strings of the same length). Later Miller (Notre Dame J Form Log 50(4):381-391, ) showed that prefix complexity $${K(\cdot)}$$ can also be used in a similar way: a sequence is 2-random if and only if it has infinitely many initial segments with O(1)-maximal prefix complexity (which is n + K( n) for strings of length n). The known proofs of these results are quite involved; in this paper we provide elementary proofs. Miller (J Symb Log 69(3):907-913, , ) also gave a quantitative version of the first result: the $${\mathbf{0}'}$$ -randomness deficiency of a sequence $${\omega}$$ equals lim inf $${_n [n - C(\omega_1\dots\omega_n)] + O(1)}$$ . Our simplified proof can also be used to prove this. We show (and this seems to be a new result) that a similar quantitative result is also true for prefix complexity: $${\mathbf{0}'}$$ -randomness deficiency equals lim inf $${_n [n + KP(n) - K(\omega_1\dots\omega_n)]+ O(1)}$$ . [ABSTRACT FROM AUTHOR]

Consider a randomness notion $${\mathcal{C}}$$ . A uniform test in the sense of $${\mathcal{C}}$$ is a total computable procedure that each oracle X produces a test relative to X in the sense of $${\mathcal{C}}$$ . We say that a binary sequence Y is $${\mathcal{C}}$$ -random uniformly relative to X if Y passes all uniform $${\mathcal{C}}$$ tests relative to X. Suppose now we have a pair of randomness notions $${\mathcal{C}}$$ and $${\mathcal{D}}$$ where $${\mathcal{C} \subseteq \mathcal{D}}$$ , for instance Martin-Löf randomness and Schnorr randomness. Several authors have characterized classes of the form Low( $${\mathcal{C}, \mathcal{D}}$$ ) which consist of the oracles X that are so feeble that $${\mathcal{C} \subseteq \mathcal{D}^X}$$ . Our goal is to do the same when the randomness notion $${\mathcal{D}}$$ is relativized uniformly: denote by Low $${\star(\mathcal{C},\mathcal{D})}$$ the class of oracles X such that every $${\mathcal{C}}$$ -random is uniformly $${\mathcal{D}}$$ -random relative to X. (1) We show that $${X\in Low ^\star}$$ (MLR, SR) if and only if X is c.e. tt-traceable if and only if X is anticomplex if and only if X is Martin-Löf packing measure zero with respect to all computable dimension functions. (2) We also show that $${X\in Low^\star}$$ (SR, WR) if and only if X is computably i.o. tt-traceable if and only if X is not totally complex if and only if X is Schnorr Hausdorff measure zero with respect to all computable dimension functions. [ABSTRACT FROM AUTHOR]