Search

A major open problem in computational complexity is the existence of a one-way function, namely a function from strings to strings which is computationally easy to compute but hard to invert. Levin (2023) formulated the notion of one-way functions from reals (infinite bit-sequences) to reals in terms of computability, and asked whether partial computable one-way functions exist. We give a strong positive answer using the hardness of the halting problem and exhibiting a total computable one-way function.

Arranging the bits of a random string or real into k columns of a two-dimensional array or higher dimensional structure is typically accompanied with loss in the Kolmogorov complexity of the columns, which depends on k. We quantify and characterize this phenomenon for arrays and trees and its relationship to negligible classes.

We study the compressibility of enumerations, and its role in the relative Kolmogorov complexity of computably enumerable sets, with respect to density. With respect to a strong and a weak form of compression, we examine the gain: the amount of auxiliary information embedded in the compressed enumeration. Strong compression and weak gainless compression is shown for any computably enumerable set, and a positional game is studied toward understanding strong gainless compression.

We study effective randomness-preserving transformations of path-incompressible trees. Some path-incompressible trees with infinitely many paths do not compute perfect path-random trees with computable oracle-use. Sparse perfect path-incompressible trees can be effectively densified, almost surely. We characterize the branching density of path-random trees., Comment: Revised

We show that degrees containing a complete extensions of arithmetic have the random join property: they are the supremum of any random real they compute, with another random real. The same is true for the truth-table and weak truth-table reducibilities.

Muchnik's paradox says that enumerable betting strategies are not always reducible to enumerable strategies whose bets are restricted to either even rounds or odd rounds. In other words, there are outcome sequences x where an effectively enumerable strategy succeeds, but no such parity-restricted effectively enumerable strategy does. We characterize the effective Hausdorff dimension of such $x$, showing that it can be as low as 1/2 but not less. We also show that such reals that are random with respect to parity-restricted effectively enumerable strategies with packing dimension as low as $\log\sqrt3$. Finally we exhibit Muchnik's paradox in the case of computable integer-valued strategies.

We study the problem of whether a betting-strategy can be decomposed into an equivalent set of simpler betting-strategies, such as betting-strategies that bet on a restricted set of stages or bet on a restricted of favorable outcomes. We show that the class of effectively enumerable betting-strategies has irreducible members which cannot be decomposed into an equivalent set of simpler betting-strategies. We answer questions of Kastermans and Hitchcock by constructing a real on which no kastergale (which is a left-c.e. supermartingale whose favorable outcomes are effectively determined) succeeds, but some unrestricted left-c.e. supermartingale succeeds on it. We generalize a result of Muchnick by showing that there is a non-1-random real such that no muchgale (which is a left-c.e. supermartingale who does not bet on certain stages) succeeds on it. Our methodology is then used to obtain further irreducibility results, strongly supporting a conjecture that if a natural class of left-c.e. supermartingales defines 1-randomness, then a single member of that class can do so. In another word, the class of left-c.e. supermartingales cannot be reduced to a simpler, natural subclass of it. For example, we show that there is a non-1-random real such that no kastergale or muchgale succeeds on it.

Leonid Levin (arxiv.org/abs/cs/0503039v14, p.7) published a new (and very nice) proof of G\'acs-Ku\v{c}era's theorem that occupies only a few lines when presented in his style. We try to explain more details and discuss the connection of this proof with image randomness theorems, making explicit some result (see Proposition 4) that is implicit in Levin's exposition. Then we review the previous work about the oracle use when reducing a given sequence to another one, and its connection with algorithmic dimension theory., Comment: published version

A tree is pathwise-random if all of its paths are Martin-Lof random. We show that (a) no weakly 2-random real computes a perfect pathwise-random tree; it follows that the class of perfect pathwise-random trees is null, with respect to any computable measure; (b) there exists a positive-measure pathwise-random tree which does not compute any complete extension of Peano arithmetic; and (c) there exists a perfect pathwise-random tree which does not compute any tree of positive measure and finite randomness deficiency. We then obtain models of second-order arithmetic that separate compactness principles below weak Konigs lemma, answering questions by Chong et al.(2019)., Comment: Revision

