Algorithmic Randomness - IMS

Algorithmic Randomness
(2 - 30 Jun 2014)

~ Abstracts ~

Normality, computability and diophantine approximation
Verónica Becher, Universidad de Buenos Aires, Argentina

We will discuss two theorems. First, a real number $a$ is the irrationality exponent of a computable number if and only if $a$ is right recursively enumerable relative to $0'$. Second, for every real number $a$ there is a real number $x$ such that $x$ is computable from $a$, has irrationality exponent equal to $a$ and is absolutely normal. More generally, the set of bases to which $x$ is normal or to which $x$ is simply normal can be made to order.

This is joint work with Theodore Slaman and Yann Bugeaud.

Finite state incompressible infinite sequences
Cristian Sorin Calude, The University of Auckland, New Zealand

We define and study finite state complexity of finite strings and infinite sequences and study connections of these complexity notions to randomness and normality. We show that the finite state complexity does not only depend on the codes for finite transducers, but also on how the codes are mapped to transducers. As a consequence we relate the finite state complexity to the plain (Kolmogorov) complexity, to the process complexity and to prefix-free complexity. Working with prefix-free sets of codes we characterise Martin-Löf random sequences in terms of finite state complexity: the weak power of finite transducers is compensated by the high complexity of enumeration of finite transducers. We also prove that every finite state incompressible sequence is normal, but the converse implication is not true. These results also show that our definition of finite state incompressibility is stronger than all other known forms of finite automata based incompressibility, in particular the notion related to finite automaton based betting systems introduced by Schnorr and Stimm. The paper concludes with a discussion of open questions.

Mathias forcing
Peter Cholak, University of Notre Dame, USA

In Mathias forcing, we force with conditions (D, E), where D is a finite set and E is an infinite set whose minimum element is greater than the maximum element of D. A condition (D*, E*) extends (D,E) if D subset D* subset D union E, and E* subset E. Here we will study the generic reals for Mathias forcing when we restrict E to be within a fixed ideal I of Turing degrees. For example, we will show if every 3-I-Mathias generic computes a set A then a modulus for A must be in I. We also provide a partial answer to the question of when an m-J-Mathias generic computes an n-I-Mathias generic for different ideals I and J. Some examples will be provided.
This work is joint with Damir Dzhafarov and Mariya Soskova.

Sets have simple members
Samuel Epstein, Boston University, USA

The combined Universal Probability m(D) of strings x in sets D is close to max m(x) over x in D: their ~logs differ by at most D's information j=I(D:H) about the halting sequence H. Thus if all x have complexity K(x) >k, D carries >i bits of information on each its x where i+j ~ k. Note that there are no ways to generate D with significant I(D:H). This is joint work with Leonid A. Levin.

The complexity of n¹₁ randomness
Noam Greenberg, Victoria University of Wellington, New Zealand

I will discuss some recent advances in the theory of higher randomness (randomness at the level of Π¹₁ sets). This theory was developed in the last decade by Hjorth and Nies and by Chong and Yu. I will discuss the separation between higher notions of randomness and the calculation of the Borel rank of the set of Π¹₁random reals. This is joint work with Bienvenu and Monin.

Weak lowness notions and weak reducibilities
Ian Herbert, National University of Singapore

Prefix-free Kolmogorov complexity gives us some 'standard' lowness notions for reals: A is K-trivial if its initial segments have the lowest possible complexity and A is low for K if using A as an oracle does not decrease the complexity of strings by more than a constant factor. We discuss various ways of weakening these notions and the relations among these weakenings and between them and standard notions. We also discuss how these notions behave under reducibilities that are based on Kolmogorov complexity and are weaker than Turing reducibility.

Algorithmically random algebraic structures
Bakhadyr Khoussainov, The University of Auckland, New Zealand

In this talk we introduce the concept of algorithmically random algebraic structure. In particular, we construct algorithmically random structures in the classes of graphs, trees, universal algebras, and monoids. We prove that there exist computably enumerable algorithmically random trees. We also build algorithmically random universal algebras and graphs computable in the halting set.

