Computability Learning Seminar

Jonathan Stephenson, Department of Pure Mathematics, University of Waterloo

“Cost functions”

We will introduce cost functions. These are used as an important method for constructing a set satisfying a desired lowness property. We will see that there is a standard cost function which can be used to build K-trivial sets, and some properties that K-trivials built by this method must satisfy as a consequence. Although we won’t prove it, in fact every K-trivial can be built using the standard cost function (this follows from the golden run method).

MC 5403