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