MATH432 COMPUTABILITY THEORY
| Course Code: | 2360432 |
| METU Credit (Theoretical-Laboratory hours/week): | 3 (3.00 - 0.00) |
| ECTS Credit: | 6.0 |
| Department: | Mathematics |
| Language of Instruction: | English |
| Level of Study: | Undergraduate |
| Course Coordinator: | |
| Offered Semester: | Fall and Spring Semesters. |
Course Objectives
Course Content
Well-formed formulas of Peano arithmetic, Gödel numbering, primitive recursive functions, Gödels 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.