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).