DM/DMP83: Advanced Computability (7.5 ECTS)

STADS: 1506242

Level
PhD course

Teaching period

Varying.

Teacher responsible
Email: meer@imada.sdu.dk

Additional teachers
www.physik.uni-paderborn.de/~ziegler

Timetable
There is no timetable available for the chosen semester.

Comment:
Valgfrit kursus.

Prerequisites:
None

Academic preconditions:
DM19 must be known.

Course introduction
Efforts within Theoretical Computer Science are usually directed towards efficient computational solutions to certain problems. However before attempting to find a fast one, you better make sure there is an according algorithm at all. And indeed already this often turns out impossible even for practically important problems. Thus knowing the principal limits of computing avoids wasting time in futile attempts to find algorithms for uncomputable problems. For example in Software Verification, one would very much like to have a program´s correctness and in particular its termination checked by a computer (i.e., effectively). However this as well as many related problems turn out to be provably undecidable, irregardless of how much time or memory we provide. Computations involving real numbers are subject to even harder principal limits of algorithms´ capabilities: If the input is given only approximately (e.g., originating from some physical measurement and supplied with error bounds), the sign and more generally any discontinuous real function becomes uncomputable for reasons related to inherent numerical instability. And even under the presumption of exact real arithmetic (BSS-model), many functions remain uncomputable. The course will provide a concise introduction into this area of computability.

Expected learning outcome


Subject overview
Models of Computation, Arithmetic Hierarchy, Infinite Words, Recursive Analysis, Algebraic Computability.

Literature

• M.Ziegler: Lecture Notes on "Advanced Computability, (52 sider).
• K.Weihrauch : "A Simple Introduction to Computable Analysis" Electronic Colloquium on Computational Complexity , 1995.
• L.Blum, M.Shub, S.Smale : "On a Theory of Computation and Complexity over the Real Numbers", pp.1-46 in Bulletin of the American Mathematical Society vol. 21(1) (46 sider).
• T.Chadzelek, G.Hotz : Analytic Machines", pp.151-167 in Theoretical Computer Science vol. 219 (17 sider), 1999.

Syllabus
See syllabus.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
Oral exam, internal examiner. Grades according to the Danish 13-mark scale. There will an obligatory assignment that has to be passed in order to take the exam.

Expected working hours
The teaching method is based on three phase model.

Forelæsninger (30 t), eksaminatorier (30 t).
Educational activities

Language
No recorded information about the language used in the course.

Remarks
The course fits well together with the course on Real number algorithms taught by K. Meer in parallel which will focus on complexity in the BSS-model. Thus, both courses together shed light on the computational aspects of real number problems from different points of view.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.