I046 Computability II

Faculty of Informatics
Spring 2000
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
prof. RNDr. Luboš Brim, CSc. (lecturer)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Luboš Brim, CSc.
Prerequisites
I997 State Exam || ( I007 Computability && M006 Set Theory && P998 Bc-Exam )
Prerequisities: I007 Computability,M006 Set Theory
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
  • Recursion theorem, generalized Rice theorem, Rogers isomorphism theorem. Applications.
  • Application to logic. Arithmetical sets and functions, Goedel-Rosser incompleteness theorem. Goedel's second incompleteness theorem.
  • Relativized computability. Programs with oracles.
  • Kleene hierarchy, Turing reducibility, tt-reducibility, arithmetical hierarchy.
  • Post's problem.
  • Analytical hierarchy, applications to logic.
  • Computability on real numbers, complete partial orders, domains.
Literature
  • Theory of Recursive Functions and Effective Computability. Edited by Hartley Rogers. Cambridge: Massachusetts Institute of Technology, 1987, 482 s. ISBN 0262680521. info
Language of instruction
Czech
Further Comments
The course is taught once in two years.
The course is taught every week.
Teacher's information
http://www.fi.muni.cz/usr/brim/I046
The course is also listed under the following terms Spring 1998, Spring 1999.
  • Enrolment Statistics (recent)
  • Permalink: https://is.muni.cz/course/fi/spring2000/I046