FI:I046 Computability II - Course Information

I046 Computability II

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

• Informatics (programme FI, B-IN)
• Informatics (programme FI, M-IN)
• Upper Secondary School Teacher Training in Informatics (programme FI, M-IN)
• Upper Secondary School Teacher Training in Informatics (programme FI, M-SS)
• Information Technology (programme FI, B-IN)

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

• Enrolment Statistics (Spring 1998, recent)
  
• Permalink: https://is.muni.cz/course/fi/spring1998/I046