Computability, Fall Quarter 2010
Computability, Fall Quarter 2010
Albert Atserias

Organization:

  • When: Mondays and Wednesdays, 10:00am to 11:30am. Classes start on September 20, 2010.
  • Where: Room A4-203, Campus Nord, UPC, Barcelona. How to reach it? Here.
  • Grading method: max(60% homework + 40% exam, 100% exam)

    • Lecture notes (for now in catalan):

  • Lecture 1: Turing-computable functions (20/09, 22/09, 27/09)
  • Lecture 2: μ-computable functions (04/10, 06/10)
  • Lecture 3: Equivalence and Church-Turing thesis (13/10, 18/10)
  • Lecture 4: Universal machine and uncomputability of the halting problem (20/10)
  • Lecture 5: More uncomputable problems (25/10, 27/10, 03/11)
  • Lecture 6: Undecidability of first-order logic (08/11, 10/11)
  • Lecture 7: Decidability, semi-decidability, and completeness (15/11, 17/11)
  • Lecture 8: Arithmetic hierarchy (22/11, 24/11, 29/11)
  • Lecture 9: Undefinability of truth (01/12, 13/12)
  • Lecture 10: Incompleteness (15/12, 20/12)


    • Homework sheets:

  • Homework 1 (due 13/10)
  • Homework 2 (due 13/12)


    • Final exam:

  • Final exam will be on Thursday, January 20, 2011, from 10am to 12 noon in room A4-204, Campus Nord, UPC (note this is not the same as the usual classroom).


    • Last modified: 27/12/2010.