SCHEDULE FOR DAGSTUHL SEMINAR IN COMPUTABILITY 2017: (abstracts can be found at the end) MONDAY: 07:30-08:45 BREAKFAST 09:00-09:15 Housekeeping/Information for Participants 09:15-10:00 Julia Knight: The Scott Isomorphism Theorem 10:00-10:30 COFFEE BREAK 12:15-13:00 LUNCH 13:00-13:20 Sasha Mel'nikov: From equivalence structures to topological groups 13:30-13:50 Alberto Marcone: A peek at the higher levels of the Weihrauch hierarchy 15:30-16:00 COFFEE AND CAKE 16:00-16:20 Sergey Goncharov: Computable numberings 16:30-16:50 Takayuki Kihara: Topological aspects of enumeration degrees 18:00-19:00 DINNER TUESDAY: 07:30-08:45 BREAKFAST 09:00-09:45 Laurent Bienvenu: Deep Pi^0_1 classes 10:00-10:30 COFFEE BREAK 12:15-13:00 LUNCH 14:30-14:50 Linda Brown Westrick: Turing-, tt-, and m-reductions for functions in the Baire hierarchy (joint with Adam Day and Rod Downey) 15:00-15:20 George Barmpalias: Machines running on random tapes and the probabilities of events 15:30-16:00 COFFEE AND CAKE 16:00-16:20 Mariya Soskova: Seven characterizations of the cototal enumeration degrees 16:30-16:50 Selwyn Ng: Weak truth table degrees of categoricity 18:00-19:00 DINNER 19:30-20:30 Open problem session WEDNESDAY: 07:30-08:45 BREAKFAST 09:00-09:45 Noam Greenberg: Finding bases of uncountable free abelian groups 10:00-10:30 COFFEE BREAK 11:00-11:20 Sasha Shen': Stopping time complexity and monotone-conditional complexities revisited 11:30-11:50 Rupert Hölzl: Monte Carlo Computability 12:15-13:00 LUNCH FREE AFTERNOON 15:30-16:00: COFFEE BREAK THURSDAY: 07:30-08:45 BREAKFAST 09:00-09:45 Ted Slaman: Three theorems between computability and diophantine approximation 10:00-10:30 COFFEE BREAK 12:15-13:00 LUNCH 14:00-14:20 André Nies: Characterising the oracles that know half of each computable set 14:30-14:50 Antonio Montalbán: A new result towards Fraïssé´s conjecture conjecture 15:00-15:20 Henry Towsner: Constructing chains and antichains in partial orders 15:30-16:00 COFFEE AND CAKE 16:00-16:20 Joe Miller: Generic Muchnik reducibility 16:30-16:50 Ulrich Kohlenbach: Computability, proof mining and metric regularity 17:00-17:20: Nikolay Vereshchagin: Are there non-stochastic objects? 17:30-17:50: Iskander Kalimullin: Strong and nonstrong degrees of categoricity 18:00-19:00 DINNER FRIDAY: 07:30-08:45 BREAKFAST 09:00-09:45 Arno Pauly: Weihrauch degrees and recursion theory 10:00-10:30 COFFEE BREAK 11:00-11:20 Bas Terwijn: Genericity, randomness, and differentiable functions 11:30-11:50 Kenshi Miyabe: Randomness notions in Muchnik and Medvedev degrees 12:15-13:00 LUNCH ABSTRACTS: Barmpalias: Machines running on random tapes and the probabilities of events Probabilistic Turing machines have been studied since the 1940s, when it was shown that the probability of a machine with a random (as in probability theory) oracle computing any fixed non-computable real is 0. Chaitin's halting probability is the probability that a universal Turing machine halts on a random oracle (with empty numerical input) and was characterized in terms of algorithmic randomness and computable approximations. In general, one can ask the same question with respect to any property that a computation of a universal Turing machine may have when it reads a random oracle: 1. will it compute a total function? 2. will it enumerate a co-finite set (say, as the domain of a partial function that it computes))? 3. will it enumerate a set which computes the halting problem? 4. will it compute an incomputable function? 5. will it halt with an output inside a certain set A? Can we give characterizations of these probabilities in terms of algorithmic randomness and effectiveness properties? We show that this is possible, but we do not always get the expected answer. Moreover we answer one of the last remaining questions from the BSL 2006 list of open questions in randomness (by Miller and Nies), by showing that the probability that the universal machine halts and outputs a number in a non-empty Pi01 set is always left-c.e. and ML-random. Intuitively, this says that if we code arithmetical sentences into numbers, the probability that the universal machine outputs an undecidable sentence (in PA) can be effectively approximated from below! My talk is mainly based on the following recent work: The probability of a computable output from a random oracle (George Barmpalias, Douglas Cenzer and Christopher P. Porter, https://arxiv.org/abs/1612.08537) Differences of halting probabilities (George Barmpalias and Andy Lewis-Pye, https://arxiv.org/abs/1604.00216) Random numbers as probabilities of machine behaviour (George Barmpalias, Douglas Cenzer and Christopher P. Porter, https://arxiv.org/abs/1605.05838) Bienvenu: Deep Pi^0_1 classes We will present the concept of deep Pi^0_1 classes, which can be thought of as those classes whose paths are uniformly `hard to generate probabilistically’ and discuss the many interesting properties those classes enjoy. In particular we will see that they behave quite similarly the class of PA degrees in their interactions with algorithmic randomness. This is joint work with Chris Porter, see https://arxiv.org/abs/1403.0450 for the paper on which this talk is based. Greenberg: Finding bases of uncountable free abelian groups A basis of a countable free abelian group can be constructed by recursion. In the uncountable case this fails, because (unlike in vector spaces) we can get stuck at limit stages. Admissible computability can be used to make this precise, by examining (a) how complicated can a basis be relative to a free group; and (b) how hard it is to recognise free groups. The results depend on the cardinality; for example, weakly compact cardinals behave differently. Hölzl: Monte Carlo Computability We introduce Monte Carlo computability as a probabilistic concept of computability on infinite objects and prove that Monte Carlo computable functions are closed under composition. We then mutually separate the following classes of functions from each other: the class of multi-valued functions that are non-deterministically computable, that of Las Vegas computable functions, and that of Monte Carlo computable functions. We give natural examples of computational problems witnessing these separations. As a specific problem which is Monte Carlo computable but neither Las Vegas computable nor non-deterministically computable, we study the problem of sorting infinite sequences. This is joint work with Vasco Brattka and Rutger Kuyper. Kalimullin: Degree spectra of generalized families (joint work with Marat Faizrahmov) An alpha-family is inductively defined as a countable beta-families, beta < alpha, while a 0-family is a set of integers. We will discuss different approaches to the computability of such families, and also study relationships with computability of algebraic structures and its degree spectra. Kihara: Topological aspects of enumeration degrees Pauly and the speaker introduced a general way of assigning a degree structure to each admissibly represented space. From this perspective, the enumeration degrees can be thought of as the degree structure of a universal second-countable T_0 space. This idea enable us to classify enumeration degrees in terms of general topology. For instance, the Turing degrees (total e-degrees) are the "finite dimensional metrizable e-degrees," and the continuous degrees are the "metrizable e-degrees." We can then talk about the existences of a Hausdorff (T_2) e-degree which is not an Urysohn (T_{2.5}) e-degree, a Frechet (T_1) e-degree which is Hausdorff-quasimininal, etc. Note that the admissibly represented spaces form a cartesian closed category, which is far larger than that of second-countable T_0 spaces. In general, the degree structure of a non-second-countable space is not a substructure of the enumeration degrees. For instance, one can show that the de Groot dual of the Baire space (which is not second-countable) has a point having non-enumeration degree. This is joint work with Steffen Lempp, Keng Meng Ng, and Arno Pauly. Knight: The Scott Isomorphism Theorem Scott proved that for a countable structure A for a countable language L, there is a sentence of L_{omega1,omega} (a Scott sentence) whose countable models are just the isomorphic copies of A. The complexity of an optimal Scott sentence measures the internal complexity of the structure. I will describe some recent results on complexity of Scott sentences. I had conjectured that every finitely generated group has a d-Sigma2 Scott sentence, and every computable finitely generated group has a computable d-Sigma2 Scott sentence. Recently, Harrison-Trainor and Ho showed that both conjectures are false. Alvir, McCoy and I applied a result of Montalban and one of A. Miller to show that a finitely generated group has a d-Sigma2 Scott sentence iff there is a generating tuple whose orbit is defined by a Pi1 formula. Using effective versions of the results of Montalban and A. Miller, we get the fact that a computable finitely generated group has a computable d-Sigma2 Scott sentence iff there is a generating tuple whose orbit is defined by a computable Pi1 formula. Gromov asked about the behavior of a typical or random group -- asking about the limiting density of group presentations. I will state a conjecture in this direction. Kohlenbach: Computability, Proof Mining and Metric Regularity Concepts of metric regularity and weak sharp minima which are generalizations of quantitative notions of strong uniqueness to problems with non-unique solutions play an important role in convex optimization. We will discuss computability and proof-theoretic aspects of this and present some applications to convex feasibility problems (partly joint work with Genaro Lopez-Acedo). Marcone: A peek at the higher levels of the Weihrauch hierarchy In this talk I will report on work in progress with my graduate student Andrea Cettolo. Weihrauch reducibility and the ensuing Weihrauch hierarchy have been successfully used to refine reverse mathematics results for statements which are provable in ACA0 and below. Our plan is to study the Weihrauch hierarchy for functions arising from statements laying at higher levels, such as ATR_0, of the reverse mathematics spectrum. In some cases we obtain the expected finer classification, but in other we observe a collapse of statements that are not equivalent with respect to provability in subsystems of second order arithmetic. This is in part due to the increased syntactic complexity of the statements. Our preliminary results deal with comparability of well-orderings, Sigma^1_1-separation, and Delta^1_1-comprehension. Mel'nikov: For equivalence structures to topological groups We will discuss three topics: the unexpected positive solution to a problem of Goncharov and Knight on equivalence structures (with Downey and Ng); the solution to a 60th problem of Maltsev for torsion abelian groups (with Ng); and the recent work on topological groups (with Khoussainov). I will try to explain the tight technical and methodological connection between these seemingly unrelated results. Miyabe: Randomness notions in Muchnik and Medvedev degrees The main question of this talk is whether one can construct a more random set from a random set. This question can be formalized by mass problems, that is, Muchnik and Medvedev degrees. As an example, computable randomness is strictly below ML-randomness in Muchnik degrees because there exists a high minimal Turing degree, which contains a computably random set but no ML-random set is Turing below it. Similar arguments can be applied for other pairs. There are two interesting pairs of randomness notions that have the same Muchnik degree. One pair is the one of ML-randomness and difference random. This is because, for ML-random set X+Y, at least one of X or Y should be difference random. In contrast ML-randomness and difference random have different Medvedev degrees. In other words, one can not compute a difference random from a ML-random uniformly. The proof uses the Levin-Kautz theorem and no-randomness-from-nothing for ML-randomness. The other pair is the one of Schnorr randomness and computable randomness. They have the same Muchnik degree but different Medvedev degrees. The proof extends the method separating Schnorr randomness and computable randomness using Levy's zero-one law from probability theory. We also discuss a version of tt-reduction. Ng: Weak truth table degrees of categoricity We investigate degrees of categoricity for the wtt degrees. In the classes that we investigate, we found that very few structures have a wtt degree of categoricity. We also consider categoricity for various strong reducibilities. Nies: Characterising the oracles that know half of each computable set The Delta parameter of a set A is a real in [0,1/2] that measures how well sets that A computes can approximate all computable sets, in the sense of lower density of the coincidence set. Dualising the methods of Monin that resolved the so called "Gamma question", we show that this parameter is either 0 or 1/2. Further, A has parameter 1/2 iff A computes a function bounded by double exponential 2^{2^n} that is almost everywhere different from each computable function. Unlike Monin's result, the equivalence is uniform. For reducibilities stronger than Turing, the Delta spectrum might be more varied. Reference: Logic Blog 2016 for now, available from my web page. Pauly: Weihrauch degrees and recursion theory In one view, Weihrauch reducibility can be seen as one of many reducibilities studied in recursion theory. In particular, it has a similar flavour to Medvedev reducibility. The Medvedev degrees embed into the Weihrauch degrees (in two different ways), but apart from that, many structural questions about the Weihrauch degrees are still open - and probably approchable using the recursion-theoretic toolbox. On the other hand, Weihrauch reducibility is used as a framework to study the computational content of mathematical theorems -- and in particular, can be applied to study the uniform aspects of theorems in recursion theory. I will present a survey on both aspects of the interplay of (classical) recursion theory and the study of Weihrauch degrees Shen': Stopping time complexity and monotone-conditional complexities revisited Recently Vovk and Pavlovich considered the following task: a program gets bits $x_1,x_2,\ldots$ one by one and should stop after reading some prefix $x_1\ldots x_n$. What is the complexity of this task? This complexity can be called a ``stopping time complexity of a string $x$''; one possibility is to define it as the minimal complexity of enumerating a prefix-free set containing $x_1\ldots x_n$. Vovk and Pavlovich also asked whether the prefix version of this notion coincides with the logarithm of a maximal lower semicomputable function $m(x)$ such that for every sequence $\alpha$ the sum of $m(x)$ over all $x$ that are prefixes of $\alpha$ does not exceed $1$. The answer turns out to be negative (for a simple reason), but the question is related to the classification of complexities: stopping time complexity of $x$ is $K(x|x)$ where $x$ in the condition is considered not as a terminated string but as a prefix of an infinite string (while the other $x$ is considered as a terminated string). We discuss different versions of the definition and some separation results (Mikhail Andreev). Slaman: Three Theorems Between Computability and Diophantine Approximation We will describe joint work with Veronica Becher, Yann Bugeaud and Jan Reimann in which we construct real number so as to control the properties of their expansions in different integer bases. Terwijn: Genericity, randomness, and differentiable functions. This is joint work with Rutger Kuyper. We present a theorem characterizing the notion of 1-genericity in terms of differentiable functions. We compare this to a recent characterization of the notion of 1-randomness, also in terms of differentiability. We also discuss variations about n-genericity, multiple differentiability, and polynomial time computability. Towsner: Constructing Chains and Antichains in Partial Orders In the setting of reverse mathematics (or, if one prefers, Turing ideals), the statement "the product of well-quasi-orders is a well-quasi-order" lies strictly between the better known statements CAC ("every partial ordering has either an infinite monotone sequence or an infinite antichain") and ADS ("every linear ordering has an infinite monotone sequence"). We'll describe how all these statements can be viewed in terms of colorings with "transitivity" restrictions on some colors and then outline a technique for separating statements of this kind. Vereshchagin: Are there non-stochastic objects? An object (encoded by a binary string x) is called stochastic if there is a simple plausible statistical explanation for it. As explanations we consider probabilistic Turing machines M whose running time is bounded by a polynomial of the length of the output. We call such a machine M a plausible explanation for x if every property of x recognized by a polynomial time deterministic Turing machine with a short program is shared by a non-negligible fraction of M's outputs. We call x stochastic if there is a plausible explanation M for x such that the program of M is short, i.e., the explanation is simple. Are all objects stochastic? Perhaps not. For instance, structured objects like paintings might be not stochastic. We will prove that under some complexity-theoretic assumption there are infinitely many objects that are not stochastic.The assumption states that there is a unary language in NP that is not recognized by any polynomial time probabilitsic machine. Westrick: Turing-, tt-, and m-reductions for functions in the Baire hierarchy (joint with Adam Day and Rod Downey) For arbitrary functions f:[0,1] --> R, (including in particular highly non-continuous functions), what would be the right notion of Turing reducibility and its variants? We present a computationally motivated definition of \leq_T, \leq{_tt}, and \leq_m for such functions, and show that within the Baire hierarchy, the linearly ordered \leq_T-equivalence classes correspond precisely to the proper Baire classes. Further, within the Baire 1 functions, the \leq_{tt} and \leq_m equivalence classes enjoy a natural correspondence with levels of the alpha rank on Baire 1 functions considered in Kechris and Louveau (1990).