I007 Computability

Faculty of Informatics
Spring 2003
Extent and Intensity
2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
prof. RNDr. Luboš Brim, CSc. (lecturer)
prof. RNDr. Jan Strejček, Ph.D. (seminar tutor)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Luboš Brim, CSc.
Timetable
Tue 17:00–17:50 B410, Tue 18:00–18:50 B410, Thu 14:00–14:50 C525, Thu 15:00–16:50 A107
Prerequisites (in Czech)
I005 Formal Languages and Automata I && (! I507 Computability )&&(!NOW( I507 Computability ))
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
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.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • Theory of Recursive Functions and Effective Computability. Edited by Hartley Rogers. Cambridge: Massachusetts Institute of Technology, 1987, 482 s. ISBN 0262680521. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Language of instruction
Czech
Further comments (probably available only in Czech)
The course is taught last offered.
Information on course enrolment limitations: Předmět je vypisován naposledy. Dále bude nahrazen předmětem IB107.
Teacher's information
http://www.fi.muni.cz/usr/brim/I007
The course is also listed under the following terms Spring 1996, Spring 1997, Spring 1998, Spring 1999, Spring 2000, Spring 2001, Spring 2002.
  • Enrolment Statistics (recent)
  • Permalink: https://is.muni.cz/course/fi/spring2003/I007