M8890 Computability

Faculty of Science
Spring 2001
Extent and Intensity
2/1/0. 5 credit(s). Type of Completion: zk (examination).
Teacher(s)
prof. RNDr. Luboš Brim, CSc. (lecturer)
Guaranteed by
prof. RNDr. Luboš Brim, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Luboš Brim, CSc.
Course Enrolment Limitations
The course is only offered to the students of the study fields the course is directly associated with.
fields of study / plans the course is directly associated with
  • Mathematics (programme PřF, M-MA, specialization Discrete Mathematics)
  • Mathematics (programme PřF, N-MA, specialization Discrete Mathematics)
Course objectives
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
Further Comments
The course is taught annually.
The course is taught: every week.
The course is also listed under the following terms Spring 2000.
  • Enrolment Statistics (recent)
  • Permalink: https://is.muni.cz/course/sci/spring2001/M8890