Blogs about: 116b
Featured Blog
116b- Lecture 20
Given any complete, consistent extension of , we showed that there is a minimal model of . This model is unique up to (unique) isomorphism, it is rigid (i.e., it has no automorphisms other than the id… more →
Computability Theory
116b- Lecture 20
andrescaicedo wrote 1 year ago: Given any complete, consistent extension of , we showed that there is a minimal model of . This mode … more →
116b- Homework 9
andrescaicedo wrote 1 year ago: Homework 9 Due Tuesday March 18 at 1pm. … more →
116b- Lecture 19
andrescaicedo wrote 1 year ago: We showed that Exponentiation is Diophantine, completing the proof of the Davis-Matiyasevich-Putnam- … more →
116b- Lecture 18
andrescaicedo wrote 1 year ago: Hilbert’s tenth problem asks whether there is an algorithm that given a polynomial with intege … more →
116b- Homework 8
andrescaicedo wrote 1 year ago: Homework 8 Due Tuesday March 11 at the beginning of lecture. Important update: In problem 4.(a), rec … more →
116b- Lecture 17
andrescaicedo wrote 1 year ago: We proved the Rice, Shapiro, McNaughton theorem characterizing index sets. We also showed that there … more →
116b- Lecture 16
andrescaicedo wrote 1 year ago: (Covered by Todor Tsankov) We defined the analog of the halting problem for any oracle and showed th … more →
116b- Lecture 15
andrescaicedo wrote 1 year ago: We proved that the class of functions computable by means of Turing machines coincides with the clas … more →
116b- Homework 7
andrescaicedo wrote 1 year ago: Homework 7 Due Tuesday March 4 at the beginning of lecture. … more →
116b- Lecture 14
andrescaicedo wrote 1 year ago: We defined translations of a language in another and interpretations between theories. These notions … more →
116b- Homework 6
andrescaicedo wrote 1 year ago: Homework 6 Due Tuesday February 26 at the beginning of lecture. … more →
116b- Lecture 13
andrescaicedo wrote 1 year ago: We proved the Kanamori-McAloon result on regressive functions as a corollary of Ramsey’s theor … more →
116b- Lecture 12
andrescaicedo wrote 1 year ago: We sketched the method of indicators and the hierarchy of fast-growing functions as techniques to pr … more →
116b- Lecture 11
andrescaicedo wrote 1 year ago: We presented the provability conditions and showed how a theory with a provability predicate satisfi … more →
116b- Homework 5
andrescaicedo wrote 1 year ago: Homework 5 Due Tuesday February 19 at the beginning of lecture. … more →
116b- Lecture 10
andrescaicedo wrote 1 year ago: We showed that proves the completeness theorem. We then proved the second incompleteness theorem usi … more →
116b- Lecture 9
andrescaicedo wrote 1 year ago: (Covered by Todor Tsankov) We proved the -uniformization theorem. This allowed us to introduce the s … more →
116b- Lecture 8
andrescaicedo wrote 1 year ago: (Covered by Clinton Conley.) We proved the Gödel-Rosser incompleteness theorem, as a consequence of … more →
116b- Homework 4
andrescaicedo wrote 1 year ago: Homework 4 Due Tuesday February 12 at the beginning of lecture. … more →
