“The Decanter Method”
Jonathan Stephenson, Department of Pure Mathematics, University of Waterloo
Jonathan Stephenson, Department of Pure Mathematics, University of Waterloo
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.
Jonathan Stephenson, Department of Pure Mathematics, University of Waterloo
Last week we saw how to prove that a K-trivial real cannot be Turing complete, but we made several simplifying assumptions that set constants equal to zero.
This week, we will show how to modify the construction we used to make it work when the constants are allowed to take on arbitrary values.
MC 5403
Michael Deveau, Department of Pure Mathematics, University of Waterloo
Michael Deveau, Department of Pure Mathematics, University of Waterloo
Now that we have verified that individual procedures respect their garbage quotas, we can use this information to show that the request set we have been working with is bounded. This will allow us to use the Recursion Theorem as promised. Following this, we will finally define the titular golden run, show that it exists, and begin to see how it helps us show that A is low for K.
Michael Deveau, Department of Pure Mathematics, University of Waterloo
At long last, we will show that the K-trivial set A we have been considering is low for K. To do this, we will expand on the brief teaser presented last time and show how a golden run may be augmented to build a request set W that witnesses that A is low for K. Of course, we have one final speed bump to take care of first: we must show that W is a bounded request set.
Mohammad Mahmoud, Department of Pure Mathematics, University of Waterloo
Omar Leon-Sanchez, McMaster University
Mohammad Mahmoud, Department of Pure Mathematics, University of Waterloo
Mohammad Mahmoud, Department of Pure Mathematics, University of Waterloo
This week we start chapter 2 and introduce some Relatively intrinsic notions. Basically we discuss R.i.c.e. (relatively intrinsic computably enumerable) relations and give some examples. Our goal is to prove a characterization theorem for R.i.c.e. relations.
MC 5417