Logic Seminar in Semester II AY 2012/2013

• 16/01/2013, 17:00 hrs, Week 1.
  John Case. Gold-style learning theory: a selection of highlights since Gold.
  Discussed will be E. Mark Gold's 1967 model of child language learning and some of its extensions since 1967. Gold cited psycholinguistic evidence that, in learning a language L (modeled as a formal language), children don't need or use information about L's complement; they only need and react to data about the (finite) strings in L. Mathematically, as will be briefly explained, the resultant theoretical work has a different character than if the learner were presented the whole characteristic function of L.
  Presented will be some motivated criteria of success developed since 1967 and some interesting mathematical constraints on this kind of learnability. The languages classes in the Chomsky Hierarchy are not learnable in the model of learning from only positive data about languages, a result depressing already to Gold. We'll present some positive results though and discuss how these may give hope. A modern take is that the possible and actual natural languages do not form a Chomsky Hierarchy class and may crosscut these in such as way as not to be subject to the mathematical constraints.
  Children may be insensitive to order of presentation of languages, and presented will be some local and global formal notions of order insensitivity together with theorems about their effects on learnability.
  There is an empirically observed phenomenon in child cognitive development called U-Shaped Learning. It occurs in many domains including language development and features a behavioral sequence of: success, then failure, then success again. For example, a child in naturally learning English irregular verbs may, for the past tense of the irregular verb to speak, first use spoke, then use speaked, and, then, finally, use spoke again. Presented are some formal analogs of U-Shaped Learning together with theorems on how such U-Shaped Learning can enhance learning power.
  If time permits, discussed will be some other learning criteria featuring plausible memory-limitations on the part of the learner.
  
  
• 23/01/2013, 17:00 hrs, Week 2.
  Bakhadyr Khoussainov. On finitely presented expansions of groups and algebras.
  We construct examples of computably enumerable finitely generated groups and algebras that fail to posses finitely presented expansions. The talk will be based on the paper to appear in Transactions of the American Math Society. The work is joint with Alexei Miasnikov.
  
  
• 30/01/2013, 17:00 hrs, Week 3.
  Dilip Raghavan. Combinatorial dichotomies and cardinal invariants - Part 1.
  The talks will be based on the results in my recent paper with Tordorcevic, "Some combinatorial dichotomies after forcing with a coherent Suslin tree". These results are part of an ongoing project to find equivalences between various phenomena in uncountable combinatorics and set theory of the reals under the P-ideal dichotomy and related principles.
  
  
• 06/02/2013, 17:00 hrs, Week 4.
  Dilip Raghavan. Combinatorial dichotomies and cardinal invariants - Part 2.
  This talk is a continuation of the talk from 30 January 2013 and will provide more details and explanations on the topics discussed in the previous week.
  
  
• 13/02/2013, 17:00 hrs, Week 5.
  Frank Stephan. Structures realised by recursively enumerable equivalence relations.
  The talk gives an overview of recent work on the following topic: Say that an r.e. equivalence relation realises a graph G iff there is an r.e. relation Edge of pairs such that the equivalence classes of E form the vertices and Edge forms the edges of G on this vertex-set. Given two r.e. equivalence relations E and F, one says that E is graph-reducible to F iff every graph realised by E is also realised by F. Now the question of the degrees of this graph-reducibility are investigated and corresponding questions are also asked for various natural classes of graphs. Furthermore, the degree structures are compared to those of the FF-reducibility between r.e. equivalence relations.
  This is joint work with Alexander Gavruskin, Sanjay Jain and Bakhadyr Khoussainov.
  
  
• 20/02/2013, 17:00 hrs, Week 6.
  Sanjay Jain. Automatic Learning from Positive Data and Negative Counterexamples.
  We introduce and study a model for learning in the limit by finite automata from positive data and negative counterexamples. The focus is on learning classes of languages with the membership problem computable by finite automata (automatic classes). We show that, within the framework of our model, automatic learners can learn all automatic classes when memory of a learner is restricted by the size of the longest datum seen so far. We also study capabilities of automatic learners in our model with other restrictions on the memory and how the choice of negative counterexamples (arbitrary, or least, or the ones whose size is bounded by the longest positive datum seen so far) can impact automatic learnability.
  This is joint work with Efim Kinber and Frank Stephan.
  
  