Integer-valued randomness and degrees
Michael McInerney, Victoria University of Wellington, New Zealand

Analysing betting strategies where only integer values are allowed, perhaps for a given set F, gives an interesting variant on algorithmic randomness where category and measure intersect. We build on earlier work of Bienvenu, Stephan, and Teutsch, and study reals random in this sense, and their intricate relationship with the c.e. degrees. This is joint work with George Barmpalias and Rod Downey.

[1] Laurent Bienvenu, Frank Stephan, and Jason Teutsch, How powerful are integer-valued martingales?, Theory of Computing Systems, vol. 51 (2010), no. 3, pp. 330-351.

An analogy between cardinal characteristics and highness properties of oracles
Andre Nies, The University of Auckland, New Zealand

Highness properties indicate strength of a Turing oracle A. We find analogs of cardinal characteristics of the continuum among highness properties. For instance, the unbounding number (how many functions on the natural numbers does one need so that no single function dominates them all?) corresponds to the usual highness: the oracle A computes a function that dominates all computable functions. This analogy was first studied by N. Rupprecht [3].

In joint work with J. Brendle, A. Brooke-Taylor, and K.M. Ng [2], we study the analog in computability of the full Cichon diagram of cardinal characteristics in set theory (see [1]). To do so, we develop a systematic transfer between the two areas. Since many cardinal characteristics are based on null sets or meager sets, we (re-)obtain interesting highness properties related to algorithmic randomness or to genericity. For instance, the cofinality of the null sets (how many null sets are needed to cover all null sets?) corresponds to not being low for Schnorr tests. Sometimes new properties emerge: the analog of non(N) (the least size of a non-null set) is computing a Schnorr test that contains all computable reals.

Combining results of Rupprecht and the above-mentioned authors, five cardinals in the Cichon diagram correspond to either being high, or being of hyperimmune degree in the computable setting. Recent research of Kihara (following discussions with Nies) suggests that there may be no collapsing if one takes hyperarithmetic reductions and properties from higher randomness.

References:

[1] Tomek Bartoszynski and Haim Judah. Set Theory. On the structure of the real line. A K Peters, Wellesley, MA, 1995. 546 pages.

[2] Joerg Brendle, Andrew Brooke-Taylor, Keng Meng Ng and Andre Nies. An analogy between cardinal characteristics and highness properties of oracles. Submitted to Proceedings of the Asian Logic Colloquium 2013. Available at arxiv.org/abs/1404.2839

[3] Nicholas Rupprecht. Relativized Schnorr tests with universal behavior. Arch. Math. Logic, 49(5):555-570, 2010.

Infinite time computations and randomness
Philipp Schlicht, University of Bonn, Germany

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? For Turing machines, the answer is yes by a classical theorem of Sacks. We show that the answer is independent from ZFC for ordinal time machines with and without ordinal parameters and give a positive answer for most other machine types, for instance infinite time machines with bounded halting time and infinite register machines. We also consider randomness for infinite time machines. This is joint work with Merlin Carl.

Layerwise computable mappings and computable Lovasz local lemma
Alexander Shen, LIRMM CNRS, France

A notion of a layerwise computable mapping was introduced by Hoyrup and Rohas in the context of the algorithmic information theory: a mapping of ML-random sequences into infinite binary sequences that is computable by a Turing machine that gets (in addition to a random sequence) an upper bound for its randomness deficiency. It turned out that this notion has a natural reformulation in terms of computable points in the space of measurable sets, and in terms of machines that may rewrite the output bits (though with small probability). The last interpretation is useful for the proof (invented by Andrey Rumyantsev) of a computable version of the Lovasz local lemma.

Reformulating quantum mechanics by algorithmic randomness
Kohtaro Tadaki, Chuo University, Japan

The notion of probability plays a crucial role in quantum mechanics. It appears in quantum mechanics as the so-called Born rule, i.e., the probability interpretation of the wave function. In modern mathematics which describes quantum mechanics, however, probability theory means nothing other than measure theory, and therefore any operational characterization of the notion of probability is still missing in quantum mechanics. In this sense, the current form of quantum mechanics is considered to be imperfect as a physical theory which must stand on operational means.

