# Fourteenth International Conference on Computability, Complexity and Randomness (CCR 2019)

## Important Dates

 Submission deadline(Extended): 14 May 2019, Notification of authors: 18 May 2019, Final version: XX XX 2019, Conference: 23 - 25 June 2019.

## Topics

• Algorithmic randomness,
• Computability theory,
• Computability in analysis,
• Kolmogorov complexity,
• Computational complexity,
• Reverse mathematics and logic.
The conference will be co-located with The Sixteenth Asian Logic Conference

## Conference Series

The conference, previously known as conference on Logic, Computability and Randomness, will be in the tradition of the previous meetings in

## Abstracts (Click to expand)

Nan Fang. Betting with preference on outcomes.
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 strategy, which always bet on red or always on black? 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 the sum of a strategy always betting on red and a strategy always betting on black, and they are computable from $M$. 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 monotonous strategies.
Elvira Mayordomo. The return trip to classical fractal theory from effective fractal dimension.
J. Lutz and N. Lutz (2017) have recently proven a point-to-set principle for Euclidean and Cantor spaces. This result is a characterization of classical Hausdorff dimension in terms of relativized effective dimension. This implies that geometric measure results regarding Hausdorff dimension can be shown using only effective methods. Several interesting classical results have already been proven using this principle.

In this talk I will present the point-to-set principle in Euclidean space and explain in detail how a Kolmogorov complexity proof (N. Lutz 2017) improves a well known classical result.

Next I will generalize this approach to any separable metric space an show examples of Information theory proofs of fractal dimension results in these spaces.

View in PDF
Steffen Lempp. On the order dimension of locally countable partial orderings.
The order dimension of a partial order $(P,<)$ is the smallest number of linearization of $<$ that intersect to $<$.

We present work on and related to our result that the order dimension of any locally countable partial ordering $(P, <)$ of size $\kappa^+$, for any $\kappa$ of uncountable cofinality, is at most $\kappa$.

In particular, this implies that it is consistent with ZFC that the dimension of the Turing degrees under partial ordering can be strictly less than the continuum. We also characterize the order dimension of the Muchnik degrees and partially that of the Medvedev degrees.

This is joint work with Kojiro Higuchi, Dilip Raghavan, and Frank Stephan.

View in PDF
Gohua Wu. Lachlan Sets and Degrees.
Many work has been done on dre degrees in the last three decades, providing quite a lot of differences between dre Turing adegrees and re Turing degrees. Lachlan observed that every nonzero dre degree bounds a nonzero r.e. degree, and the sets he used were based on the dre enumeration of a given dre set, and these sets are called Lachlan sets. Ishmukhametov initiated to consider the Turing degrees of Lachlan sets, Lachlan degrees, of those dre sets in the same Turing degrees and provided a couple of structural properties of these degrees.

In this talk, we will present some new results along this direction. In particular, we will show the existence of a dre degree such that the Lachlan degrees associated do not have a lower bound, a work joint with Fang, Liu and Yamaleev. The technique developed in the construction is a modification of the gap-cogap method.

Luca San Mauro. Computable reducibility and its variants.
Computability reducibility is the effectivization of Borel reducibility, one of the main focuses of modern descriptive set theory. It has been studied for decades -- being firstly introduced by Ershov in the 1970s -- and was successfully applied to measure the complexity of many equivalence relations arising in mathematics. To give few examples, computable reducibility has been used to compare: the complexity of isomorphism relations of familiar classes of structures; the word problems of finitely generated and finitely presented groups; the provability within different fragments of $PA$.

In this talk, we will survey all these applications and many others. We will also discuss the current knowledge about the degree structure generated by computable reducibility. Finally, we will report on recent progress about reducibilities between equivalence relations that are natural variants of the computable one.

View in PDF
Svetlana Selivanova. Exact real computation and complexity of PDEs.
For solving partial differential equations (PDEs), there exists a rich theory including a vast variety of analytic methods and numerical (often heuristic) algorithms. Yet in many cases it still remains unknown how to

(1) describe the candidate algorithms in a uniform computational framework and work out reliable and efficient algorithms, i.e. computing the solution with a guaranteed prescribed precision or reporting there are not enough resources to do so;

(2) determine what minimal resources (time, storage space,…) a given algorithm would require; and more generally minimal amount of resources needed to solve a differential equation problem, i.e. computational complexity of this problem.

In this talk we give an overview of some recent achievements and open questions in these directions, following the rigorous computable analysis approach.

The talk is partially based on joint works with I. Koswara and M. Ziegler, and with V. Selivanov.

