M8890 Computability

Faculty of Science
Spring 2000
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)
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
Further Comments
The course is taught annually.
The course is taught: every week.
The course is also listed under the following terms Spring 2001.
  • Enrolment Statistics (Spring 2000, recent)
  • Permalink: https://is.muni.cz/course/sci/spring2000/M8890