Computability Theory

Course Description and Grading
This is the first part of a three-term course providing an introduction to the basic concepts and results of the mathematical theory of computability and computational complexity theory. It requires no essential prerequisites, except perhaps some familiarity with somewhat abstract mathematical reasoning, at the level of a course like Math 5.

The Fall term will be first devoted to the discussion of various theoretical models of computation, like Turing machines, register machines, Markov algorithms, and recursive functions. We will demonstrate their equivalence and discuss Church's Thesis. Then we will study the basic theory of computable functions and effectively enumerable sets on the integers. We will use this theory to show that certain problems, like the so-called Halting Problem for Turing machines, are undecidable, i.e. cannot be solved algorithmically.

The grades for this course will be based on the homework assignments.

Course Meeting Time and Location

Tuesday and Thursday
1:00 - 2:25 pm
310 Linde

Course Instructor Contact Information and Office Hours

kechris@caltech.edu
Office - 379 Linde


TA Contact Information and Office Hours

fshinko@caltech.edu
Office - 153 Linde
Office Hours: Monday 6:30pm-7:30pm or by appointment


Syllabus


Notes

 DateTopic 
 10/8/2018 Notes #1
notes1.pdf
 10/22/2018Notes #2
Notes2.pdf
 10/22/2018 Notes #3
 Notes3.pdf

There is no textbook for this course. Here is a list of books on computability theory:
  • H. Hermes, Enumerability, Decidability, Computability, Springer-Verlag, 1970.
  • Y. Manin, A Course in Mathematical Logic for Mathematicians, Springer, 2010.
  • M. Carey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979.
  • Handbook of Mathematical Logic, J. Barwise, Ed., North-Holland, 1977.
  • M. Machtey and P. Young, An Introduction to the General Theory of Algorithms, North-Holland, 1978.
  • A. Yasuhara, Recursive Function Theory and Logic, Academic Press, 1971.
  • G. Boolos, J. Burgess and R. Jeffrey, Computability and Logic, Cambridge Univ. Press, 2002.
  • N. Cutland, Computability: An Introduction to Recursive Function Theory, Cambridge Univ. Press, 1980.
  • M. Davis, Computability and Unsolvability, Dover, 1985.
  • E. Engeler, Introduction to the Theory of Computation, Academic Press, 1973.
  • M. Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, 1967.
  • B. Trakhtenbrot, Algorithms and Automatic Computing Machines, D.C. Heath, 1963.
  • A. Malcev, Algorithms and Recursive Functions, Noordhoff, 1970.
  • H. Lewis and C. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1997.
  • H. Rogers, Theory of Recursive Functions and Effective Computability, MIT Press, 1987.
  • G. Tourlakis, Theory of Computation, Wiley, 2012.
  • H. Enderton, Computability Theory, Academic Press, 2011.
  • M. Sipser, Introduction to the Theory of Computation, Course Technology, 2005.
  • M. Davis, R. Sigal and E. Weyuker, Computability, Complexity and Languages, Morgan Kaufmann, 1994.
  • R. Weber, Computability Theory, Amer. Math. Society, 2012.
  • D. Bridges, Computability: A Mathematical Sketchbook, Springer, 1994



Course Policies

In each homework set, there will be one starred problem on which no collaboration is allowed. For the other problems, collaboration is allowed but you should write up your own solutions. You cannot look up solutions to the problems from any source, including books, previous years' solutions, the Internet, etc. 
Late submissions without prior approval from the instructor are not allowed except for medical problems or serious personal difficulties in which a note from the Dean's office is provided.


Exercises

 10/3/2018Exercise set #1
exercise1.pdf
 11/3/2018 Exercise set #2
exercise2.pdf


Homework Assignments

 Date PostedAssignment Due Date  Solutions
 10/3/2018Assignment #A
HomeworkA.pdf
10/16/2018assignA-sol.pdf
 10/12/2018Assignment #B
HomeworkB.pdf
10/23/2018assignB-sol.pdf
 10/22/2018Assignment #C
HomeworkC.pdf
10/30/2018
assignC-sol.pdf
 10/29/2018Assignment #D
HomeworkD.pdf
11/6/2018
assignD-sol.pdf
 11/3/2018Assignment #E
HomeworkE.pdf
11/13/2018assignE-sol.pdf
 11/11/2018Assignment #F
HomeworkF.pdf
11/20/2018assignF-sol.pdf
 11/18/2018Assignment #G
HomeworkG.pdf
11/27/2018 assignG-sol.pdf
 11/25/2018Assignment #H (last homework)
HomeworkH.pdf
 12/6/2018 (note change in day)
 assignH-sol.pdf


Collaboration Table

Homework
You may consult: 
Suggested or other booksYES
Solution manualsNO
InternetYES
Your notes (taken in class)YES
Class notes of othersYES
Your hand copies of class notes of othersYES
Photocopies of class notes of othersYES
Electronic copies of class notes of othersYES
Course handoutsYES
Your returned homeworkYES
Solutions to homework (posted on course webpage)YES
Homework / exams of previous yearsNO
Solutions to homework / exams of previous yearsNO
Emails from TA or the instructorYES
You may:
Discuss problems with othersYES
Look at communal materials while writing up solutionsYES
Look at individual written work of othersNO
Look up solutions to problems from any sourceNO
Ċ
Alexander Kechris,
Oct 8, 2018, 9:29 AM
Ċ
Alexander Kechris,
Oct 12, 2018, 10:08 AM
Ċ
Alexander Kechris,
Oct 22, 2018, 9:35 AM
Ċ
Alexander Kechris,
Oct 29, 2018, 10:07 AM
Ċ
Alexander Kechris,
Nov 3, 2018, 4:36 PM
Ċ
Alexander Kechris,
Nov 11, 2018, 10:16 AM
Ċ
Alexander Kechris,
Nov 18, 2018, 9:24 AM
Ċ
Alexander Kechris,
Nov 25, 2018, 10:14 AM
Ċ
Alexander Kechris,
Oct 22, 2018, 9:43 AM
Ċ
Alexander Kechris,
Oct 22, 2018, 10:38 AM
Ċ
Forte Shinko,
Oct 18, 2018, 3:12 PM
Ċ
Forte Shinko,
Oct 25, 2018, 8:30 PM
Ċ
Forte Shinko,
Nov 1, 2018, 1:09 PM
Ċ
Forte Shinko,
Nov 8, 2018, 5:39 PM
Ċ
Forte Shinko,
Nov 15, 2018, 9:54 AM
Ċ
Forte Shinko,
Nov 23, 2018, 11:44 AM
Ċ
Forte Shinko,
Nov 29, 2018, 1:31 PM
Ċ
Forte Shinko,
Dec 7, 2018, 3:17 PM
Ċ
Alexander Kechris,
Oct 3, 2018, 9:25 AM
Ċ
Alexander Kechris,
Nov 3, 2018, 4:36 PM
Ċ
Alexander Kechris,
Oct 8, 2018, 9:13 AM
Ċ
toc.pdf
(53k)
Alexander Kechris,
Oct 2, 2018, 5:24 PM