Linda Brown Westrick
Various notions of computable reducibility, such as Turing reduction, truth table reduction, and many-one reduction, provide coarse- and fine-grained ways of saying that one infinite sequence can compute another one. Infinite sequences have discrete bits with discrete addresses, so what it means to “compute” one is clear: given an address as input, an algorithm should return the appropriate bit. What it means to “compute” a continuous function is less obvious, but also well established. However, for a larger class of functions (in particular those of the Baire hierarchy, which I will define) it is not at all clear what it means to compute one. I will present one possibility and describe its degree structure and how this structure relates to features of the Baire hierarchy. This is joint work with Adam Day and Rod Downey.