Comparing induction and bounding principles over RCA0 and RCA*0

Abstract: In this talk, I will discuss joint work with Damir D. Dzhafarov and Denis R. Hirschfeldt, and more recent work following that line of research. Our work centers on the characterization of reductions between Π12 problems P and Q in terms of winning strategies in certain games. These characterizations were originally introduced by Hirschfeldt and Jockusch in [1]. I will discuss extensions and generalizations of these characterizations, including a certain notion of compactness that allows us, for strategies satisfying particular conditions, to bound the number of moves it takes to win. This bound is independent of the instance of the problem P being considered. This allows us to develop the idea of Weihrauch and generalized Weihrauch reduction over some base theory. Here, we will focus on the base theory RCA0 and the weaker system RCA*0. In this talk, I will explore these notions of reduction among various principles, including bounding and induction principles. I will present a metatheorem that allows us to obtain many nonreductions between these principles.

[1] D. R. Hirschfeldt and C. G. Jockusch, Jr.: On notions of computability-theoretic reduction between Π12 principles. Journal of Mathematical Logic 16 (1650002), 59 pp. (2016)

logic

Audience: researchers in the topic

Computability theory and applications

Series comments: Description: Computability theory, logic

The goal of this endeavor is to run a seminar on the platform Zoom on a weekly basis, perhaps with alternating time slots each of which covers at least three out of four of Europe, North America, Asia, and New Zealand/Australia. While the meetings are always scheduled for Tuesdays, the timezone varies, so please refer to the calendar on the website for details about individual seminars.