Date: July 28, 2003
Time: 3:00pm
Room: ASB 9705

Speaker: Valeriy Bulitko, http://members.shaw.ca/booly

Title: Bounded reducibilities and Post's Problem

Abstract:
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.