• 06/03/2013, 17:00 hrs, Week 7.
  Manat Mustafa. On minimal and principal numbering in the Ershov hierarchy.
  The talk gives an overview of recent work on the minimal and principal numbering in the Ershov hierarchy.
  
  
• 13/03/2013, 17:00 hrs, Week 8.
  Chong Chi Tat. Randomness in the higher setting.
  Algorithmic randomness over natural numbers is an active area of research in the study of computability. We discuss the notion of randomness in the setting of second order arithmetic from the point of view of higher recursion theory. The subject was initiated by Hjorth and Nies and illustrates a nice interplay between randomness and hyperarithmertic theory and descriptive set theory. In this talk, we present some of the recent work done by Chong, Nies and Yu.
  
  
• 20/03/2013, 17:00 hrs, Week 9.
  Liu Yiqun. Isolation pair and its induction strength.
  A classical result in d.c.e degree by S. Ishmukhametov and G. Wu is that a high d.c.e degree is isolated by a low c.e degree. First, we will review the strategies and the construction. Based on that, we discuss whether the infinite injury argument could be performed inside M which is a model of P^-+IΣ₁.
  
  
• 25/03/2013, 17:00 hrs, Week 10.
  Ludwig Staiger. Oscillation-free ε-random sequences.
  In algorithmic information theory, along with the randomness of infinite sequences a relaxation of this concept - so-called partially random sequences - are considered. These partially random sequences can be characterised in several ways: by gambling systems (so-called super-martingales) and growth functions, by Martin-Löf tests or by Kolmogorov-complexity.
  Per Martin-Löf had proven in 1966 that the usual (plain or simple) Kolmogorov complexity of random sequences necessarily oscillates. A similar result holds for the prefix-free variant of Kolmogorov complexity of random sequences. In contrast to this this is not true for the a priori complexity. In the talk we consider whether these oscillations can be also avoided for partially random sequences.
  For a priori Kolmogorov complexity it can be shown that for every positive ε between 0 and 1 (inclusive) oscillation-free ε-random sequences exist. Surprisingly, the same holds for the prefix-free variant of Kolmogorov complexity: it can be shown that for every positive ε between 0 to 1 (here exclusive) oscillation-free ε-random sequences exist.
  Then it is shown that the Hausdorff dimension of the set of all oscillation-free ε-random sequences is just ε. Finally for constructively described sets of sequences it is investigated when they contain a priori ε-random sequences. Here the Hausdorff dimension α of such sets is an upper bound on the possible value of ε. If, moreover, the Hausdorff measure of those sets does not vanish, they contain α-random sequences.
  Note: This talk will be held in AS6#05-10 (MR6) at the Department of Computer Science, the building is near the Central Library. The talk is on Monday instead of Wednesday. It is a joint talk together with the Theory Seminar of the School of Computing.
  
  
• 03/04/2013, 17:00 hrs, Week 11.
  Feng Qi. A universality theorem.
  We outline a proof of a universality theorem for type-1 mice.
  
  
• 10/04/2013, 17:00 hrs, Week 12.
  Li Wei. Effective aspects of differential functions.
  Kechris and Woodin defined a rank for everywhere differentiable functions from the view point of descriptive set theory. This rank was later named as Kechris-Woodin rank. In this talk, we will report on the recursive aspect of their results. We will show the following:
  1. The set {e: Φ_e describes an everywhere differentiable function in [0,1]} is Π¹₁ complete.
     
  2. If Φ_e describes an everywhere differentiable function in [0,1], then its Kechris-Woodin rank is less than ω₁^CK; conversely, given any recursive ordinal α>0, there is an everywhere differentiable function in [0,1] with a recursive description and Kechris-Woodin rank α.
     
  3. More generally, if Φ_e describes a continuous function in [0,1], then its Kechris-Woodin rank is less or equal to ω₁^CK.
  
  
  
• 17/04/2013, 17:00 hrs, Week 13.
  Jason Teutsch. Short lists for shortest descriptions in short time.
  Given a binary string, can one find a short description for it? The well-known answer is "no, Kolmogorov complexity is not computable." Faced with this barrier, one might instead seek a short list of candidates which includes a laconic description. In fact, efficiently computable short lists do exist, and I will discuss the extent to which one can obtain them. This talk will include a gentle introduction to Kolmogorov complexity followed by a discussion connecting short lists to classical combinatorics and randomness extraction.