Date: July 28, 2003
Room: ASB 9705
Speaker: Valeriy Bulitko, http://members.shaw.ca/booly
Title: Bounded reducibilities and Post's Problem
The talk contains some definitions of size of access to oracle for turing reducibility and describes reducibilities with restricted size of access to oracle. These restrictions are set by functions. Since the complexity of these functions can be bounded by degrees of unsolvability w.r.t. these restricted reducibilities we come to a diversive hierarchy of subturing reducibilities. This approach gives opportunities to specify some classical results in recursion theory. In this talk we apply the approach to the problem by Post.