MATH432 COMPUTABILITY THEORY
| Course Code: | 2360432 |
| METU Credit (Theoretical-Laboratory hours/week): | 3(3-0) |
| ECTS Credit: | 6.0 |
| Department: | Mathematics |
| Language of Instruction: | English |
| Level of Study: | Undergraduate |
| Course Coordinator: | |
| Offered Semester: | Fall and Spring Semesters. |
Course Content
Well-formed formulas of Peano arithmetic, Gödel numbering, primitive recursive functions, Gödel’s Incompleteness Theorems, partial recursive functions, Turing machines, Church-Turing Thesis, decidabilitiy, recursion theorem, s-m-n theorem, padding lemma, recursively enumerable sets, computable approximations, halting problem, creative sets, simple sets, Turing reducibility, Turing degrees, properties of Turing degrees, recursively enumerable degrees, joins, Turing jump.Selected topics may include: Arithmetical hierarchy, limit lemma, finite extension method, co-infinite extension method, minimal degrees, splitting threes, jump classes, jump inversion, low and hign degrees, finite injury priority method, r.e. permitting, computable dimination, hyperimmune-free degrees.