 |
Abstract: Computability theory investigates the algebraic structures one gets by considering notions of relative computability. Informally, one object A (say a set of natural numbers) can compute another such object B if A contains at least as much information as B. As one varies the collection of objects and the way we view information, the structure of information content (the so-called \emph{degree structure}) varies as well.
Many algorithms were devised in order to investigate these degree structures. Many of them are useful in a wide variety of contexts. It turns out, however, that some of them make essential use of finiteness of objects; these constructions cannot be generalized to situations in which true finiteness is replaced by similar, but different, notions.
I will describe the classical recursively enumerable degrees and their generalizations to admissible ordinals, exhibit the essential use of true finiteness in some constructions and discuss the effect this has on the structure of the degrees of information.
This talk will be accessible to graduate students.
|