In this talk, we present an alternative rule to the Born rule based on the toolkit of algorithmic randomness without reference to the notion of probability for the purpose of making quantum mechanics perfect. We use the notion of Martin-Loef randomness with respect to Bernoulli measure to state this new rule for specifying the property of the results of quantum measurements in an operational way. We then consider the validity of the new rule, in particular, based on the many-worlds interpretation of quantum mechanics.

The many-worlds interpretation of quantum mechanics is more than just an interpretation of quantum mechanics. It aims to recover the predictions of quantum mechanics without assuming the Born rule. For that purpose, the many-worlds interpretation of quantum mechanics usually assumes that our world is 'typical' or 'random' among many coexisting worlds. This assumption by physicists is not necessarily mathematically rigorous. In this talk we point out that the alternative rule is a mathematically rigorous form of the assumption.

On approximate decidability of minimal programs
Jason Teutsch, The University of Chicago, USA

An index $e$ for a partial-computable function is called minimal if every lesser index computes a different function from $e$. Since the 1960's it has been known that, in any reasonable programming language, no effective procedure determines whether or not a given index is minimal. We investigate whether the task of determining minimal indices can be solved in an approximate sense. Our first question, regarding the set of minimal indices, is whether there exists an algorithm which can correctly label 1 out of $k$ indices as either minimal or non-minimal. Our second question, regarding the function which computes minimal indices, is whether one can compute a short list of candidate indices which includes a minimal index for a given program. We give some negative results and leave the possibility of positive results as open questions.

On algorithmic strong sufficient statistics
Nikolay Vereshchagin, Moscow State University, Russia

Sufficient statistics for a given data can be considered as a squeezing noise from the data. We introduce the notion of a strong sufficient statistic and show that strong sufficient statistics have better properties than just sufficient statistics. We prove that there are "strange" data strings, whose minimal strong sufficient statistic have much larger complexity than the minimal sufficient statistic.

Degrees of members of thin classes
Guohua Wu, Nanyang Technological University

In this talk, I will present recent progress on the research of degrees of members of thin Pi01 classes. Especially, we will extend a result of Cenzer, Downey, Jockusch and Shore about the existence of computably enumerable degrees containing no members of thin Pi01 classes. We will consider (weak) density of such degrees in the structure of c.e. degrees.

Some applications of higher Demuth's theorem
Liang Yu, Nanjing University, China

We apply higher Demuth's theorem to both higher and classical recursion theory. In particular, we apply it to investigate measure theoretical aspects of hyper and Turing degrees. We give a proof of Kripke's unpublished result on higher recursion theory. And answer some questions concerning antichains of Turing degrees.

This is a joint work with CT Chong.

Applications of algorithmic complexity to network science and synthetic biology
Hector Zenil, Karolinska Institutet, Sweden

Network theory is today a central topic in computational systems biology as a framework to understand and reconstruct relations among biological elements. For example, constructing networks from a gene expression dataset provides a set of possible hypotheses explaining connections among genes, vital knowledge to advancing our understanding of living organisms as systems. I will briefly survey aspects at the intersection of information theory and network biology. I will show that numerical approximations of Kolmogorov complexity (K) applied to graph adjacency matrices capture some group-theoretic and topological properties of graphs and empirical networks such as size of group of automorphisms. We show that approximations of K characterise synthetic and natural networks by their generating mechanisms, assigning lower algorithmic randomness to complex network models (Watts-Strogatz and Barabasi-Albert networks) and high Kolmogorov complexity to (random) Erdos-Renyi graphs. We derive these results via two different Kolmogorov complexity approximation methods applied to the adjacency matrices of the graphs and networks, one of which is a novel method based upon algorithmic probability thus connecting several concepts in complexity science, from complex networks to algorithmic randomness to synthetic biology.

Best viewed with IE 7 and above