In a casino where arbitrarily small bets are admissible, any betting strategy M can be modified into a savings strategy that, not only is successful on each casino sequence where M is (thus accumulating unbounded wealth inside the casino) but also saves an unbounded capital, by permanently and gradually withdrawing it from the game. Teutsch showed that this is no longer the case when a fixed minimum wager is imposed by the casino, thus exemplifying a savings paradox where a player can win unbounded wealth inside the casino, but upon withdrawing a sufficiently large amount out of the game, he is forced into bankruptcy. We study the potential for saving under a shrinking minimum wager rule (granularity) and its dependence on the rate of decrease (inflation) as well as timid versus bold play.

Suppose that the outcomes of a roulette table are not entirely random, in the sense that there exists a successful betting strategy. Is there a successful `separable' strategy, in the sense that it does not use the winnings from betting on red in order to bet on black, and vice-versa? We study this question from an algorithmic point of view and observe that every strategy $M$ can be replaced by a separable strategy which is computable from $M$ and successful on any outcome-sequence where $M$ is successful. We then consider the case of mixtures and show: (a) there exists an effective mixture of separable strategies which succeeds on every casino sequence with effective Hausdorff dimension less than 1/2; (b) there exists a casino sequence of effective Hausdorff dimension 1/2 on which no effective mixture of separable strategies succeeds. Finally we extend (b) to a more general class of strategies.

We introduce the \emph{idemetric} property, which formalises the idea that most nodes in a graph have similar distances between them, and which turns out to be quite standard amongst small-world network models. Modulo reasonable sparsity assumptions, we are then able to show that a strong form of idemetricity is actually equivalent to a very weak expander condition (PUMP). This provides a direct way of providing short proofs that small-world network models such as the Watts-Strogatz model are strongly idemetric (for a wide range of parameters), and also provides further evidence that being idemetric is a common property. We then consider how satisfaction of the idemetric property is relevant to algorithm design. For idemetric graphs we observe, for example, that a single breadth-first search provides a solution to the all-pairs shortest paths problem, so long as one is prepared to accept paths which are of stretch close to 2 with high probability. Since we are able to show that Kleinberg's model is idemetric, these results contrast nicely with the well known negative results of Kleinberg concerning efficient decentralised algorithms for finding short paths: for precisely the same model as Kleinberg's negative results hold, we are able to show that very efficient (and decentralised) algorithms exist if one allows for reasonable preprocessing. For deterministic distributed routing algorithms we are also able to obtain results proving that less routing information is required for idemetric graphs than the worst case in order to achieve stretch less than 3 with high probability: while $\Omega(n^2)$ routing information is required in the worst case for stretch strictly less than 3 on almost all pairs, for idemetric graphs the total routing information required is $O(nlog(n))$.

Algorithmic learning theory traditionally studies the learnability of effective infinite binary sequences (reals), while recent work by [Vitanyi and Chater, 2017] and [Bienvenu et al., 2014] has adapted this framework to the study of learnability of effective probability distributions from random data. We prove that for certain families of probability measures that are parametrized by reals, learnability of a subclass of probability measures is equivalent to learnability of the class of the corresponding real parameters. This equivalence allows to transfer results from classical algorithmic theory to learning theory of probability measures. We present a number of such applications, providing many new results regarding EX and BC learnability of classes of measures, thus drawing parallels between the two learning theories.

We study the problem of identifying a probability distribution for some given randomly sampled data in the limit, in the context of algorithmic learning theory as proposed recently by Vinanyi and Chater. We show that there exists a computable partial learner for the computable probability measures, while by Bienvenu, Monin and Shen it is known that there is no computable learner for the computable probability measures. Our main result is the characterization of the oracles that compute explanatory learners for the computable (continuous) probability measures as the high oracles. This provides an analogue of a well-known result of Adleman and Blum in the context of learning computable probability distributions. We also discuss related learning notions such as behaviorally correct learning and orther variations of explanatory learning, in the context of learning probability distributions from data.

According to Kolmogorov complexity, every finite binary string is compressible to a shortest code -- its information content -- from which it is effectively recoverable. We investigate the extent to which this holds for infinite binary sequences (streams). We devise a new coding method which uniformly codes every stream $X$ into an algorithmically random stream $Y$, in such a way that the first $n$ bits of $X$ are recoverable from the first $I(X\upharpoonright_n)$ bits of $Y$, where $I$ is any partial computable information content measure which is defined on all prefixes of $X$, and where $X\upharpoonright_n$ is the initial segment of $X$ of length $n$. As a consequence, if $g$ is any computable upper bound on the initial segment prefix-free complexity of $X$, then $X$ is computable from an algorithmically random $Y$ with oracle-use at most $g$. Alternatively (making no use of such a computable bound $g$) one can achieve an oracle-use bounded above by $K(X\upharpoonright_n)+\log n$. This provides a strong analogue of Shannon's source coding theorem for algorithmic information theory.

The halting probability of a Turing machine,also known as Chaitin's Omega, is an algorithmically random number with many interesting properties. Since Chaitin's seminal work, many popular expositions have appeared, mainly focusing on the metamathematical or philosophical significance of Omega (or debating against it). At the same time, a rich mathematical theory exploring the properties of Chaitin's Omega has been brewing in various technical papers, which quietly reveals the significance of this number to many aspects of contemporary algorithmic information theory. The purpose of this survey is to expose these developments and tell a story about Omega, which outlines its multifaceted mathematical properties and roles in algorithmic randomness.

Every real is computable from a Martin-Loef random real. This well known result in algorithmic randomness was proved by Kucera and Gacs. In this survey article we discuss various approaches to the problem of coding an arbitrary real into a Martin-Loef random real,and also describe new results concerning optimal methods of coding. We start with a simple presentation of the original methods of Kucera and Gacs and then rigorously demonstrate their limitations in terms of the size of the redundancy in the codes that they produce. Armed with a deeper understanding of these methods, we then proceed to motivate and illustrate aspects of the new coding method that was recently introduced by Barmpalias and Lewis-Pye and which achieves optimal logarithmic redundancy, an exponential improvement over the original redundancy bounds.

Consider a universal Turing machine that produces a partial or total function (or a binary stream), based on the answers to the binary queries that it makes during the computation. We study the probability that the machine will produce a computable function when it is given a random stream of bits as the answers to its queries. Surprisingly, we find that these probabilities are the entire class of real numbers in (0, 1) that can be written as the difference of two halting probabilities relative to the halting problem. In particular, there are universal Turing machines which produce a computable output with probability exactly 1/2. Our results contrast a large array of facts (the most well-known being the randomness of Chaitin's halting probability) which witness maximal initial segment complexity of probabilities associated with universal machines. Our proof uses recent advances in algorithmic randomness.

We show that there is a strong minimal pair in the computably enumerable Turing degrees.

Schnorr showed that a real is Martin-Loef random if and only if all of its initial segments are incompressible with respect to prefix-free complexity. Fortnow and independently Nies, Stephan and Terwijn noticed that this statement remains true if we can merely require that the initial segments of the real corresponding to a computable increasing sequence of lengths are incompressible. The purpose of this note is to establish the following generalization of this fact. We show that a real is X Martin-Loef random if and only if its initial segments corresponding to a pointedly X-computable sequence (r_n) (where r_n is computable from X in a self-delimiting way, so that at most the first r_n bits of X are queried in the computation) of lengths are incompressible. On the other hand we also show that there are reals which are very far from being Martin-Loef random, yet they compute an increasing sequence of lengths at which their initial segments are incompressible.

Kobayashi introduced a uniform notion of compressibility of infinite binary sequences in terms of relative Turing computations with sub-identity use of the oracle. Kobayashi compressibility has remained a relatively obscure notion, with the exception of some work on resource bounded Kolmogorov complexity. The main goal of this note is to show that it is relevant to a number of topics in current research on algorithmic randomness. We prove that Kobayashi compressibility can be used in order to define Martin-Loef randomness, a strong version of finite randomness and Kurtz randomness, strictly in terms of Turing reductions. Moreover these randomness notions naturally correspond to Turing reducibility, weak truth-table reducibility and truth-table reducibility respectively. Finally we discuss Kobayashi's main result from his 1981 technical report regarding the compressibility of computably enumerable sets, and provide additional related original results.

A classic result in algorithmic information theory is that every infinite binary sequence is computable from a Martin-Loef random infinite binary sequence. Proved independently by Kucera and Gacs, this result answered a question by Charles Bennett and has seen numerous applications in the last 30 years. The optimal redundancy in such a coding process has, however, remained unknown. If the computation of the first n bits of a sequence requires n + g(n) bits of the random oracle, then g is the redundancy of the computation. Kucera implicitly achieved redundancy n log n while Gacs used a more elaborate block-coding procedure which achieved redundancy sqrt(n) log n. Different approaches to coding such as the one by Merkle and Mihailovic have not improved this redundancy bound. In this paper we devise a new coding method that achieves optimal logarithmic redundancy. Our redundancy bound is exponentially smaller than the previously best known bound and is known to be the best possible. It follows that redundancy r log n in computation from a random oracle is possible for every stream, if and only if r > 1.

A fruitful way of obtaining meaningful, possibly concrete, algorithmically random numbers is to consider a potential behaviour of a Turing machine and its probability with respect to a measure (or semi-measure) on the input space of binary codes. For example, Chaitin's Omega is a well known Martin-Loef random number that is obtained by considering the halting probability of a universal prefix-free machine. In the last decade, similar examples have been obtained for higher forms of randomness, i.e. randomness relative to strong oracles. In this work we obtain characterizations of the algorithmically random reals in higher randomness classes, as probabilities of certain events that can happen when an oracle universal machine runs probabilistically on a random oracle. Moreover we apply our analysis to different machine models, including oracle Turing machines, prefix-free machines, and models for infinite online computation. We find that in many cases the arithmetical complexity of a property is directly reflected in the strength of the algorithmic randomness of the probability with which it occurs, on any given universal machine. On the other hand, we point to many examples where this does not happen and the probability is a number whose algorithmic randomness is not the maximum possible (with respect to its arithmetical complexity). Finally we find that, unlike the halting probability of a universal machine, the probabilities of more complex properties like totality, cofinality, computability or completeness do not necessarily have the same Turing degree when they are defined with respect to different universal machines.

We show that given any non-computable left-c.e. real $\alpha$ there exists a left-c.e. real $\beta$ such that $\alpha\neq \beta+\gamma$ for all left-c.e. reals and all right-c.e. reals $\gamma$. The proof is non-uniform, the dichotomy being whether the given real $\alpha$ is Martin-Loef random or not. It follows that given any universal machine $U$, there is another universal machine $V$ such that the halting probability of U is not a translation of the halting probability of V by a left-c.e. real. We do not know if there is a uniform proof of this fact.

The halting probabilities of universal prefix-free machines are universal for the class of reals with computably enumerable left cut (also known as left-c.e. reals), and coincide with the Martin-Loef random elements of this class. We study the differences of Martin-Loef random left-c.e. reals and show that for each pair of such reals a, b there exists a unique number r > 0 such that qa - b is a 1-random left-c.e. real for each positive rational q > r and a 1-random right-c.e. real for each positive rational q < r. Based on this result we develop a theory of differences of halting probabilities, which answers a number of questions about Martin-Loef random left-c.e. reals, including one of the few remaining open problems from the list of open questions in algorithmic randomness by Miller and Nies in 2006. The halting probability of a prefix-free machine M restricted to a set X is the probability that the machine halts and outputs an element of X. These numbers Omega_M(X) were studied by a number of authors in the last decade as a way to obtain concrete highly random numbers. When X is the complement of a computably enumerable set, the number Omega_M(X) is the difference of two halting probabilities. Becher, Figueira, Grigorieff, and Miller asked whether Omega_U(X) is Martin-Loef random when U is universal and X is the complement of a computably enumerable set. This problem has resisted numerous attempts in the last decade. We apply our theory of differences of halting probabilities to give a positive answer, and show that Omega_U(X) is a Martin-Loef random left-c.e. real whenever X is nonempty and the complement of a computably enumerable set.

The Ku\v{c}era-G\'acs theorem is a landmark result in algorithmic randomness asserting that every real is computable from a Martin-L\"of random real. If the computation of the first $n$ bits of a sequence requires $n+h(n)$ bits of the random oracle, then $h$ is the redundancy of the computation. Ku\v{c}era implicitly achieved redundancy $n\log n$ while G\'acs used a more elaborate coding procedure which achieves redundancy $\sqrt{n}\log n$. A similar upper bound is implicit in the later proof by Merkle and Mihailovi\'c. In this paper we obtain strict optimal lower bounds on the redundancy in computations from Martin-L\"of random oracles. We show that any nondecreasing computable function $g$ such that $\sum_n 2^{-g(n)}=\infty$ is not a general upper bound on the redundancy in computations from Martin-L\"of random oracles. In fact, there exists a real $X$ such that the redundancy $g$ of any computation of $X$ from a Martin-L\"of random oracle satisfies $\sum_n 2^{-g(n)}<\infty$. Moreover, the class of such reals is comeager and includes a $\Delta^0_2$ real as well as all weakly 2-generic reals. This excludes many slow growing functions such as $\log n$ from bounding the redundancy in computations from random oracles for a large class of reals. On the other hand it was recently shown that if $\sum_n 2^{-g(n)}<\infty$ then $g$ is a general upper bound for the redundancy in computations of any real from some Martin-L\"of random oracle. Our results are obtained as an application of a theory of effective betting strategies with restricted wagers which we develop.

The halting probability of a Turing machine is the probability that the machine will halt if it starts with a random stream written on its one-way input tape. When the machine is universal, this probability is referred to as Chaitin's omega number, and is the most well known example of a real which is random in the sense of Martin-L\"{o}f. Although omega numbers depend on the underlying universal Turing machine, they are robust in the sense that they all have the same Turing degree, namely the degree of the halting problem. In this paper we give precise bounds on the redundancy growth rate that is generally required for the computation of an omega number from another omega number. We show that for each $\epsilon >1$, any pair of omega numbers compute each other with redundancy $\epsilon \log n$. On the other hand, this is not true for $\epsilon=1$. In fact, we show that for each omega number there exists another omega number which is not computable from the first one with redundancy $\log n$. This latter result improves an older result of Frank Stephan.

Chaitin's number Omega is the halting probability of a universal prefix-free machine, and although it depends on the underlying enumeration of prefix-free machines, it is always Turing-complete. It can be observed, in fact, that for every computably enumerable (c.e.) real, there exists a Turing functional via which Omega computes it, and such that the number of bits of omega that are needed for the computation of the first n bits of the given number (i.e. the use on argument n) is bounded above by a computable function h(n) = n+o(n). We characterise the asymptotic upper bounds on the use of Chaitin's omega in oracle computations of halting probabilities (i.e. c.e. reals). We show that the following two conditions are equivalent for any computable function h such that h(n)-n is non-decreasing: (1) h(n)-n is an information content measure, (2) for every c.e. real there exists a Turing functional via which omega computes the real with use bounded by h. We also give a similar characterisation with respect to computations of c.e. sets from Omega, by showing that the following are equivalent for any computable non-decreasing function g: (1) g is an information-content measure, (2) for every c.e. set A, Omega computes A with use bounded by g. Further results and some connections with Solovay functions are given.

The Schelling model of segregation looks to explain the way in which a population of agents or particles of two types may come to organise itself into large homogeneous clusters, and can be seen as a variant of the Ising model in which the system is subjected to rapid cooling. While the model has been very extensively studied, the unperturbed (noiseless) version has largely resisted rigorous analysis, with most results in the literature pertaining to versions of the model in which noise is introduced into the dynamics so as to make it amenable to standard techniques from statistical mechanics or stochastic evolutionary game theory. We rigorously analyse the one-dimensional version of the model in which one of the two types is in the minority, and establish various forms of threshold behaviour. Our results are in sharp contrast with the case when the distribution of the two types is uniform (i.e. each agent has equal chance of being of each type in the initial configuration), which was studied by Brandt, Immorlica, Kamath, and Kleinberg.

Betting strategies are often expressed formally as martingales. A martingale is called integer-valued if each bet must be an integer value. Integer-valued strategies correspond to the fact that in most betting situations, there is a minimum amount that a player can bet. According to a well known paradigm, algorithmic randomness can be founded on the notion of betting strategies. A real X is called integer-valued random if no effective integer-valued martingale succeeds on X. It turns out that this notion of randomness has interesting interactions with genericity and the computably enumerable degrees. We investigate the computational power of the integer-valued random reals in terms of standard notions from computability theory.

Schelling's model of segregation, first described in 1969, has become one of the best known models of self-organising behaviour. While Schelling's explicit concern was to understand the mechanisms underlying racial segregation in large cities from a game theoretic perspective, the model should be seen as one of a family, arising in fields as diverse as statistical mechanics, neural networks and the social sciences, and which are concerned with interacting populations situated on network structures. Despite extensive study, however, the (unperturbed) Schelling model has largely resisted rigorous analysis, prior results in the literature generally pertaining to variants of the model in which noise is introduced into the dynamics of the system, the resulting model then being amenable to standard techniques from statistical mechanics or stochastic evolutionary game theory. A series of recent papers (one by Brandt, Immorlica, Kamath, and Kleinberg, and two by the authors), has seen the first rigorous analysis of the one dimensional version of the unperturbed model. Here we provide the first rigorous analysis of the two and three dimensional unperturbed models, establishing most of the phase diagram, and answering a challenge from a recent paper by Brandt, Immorlica, Kamath, and Kleinberg., Comment: 24 pages and 7 figures

One of the earliest agent-based economical models, Schelling's spacial proximity model illustrated how global segregation can emerge, often unwanted, from the actions of agents of two races acting in accordance with their individual local preferences. Here a 1-dimensional unperturbed variant of the model is studied, which is additionally open in the sense that agents may enter and exit the model. Following the authors' previous work in [1] and that of Brandt, Immorlica, Kamath, and Kleinberg in [2], rigorous results are established, whose statements are asymptotic in both the model and neighbourhood sizes. The current model's openness allows one race or the other to take over almost everywhere in a measure-theoretic sense. Tipping points are identified between the two regions of takeover and the region of staticity, in terms of the parameters of the model. In a significant generalization from previous work, the parameters comprise the initial proportions of the two races, along with independent values of the tolerance for each race.

Schelling's model of segregation looks to explain the way in which particles or agents of two types may come to arrange themselves spatially into configurations consisting of large homogeneous clusters, i.e.\ connected regions consisting of only one type. As one of the earliest agent based models studied by economists and perhaps the most famous model of self-organising behaviour, it also has direct links to areas at the interface between computer science and statistical mechanics, such as the Ising model and the study of contagion and cascading phenomena in networks. While the model has been extensively studied it has largely resisted rigorous analysis, prior results from the literature generally pertaining to variants of the model which are tweaked so as to be amenable to standard techniques from statistical mechanics or stochastic evolutionary game theory. In \cite{BK}, Brandt, Immorlica, Kamath and Kleinberg provided the first rigorous analysis of the unperturbed model, for a specific set of input parameters. Here we provide a rigorous analysis of the model's behaviour much more generally and establish some surprising forms of threshold behaviour, notably the existence of situations where an \emph{increased} level of intolerance for neighbouring agents of opposite type leads almost certainly to \emph{decreased} segregation.

We study the computably enumerable sets in terms of the: (a) Kolmogorov complexity of their initial segments; (b) Kolmogorov complexity of finite programs when they are used as oracles. We present an extended discussion of the existing research on this topic, along with recent developments and open problems. Besides this survey, our main original result is the following characterization of the computably enumerable sets with trivial initial segment prefix-free complexity. A computably enumerable set $A$ is $K$-trivial if and only if the family of sets with complexity bounded by the complexity of $A$ is uniformly computable from the halting problem.

The Turing degree of a real measures the computational difficulty of producing its binary expansion. Since Turing degrees are tailsets, it follows from Kolmogorov's 0-1 law that for any property which may or may not be satisfied by any given Turing degree, the satisfying class will either be of Lebesgue measure 0 or 1, so long as it is measurable. So either the \emph{typical} degree satisfies the property, or else the typical degree satisfies its negation. Further, there is then some level of randomness sufficient to ensure typicality in this regard. A similar analysis can be made in terms of Baire category, where a standard form of genericity now plays the role that randomness plays in the context of measure. We describe and prove a number of results in a programme of research which aims to establish the properties of the typical Turing degree, where typicality is gauged either in terms of Lebesgue measure or Baire category., Comment: 42 pages

We show that there are Turing complete computably enumerable sets of arbitrarily low non-trivial initial segment prefix-free complexity. In particular, given any computably enumerable set $A$ with non-trivial prefix-free initial segment complexity, there exists a Turing complete computably enumerable set $B$ with complexity strictly less than the complexity of $A$. On the other hand it is known that sets with trivial initial segment prefix-free complexity are not Turing complete. Moreover we give a generalization of this result for any finite collection of computably enumerable sets $A_i, i