Computability Learning Seminar

Wednesday, June 8, 2016 10:00 am - 10:00 am EDT (GMT -04:00)

Jonathan Stephenson, Department of Pure Mathematics, University of Waterloo

“The Decanter Method (continued)”

Last week we introduced the decanter method, which we used to show that there is no wtt-complete K-trivial.

This week, we will strengthen the result by showing that a K-trivial cannot be Turing complete. We will see more clearly where the decanter method gets its name: our strategy will involve us assigning measure to a sequence of ”decanters” which may be ”poured” into each other. To complete the metaphor, we will see that occasionally we may suffer a ”spillage” and permanently lose some of our finite quantity of measure.

MC 5403