December 2, Building 303, Room B 11.
- Santiago Figueira, Universidad de Buenos Aires.
Feasible analysis, randomness, and base invariance .
Abstract. We show that polynomial time randomness of a real number does not depend on the choice of a base for representing it. Our main tool is an `almost Lipschitz' condition that we show for the cumulative distribution function associated to martingales with the savings property. Based on a result of Schnorr, we prove that for any base $r$, $n\cdot\log^2 n$-randomness in base $r$ implies normality in base $r$, and that~$n^4$-randomness in base $r$ implies absolute normality. Our methods yield a construction of an absolutely normal real number which is computable in polynomial time.
Joint work with Andre Nies .
2:45 break
3pm
- Takayuki Kihara, JAIST, Kanazawa
A hierarchy of the countably computable functions.
Abstract. A partial function f on Baire space is called countably (finitely, resp.) computable if it is decomposable into countably(finitely, resp.) many partial computable functions (or equivalently, f(x) is Turing reducible to x, where the Turing reduction depends on x, nonuniformly). If the domains of such partial computable functions can be in a pointclass Gamma, it is called Gamma-countably/finitely computable. By using these notions, we reveal the fine structure behind the Simpson-Slaman theorem stating that infinitely many Medvedev degrees exist inside the Muchnik degree of any nontrivial Pi^0_1 subset of Cantor space.
Joint Work with K. Higuchi.
3.45pm Coffee
4:15pm- Kenshi Miyabe, Tokyo Daigaku.
Variants of Layerwise Computability.
Abstract. We have a hierarchy of reals by computability, that is,
- computable reals
- weakly computable reals
- divergence bounded computable reals
- computably approximable reals.
A similar hierarchy exists in continuous functions, L^1-functions and layerwise continuous functions. This is interesting because of the relation with the omega operator and the notion of being generalized low.
5pm
- Alexander Gavruskin, Auckland University of Technology.
Computably enumerable structures.
Abstract. We investigate the dependence of computably enumerable structures on the equality relation which is fixed to a specific c.e. equivalence relation. In particular we compare c.e. equivalence relations in terms of classes of structures they permit to represent. Through this, we define partially ordered sets that depend on classes of structures under consideration. We investigate some algebraic properties of these partially ordered sets. For instance, we show that some of these partial ordered sets possess atoms, minimal, and maximal elements. We also fully describe the isomorphism types of some of those partial orders. This is a new work that brings in a fresh view and new ideas on interactions between algebraic structures and computability. This is a joint work with B. Khoussainov (UoA), F. Stephan (NUS), and S. Jain (NUS).
December 3, Building 303, Room B 11.
3:00
- Jing Zhang, National University of Singapore.
Weakly represented families in reverse mathematics.
Abstract. We introduce the notion of a weakly represented family of sets and functions into principles in Second Order arithmetic in the context of reverse mathematics. This extends the existing notions about sequence of sets or functions which are uniformly recursive in a set of the model. With the help of weakly represented families of sets and functions, we are able to investigate a larger class of sets or functions, for example, the class of total recursive functions, the class of recursive sets etc. Specifically, we investigate the Cohesive Principle for weakly represented family (COHW) and separate COHW from Cohesive Principle COH. Further, other related principles using weakly represented family of sets/functions are also investigated, such as Domination Principle (DOM), Avoiding Principle (AVOID), Meeting Principle (MEET) and Hyperimmune Principle (HIM). Our results show that weakly represented families are a natural and robust notion to formalize principles in reverse mathematics. Joint work with Frank Stephan.
4:00- Matthew Conder and Marcus Triplett, University of Auckland (student presentation).
5:00
Van der Waerden's Theorem and Szemeredi's Theorem.
Abstract. Van der Waerden (1927) showed that if you split the natural numbers into finitely many sets, then one of them has arbitrarily long arithmetical progressions. Szemeredi's 1975 Theorem is much stronger: any set of positive upper density has arbitrarily long arithmetical progressions. Green and Tao have used ideas from its proof to show there are arbitrarily long progressions in the primes. Supervised by Andre Nies.
- Rutger Kuyper, University of Nijmegen.
Coarse reducibility and randomness.
Abstract. We study the notion of coarse reducibility, introduced by Jockusch and Schupp. We say that a set A coarsely reduces to B if there is a single Turing functional which transforms every set which coincides with B on a set of asymptotic density 1 into a set which coincides with A on a set of density 1. In particular, we study how various notions from algorithmic randomness behave under this notion of reduction. Joint work with D. Hirschfeldt, C. G. Jockusch, Jr. and P. Schupp. - Takayuki Kihara, JAIST, Kanazawa
Organized by Andre Nies
2pm
Prior to the meeting 6 of the participants had at a retreat at Puka Beach, Nov 24-30. Program of the retreat.