Margarita Marchuk. Index sets of decidably categorical and computably categorical structures.
Let $K$ be a class of structures, closed under isomorphism. A computable characterization for $K$ should separate the computable members of $K$ from other structures, where these are either not in $K$, nor computable. Goncharov and Knight introduced three different approaches to computable characterization for classes of structures. One of these approaches is based on the notion of an index set. Suppose that $K$ is a class of computable structures of a signature $\sigma$. Suppose also that $K$ is closed under isomorphism. The index set of the class $K$ is the set $$I(K) = \left\{ e\in\omega \,\colon \exists \mathfrak{M} \in K \left( \varphi_e = \chi_{D(\mathfrak{M})} \right)\right\},$$ where $\chi_{D(\mathfrak{M})}$ is the characteristic function of the atomic diagram of $\mathfrak{M}$. A computable structure $\mathfrak{M}$ is computably $\mathbf{d}$-categorical if for every computable copy $\mathfrak{N}$ of $\mathfrak{M}$, there exists a $\mathbf{d}$-computable isomorphism. A decidable structure $\mathfrak{M}$ is decidably $\mathbf{d}$-categorical if for every decidable copy $\mathfrak{N}$ of $\mathfrak{M}$, there exists a $\mathbf{d}$-computable isomorphism. We will talk about the complexity of index sets of decidably categorical and computably categorical structures.

View in PDF
Tim McNicholl. Effective metric structure theory.
We will survey recent work on extending the classical computable structure theory program to uncountable metric structures by means of the framework of computable analysis. Specifically, we will summarize results on degrees of categoricity, index sets, and computable presentability for metric spaces and Banach space, especially Lebesgue spaces.

Andrei Alpeev. Entropy and Kolmogorov complexity for amenable-group actions.
I will show how entropy of a shift action of a computable group is related to asymptotic Kolmogorov complexities of its points. In particular, I will show that for ergodic invariant measure on a shift action of a computable amenable group, almost every point have the asymptotic Kolmogorov complexity equal to the Kolmogorov-Sinai entropy of the action.

Wolfgang Merkle. Logical Depth of Infinite Binary Strings: an Overview.
Bennett's notion of logical depth can be applied for investigating the relation between the information content of an infinite binary sequence and its computational power and usefulness. Over the last decade, these investigations received some attention and several new results were obtained. We give an introduction to this research area and review its state of the art.

Bruno Bauwens. Enumerable semimeasure, randomness, and dependence: explaining Leonid Levin's paper.
The goal of the talk is to explain the statement and the proof of the main results in the paper https://arxiv.org/abs/1208.2955. These results concern 2 related questions: (a) how to define mutual information for pairs of infinite bitsequences, and (b) how to define randomness deficiency relative to lower-semicomputable semimeasures. As usual, randomness deficiency is defined by an optimal function inside some class of functions. Levin provides a natural class of functions for this. When applied to a pair of discrete universal measures, it evaluates to algorithmic mutual information. When applied to computable measures, we obtain Martin-Loff randomness deficiency. When applied to a pair of universal semimeasures, we obtain a new notion of mutual information for infinite bitsequences. Levin provides several characterizations. My hope is that with a more accessible presentation, the results are no longer ignored by our community.

Sergey Goncharov, Sergey Ospichev, Dmitry Sviridenko and Denis Ponomaryov. Logical Language of Polynomial Computability.
We study the algorithmic complexity of hereditarily finite list extensions of structures. The generalized computability theory based on $\Sigma$-definability, which has been developed by Yuri Ershov {Ershov1996} and Jon Barwise {Barwise1975}, considers hereditarily finite extensions consisting of hereditarily finite sets. In the papers {bib1,bib4} a theory of hereditarily finite extensions has been developed, which rests on the concept of Semantic Programming. In the paradigm of Semantic Programming, a program is specified by a $\Sigma$-formula in a suitable superstructure of finite lists. This approach raises the natural question of how fast one can compute a program represented by $\Sigma$-formulas. In the recent papers {bib7,bib8} conservative enrichment of language of bounded quantifiers by conditional and recursive terms was constructed. In {bib9} was proved that in case the base model $\mathcal{M}$ is polynomially computable then deciding the truth of a given $\Delta_0$-formula in this enriched language in a hereditarily finite list extension of $\mathcal{M}$ has polynomial complexity.

Following this line of research, we will discuss the concept of logical language, in which the described property is preserved, and $\Delta_0$-terms constructed using $\Delta_0$-formulas would define all polynomially computable functions.

