FI:I007 Computability - Course Information
I007 Computability
Faculty of InformaticsSpring 1996
- Extent and Intensity
- 0/0. 3 credit(s). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
- Teacher(s)
- prof. RNDr. Luboš Brim, CSc. (lecturer)
- Guaranteed by
- Contact Person: prof. RNDr. Luboš Brim, CSc.
- Course Enrolment Limitations
- The course is also offered to the students of the fields other than those the course is directly associated with.
- fields of study / plans the course is directly associated with
- Informatics (programme FI, B-IN)
- Informatics (programme FI, M-IN)
- Upper Secondary School Teacher Training in Informatics (programme FI, M-IN)
- Upper Secondary School Teacher Training in Informatics (programme FI, M-SS)
- Information Technology (programme FI, B-IN)
- Syllabus
- Algorithms, Church's thesis.
- Syntax and semantics of WHILE-programs, computable functions, computability on words.
- Standard enumeration of computable functions, enumeration (utm) theorem, parametrization (smn) theorem, effective numberings, Kleene's normal form theorem.
- Recursive and recursively enumerable sets, enumeration of r.e. sets, closure properties.
- Examples of undecidable problems, reduction and diagonalization, halting problem, verification problem, equivalence problem.
- Riece's theorems.
- Creative and productive sets, m-complete and 1-complete sets, effectively inseparable sets, simple and immune sets.
- Recursion theorem, applications of the recursion theorem.
- Alternative approaches to computability, recursive functions.
- Language of instruction
- Czech
- Enrolment Statistics (Spring 1996, recent)
- Permalink: https://is.muni.cz/course/fi/spring1996/I007