Wednesday, June 8, 2016 10:00 am
-
10:00 am
EDT (GMT -04:00)
Jonathan Stephenson, Department of Pure Mathematics, University of Waterloo
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