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.

I046 Computability II

Faculty of Informatics
Spring 1999
Extent and Intensity
0/2. 2 credit(s). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
prof. RNDr. Luboš Brim, CSc. (lecturer)
Guaranteed by
Contact Person: prof. RNDr. Luboš Brim, CSc.
Prerequisites
I007 Computability && I011 Programming Language Semantics && M006 Set Theory II
Prerequisities: I007 Computability,I011 Programming Language Semantics, 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
  • This seminar is open to active participants only. Every participant is expected to study one or two topics from the list given bellow and to give a talk.
  • Recursion theorem, generalized Rice theorem, Rogers isomorphism theorem.
  • Application to logic. Arithmetical sets and functions, Goedel-Rosser incompleteness theorem.
  • Kleene hierarchy, Turing reducibility, arithmetical hierarchy.
  • Analytical hierarchy, applications to logic.
  • Computability on real numbers, complete partial orders, denotational semantics.
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 1998, Spring 2000.

I046 Computability II

Faculty of Informatics
Spring 1998
Extent and Intensity
0/2. 2 credit(s). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
prof. RNDr. Luboš Brim, CSc. (lecturer)
Guaranteed by
Contact Person: prof. RNDr. Luboš Brim, CSc.
Prerequisites
I007 Computability
Prerequisities: I007 Computability,I011 Programming Language Semantics, 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
  • This seminar is open to active participants only. Every participant is expected to study one or two topics from the list given bellow and to give a talk.
  • Recursion theorem, generalized Rice theorem, Rogers isomorphism theorem.
  • Application to logic. Arithmetical sets and functions, Goedel-Rosser incompleteness theorem.
  • Kleene hierarchy, Turing reducibility, arithmetical hierarchy.
  • Analytical hierarchy, applications to logic.
  • Computability on real numbers, complete partial orders, denotational semantics.
Language of instruction
Czech
The course is also listed under the following terms Spring 1999, Spring 2000.

I046 Computability II

Faculty of Informatics
Spring 2002

The course is not taught in Spring 2002

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, Spring 2000.

I046 Computability II

Faculty of Informatics
Spring 2001

The course is not taught in Spring 2001

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, Spring 2000.
  • Enrolment Statistics (recent)