max planck institut
informatik

# Limits of Computational Learning (SS 2012)

## Basic Information

Lecture time Wednesday 10-12
Exercise time Friday 10-12
Lecture rooms Wednesdays: E1.4 Room 024;
Fridays: E1.4 Room 023
Lecturer Timo Kötzing
Content 3,5,7,11,13,... what's next? What general rule (apparently) produces this sequence? Maybe the sequence lists all the odd primes, but what if the next datum is 15? Maybe all odd numbers that are not squares?
In this course we will study learning (identification) of infinite objects (such as infinite sequences) from finite data (such as initial pieces of the sequence), also known as Inductive Inference. What (collections of) sequences can be learned? What does learning, or identification, actually mean? We will discuss and compare several notions of "identification." The main focus lies on exploring the limits of what can be learned algorithmically.
Prerequisites If you can write proofs and at least 2 of the following statements are true for you, then you fulfill the requirements of the course. Statements: I know the Turing-machine model (or some other abstract computation model). I know what "computably enumerable" means. I know what "halting problem" refers to.
Credits The grade will be determined based on the performance in the exercises and a (short) final exam. Successful participation will earn you 6 credits.
Exercises There will be exercises every week. These exercises will be discussed in the exercise session of the following week. It is permissable to work on the exercises in groups of two people.
Lecture Notes I provide my lecture notes for your convenience. I believe that all assigments are solvable with the lecture notes and not other material.
Final Exam The final exam will be a short oral exam; I compiled a list of areas for your convenience.
Lesson Plan
DateTopic
Apr 18Definitions and Remarks [slides] Exercise 1 NOTE: The third exercise of the handout from class is postponed!
Apr 25Basic Toolkit: Recursion TheoremsExercise 2NOTE: Room Changed! Now in Building E1 7, Room 10.
May 2No Class
May 9Advanced Toolkit: Infinite Self ReferenceExercise 3
May 16Learning CriteriaExercise 4NOTE: Room Changed! Now in Building E1 7, Room 10.
May 23Basic IdentificationExercise 5NOTE: Exercise 5 has changed on May 24.
May 30Approximate IdentificationExercise 6
Jun 6Consistency and IterativenessNo new exerciseNOTE: No exercise session on June 8.
Jun 14Loose EndsExercise 7NOTE: Class now on Thursdays, 10am, same room.
Jun 21Reliability and PrudenceExercise 8
Jun 28Wiehagen's ThesisNo new exercise
Jul 4Concluding Function LearningExercise 9NOTE: Class this week on Wednesday, 10am.
Jul 12No class
Jul 19Language LearningExercise 10
Jul 26Wrapping Up

Search MPII (type ? for help)