FI:IA046 Computability - Course Information

IA046 Computability

Extent and Intensity

2/0. 2 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)

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

Thu 14:00–15:50 B410

Prerequisites

! I046 Computability II
Prerequisities: IB107 Computability and Complexity,MA006 Set Theory

Course Enrolment Limitations

The course is only offered to the students of the study fields the course is directly associated with.

fields of study / plans the course is directly associated with

• Applied Informatics (programme FI, N-AP)
• Informatics (programme FI, M-IN)
• Informatics (programme FI, N-IN)
• Upper Secondary School Teacher Training in Informatics (programme FI, M-IN)
• Upper Secondary School Teacher Training in Informatics (programme FI, M-SS)
• Upper Secondary School Teacher Training in Informatics (programme FI, M-TV)
• Upper Secondary School Teacher Training in Informatics (programme FI, N-SS)

Course objectives

The course is focused on deeper understanding of results in the computability theory with emphasis on methods and techniques used to prove such results.

Syllabus

• Recursion theorem, generalized Rice theorem, Rogers isomorphism theorem.
• 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.
• 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

Assessment methods (in Czech)

Zkouška je písemná a ústní. V případě zadání průběžných testů během semestru, mají tyto podíl nejvýše 30% na závěrečném hodnocení. Pomocné materiály nejsou povoleny.

Language of instruction

Czech

Further Comments

The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/brim/IA046

• Enrolment Statistics (Spring 2005, recent)
  
• Permalink: https://is.muni.cz/course/fi/spring2005/IA046