Complexity of inversion of functions on the reals
We study the complexity of deterministic and probabilistic inversions of partial computable functions on the reals.
Source author record
George Barmpalias
George Barmpalias appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
ResearcherUnclaimed source record
Catalog footprint
What is connected
15works
9topics
4close collaborators
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
15 published item(s)
preprint2022arXiv
Aspects of Muchnik's paradox in restricted betting
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.
0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv
Irreducibility of enumerable betting 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.
0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv
Granularity of wagers in games and the possibility of savings
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.
0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv
Computing halting probabilities from other halting probabilities
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ö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 $ε>1$, any pair of omega numbers compute each other with redundancy $ε\log n$. On the other hand, this is not true for $ε=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.
0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv
On the existence of a strong minimal pair
We show that there is a strong minimal pair in the computably enumerable Turing degrees.
0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv
Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
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.
0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv
Unperturbed Schelling segregation in two or three dimensions
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.
0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv
Digital morphogenesis via Schelling segregation
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.
0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv
Integer Valued Betting strategies and Turing Degrees
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.
0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv
Minority population in the one-dimensional Schelling model of segregation
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.
0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv
Tipping Points in Schelling Segregation
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.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
Kolmogorov complexity and computably enumerable sets
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.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
Universal computably enumerable sets and initial segment prefix-free complexity
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<k$ with non-trivial initial segment prefix-free complexity. An application of this gives a negative answer to a question from \cite[Section 11.12]{rodenisbook} and \cite{MRmerstcdhdtd} which asked for minimal pairs in the structure of the c.e.\ reals ordered by their initial segment prefix-free complexity. Further consequences concern various notions of degrees of randomness. For example, the Solovay degrees and the $K$-degrees of computably enumerable reals and computably enumerable sets are not elementarily equivalent. Also, the degrees of randomness based on plain and prefix-free complexity are not elementarily equivalent; the same holds for their $Δ^0_2$ and $Σ^0_1$ substructures.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
The typical Turing degree
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.
0 citations0 reviewsNo code linkedOpen access