{Ershov1996} Y.L. Ershov,Definability and computability. Consultants Bureau, New York (1996)
{Barwise1975} J. Barwise, Admissible sets and structures. Springer, Berlin (1975)
{bib1} S.S. Goncharov and D.I. Sviridenko, $\Sigma$-programming, Transl. II. Ser., Amer. Math. Soc., no. 142, 101--121 (1989).
{bib4} Y.L. Ershov, S.S. Goncharov and D.I. Sviridenko, Semantic Programming, Information processing 86: Proc. IFIP 10th World Comput. Congress, vol. 10, Elsevier Sci., Dublin, 1093--1100 (1986).
{bib7} S.S. Goncharov, Conditional Terms in Semantic Programming, Siberian Mathematical Journal, vol. 58, no. 5, 794--800 (2017).
{bib8} S.S. Goncharov and D.I. Sviridenko, Recursive Terms in Semantic Programming, Siberian Mathematical Journal, vol. 59, no. 6, 1279--1290 (2018).
{bib9} S. Ospichev and D. Ponomarev, On the complexity of formulas in semantic programming, Sib. Electr. Math. Reports, vol. 15, 987--995 (2018)
Rod Downey. A Hierarchy of Degrees.
Noam Greenberg and I have extensively developed a hierarchy of degrees which classify the combinatorics of many constructions.
I will discuss this by looking at an example of presentations of halting probabilities.

Joint work with Noam Greenberg.

Alexander Shen. Kolmogorov complexity and logic.
There are intrinsic connection between Kolmogorov complexity, computability theory and logic. The best known and most important example is Chaitin's proof of Gödel incompleteness theorem (another inpressive result is the Kritchman--Raz proof of the Second incompleteness theorem). We will discuss several other examples:

1. Chaitin statements (of the form $C(x)>n$ for some string $x$ and some integer $n$) are $\Pi_1$ (universal) statements. Question: is it true that every universal statement is (provably) equivalent to some Chaitin statement? No, and the answer is already obtained by the computability theory: the upper graph of the Kolmogorov complexity function is not m-complete.

2. Kolmogorov complexity function is not computable. Moreover, it cannot be approximated up to a constant factor. Moreover, for every constant $c$ the set of incompressible bit strings cannot be separated from strings $x$ such that $C(x)<|x|/c$. Moreover, this separation problem (as a Medvedev mass problem) is above the halting problem. The proof-theoretic counterpart of this result: Fix some constant $c$. If we add for every string $x$ the axiom $C(x)>m/c$ where $m$ is the complexity of $x$, then in the resulting theory all true universal statements are provable. However, if we add only one axiom $C(x)>m'$ where $m'$ is significantly smaller than the true complexity of $x$, we get a quasi conservative'' extension: no new simple theorems are provable.

Based on the old paper 10.1016/j.apal.2014.04.009 and recent work with Ruslan Ishkuvatov and Daniil Musatov.

## Location

The conference will be hosted by the Departament of Mathematics, at Nazarbayev University, Astana, Kazakhstan.

## Submissions

Authors are invited to submit an abstract in PDF format of typically about 1 or 2 pages via the following web page:

https://easychair.org/conferences/?conf=ccr20190

No full papers will be required for this conference. After the deadline for submissions has expired, submissions may still be accepted for reviewing at the discretion of the PC chairs.

## Registration

If you are planning to attend the conference, please fill out the following registration form as soon as possible.

Conference Registration

## Proceedings

No proceedings will be published before the conference. A booklet with abstracts will be made available at the conference.

## Programme Committee

• Rod Downey (Victoria University of Wellington, New Zealand), Chair
• Yang Yue (National University of Singapore, Singapore), co-Chair
• Bruno Bauwens (National Research University Higher School of Economics, Russia)
• Daniel Turetsky (University of Notre Dame, USA)
• Serikzhan Badaev (Al-Farabi Kazakh National University, Kazakhstan)
• Ng Keng Meng (Selwyn) (Nanyang Technological University, Singapore)
• George Barmpalias (Chinese Academy of Sciences, China)
• Johanna N.Y. Franklin (Hofstra University, USA)
• Barbara F. Csima (University of Waterloo, Canada)
• Denis Hirschfeldt (University of Chicago,USA)

## Contacts

Inquiries about organizational matters such as registration or accommodation are best addressed to the local organizing committee.

## CCR Steering Committee

Verónica Becher (Buenos Aires, Argentina), Laurent Bienvenu (Montpellier, France), Rod Downey, chair (Wellington, New Zealand), Denis Hirschfeldt (Chicago, United States), Elvira Mayordomo (Zaragoza, Spain), Wolfgang Merkle (Heidelberg, Germany), Nikolai K. Vereshchagin (Moscow, Russia), Liang Yu (Nanjing, China).

## Funding

Funding opportunities for student members of the Association for Symbolic Logic (ASL) are available. Applications should be directed to the Association for Symbolic Logic three months prior to the meeting, following these instructions.