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.

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.

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.

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.

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.

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.

For questions, in particular about scientific
aspects of the meeting, please contact the chairs of the programme
committee.

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.

Copyright Notice

The layout of the webpage has been adapted from the style of the CCA conference series and is used by courtesy of Vasco
Brattka.