Generic computability, geometric group theory and Turing reducibility
Time and place
4 PM on Friday, October 29th, 2010; GC 5417
Paul Schupp (Univ. of Illinois)
Abstract
Abstract. We define the idea of generic computability and generic complexity and review some results on generic-case complexity in geometric group theory. We then discuss how generic computability interacts with classic concepts of computability theory: computably enumerable sets, bi-immune sets and Turing reducibility. We define a general concept of generic reducibility and explain why there is an order-preserving embedding of Turing degrees into the generic degrees which is not surjective.
