In this undergraduate seminar at M.I.T., students present and discuss the subject matter taken from current journals or books. Topics vary from year to year. Instruction and practice in written and oral communication are provided. Enrollment is limited to 12.
This term’s topic: Kolmogorov complexity and algorithmic randomness
Algorithmic Randomness describes what it means for a string of bits to be random using notions from computability theory, information theory, and probability theory. The Kolmogorov Complexity of a string is its intrinsic information and is defined in terms of incompressibility. This seminar will explore these important notions and their applications. Possible topics for student projects include coding theory, learning theory, alternative notions of randomness, and entropy in physics.
Textbook
Li and Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications, 2nd edition.
Course Format
Presentations
Most of the lecture periods will be devoted to student presentations of assigned readings. Each student will be expected to present three or four times during the semester. Interspersed with the presentations, we will also have workshops on communication skills, including workshops on effective mathematics writing, and informative technical presentations. The component of the grade allotted to class presentations and participation will be determined by a combination of attendance and participation, the quality and growth of presentation skills, and a self-assessment.
Psets
Weekly problem sets will be assigned based on the lectures and readings. They are due in class at the beginning of each Thursday meeting. You are allowed and encouraged to work on the pset problems together. However, you must write up the solutions individually. Since 18.504 is designated a CI-M (communication intensive) course, you will be graded on the style of your solutions in addition to their correctness. The lowest pset grade will be dropped. No late homework will be accepted.
Final paper
The final project of the semester is a 10- to 12- page paper on a topic related to the course material. To establish good writing and editing habits, there will be a peer-editing and revision process near the end of semester. The final paper grade will incorporate grades for the proposal, first draft, peer-editing, and the final product.
Grading
Final grades in the course will be assigned according to the following approximate weighting.
- Class presentations and participation: 35 %
- Psets: 30 %
- Final paper: 35 %
Topics of past logic seminars
- Introduction to mathematical logic
- Set Theory
- Finite model theory
- Decidability and Undecidability
Materials for this course are available at the lower-left corner of this page, under the head “Related Media Folders.”
