Sendai Logic School 2015

■Conference Venue

10 March (Tuesday), 2015
Kawai Hall, Tohoku University(Mathematical Institute)


Stanley Wainer (Leeds)
NingNing Peng (Singapore)
Keita Yokoyama (JAIST)


March 10th
TIME Speaker
14:00 - 14:30 NingNing Peng
14:45 - 15:45 Keita Yokoyama
16:00 - 17:00 Stanley Wainer


NingNing Peng
Title: A generalization of Liu-Tanaka theorem
Abstract: In 2007, Liu and Tanaka show that for any uniform binary AND-OR tree on the assignments that are independently distributed (ID), the distributional complexity is achieved only if the assignments are also identically distributed (IID).
We generalize Liu-Tanaka's result to uniform level-by-level $k$-brabching AND-OR tree. The technique is different from available proofs. One part of our proof is by generalize Suzuki-Niida's "fundamental relationships between costs and probabilities". Another part of our proof is by analyse the algorithms.
Keita Yokoyama
Title: Several questions on the restricted versions of Ramsey's theorem
Abstract: In the field of reverse mathematics, so many variations of Ramsey's theorem are studied, e.g., stable Ramsey theorem, transitive Ramsey theorem, Rainbow Ramsey theorem, thin set theorem, pseudo Ramsey theorem, etc. Although many important works are done in this area, there still remain a lot of interesting questions. In this talk, I will try to classify some of these, and show many questions which should be solved.
Stan Wainer
Title: A miniaturized predicativity
Abstract: This talk attempts to characterize those recursive functions which are "predictably terminating" according to a finitistic point of view.
The basis of the work is Leivant's (1995) theory of ramified induction over N, which has elementary recursive strength. It has been redeveloped and extended in various ways by many people. Eg. Spoors & W. (2012) built a hierarchy of ramified "input-output" theories whose strengths correspond to the levels of the Grzegorczyk hierarchy. Here, a further extension of this hierarchy is developed, with one additional input level on top (level omega). The underlying logic is an autonomously generated infinitary calculus with arbitrary finitely-many stratification levels of numerical inputs and a ramified Repetition Rule. The autonomous control on allowable ordinals is based on a weak (finitistic) notion of "pointwise transfinite induction". It turns out that the ordinal of this theory is then Gamma-0; the provably computable functions are those which are resource-bounded by the slow growing hierarchy; and these are the functions elementary recursive in the Ackermann function.


[sendai logic homepage]
[JSPS-NUS Joint Workshop in Mathematical Logic and Foundations of Mathematics]
[Sendai Logic School]

Organizer: Kazuyuki Tanaka (Math. Inst., Tohoku Univ.)
Contact: sendailogic[at]
Partially Supported by: JSPS-NUS Bilateral Program and
Grants-in-Aid for Scientific Research (KAKENHI) No.23340020.
Copyright (c) 2015 Sendai Logic School All Rights Reserved.