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.