CSE 6321 - Computability and Complexity

Spring 2014

Thought provoking links:

http://en.wikipedia.org/wiki/Hilbert's_tenth_problem
http://rjlipton.wordpress.com/2010/01/20/are-the-reals-really-uncountable/
http://en.wikipedia.org/wiki/Busy_beaver

Announcements:

Textbook:

Introduction to the Theory of Computation, third edition. M. Sipser.

Recommended reading:

Syllabus:

PDF

Office hours:

By grader: Joseph Anderson, 

andejose@cse.ohio-state.edu, in Caldwell Lab 405, Tuesday 3-4pm or by appointment.

By instructor, Dreese Labs 495, Monday 2:30-3:30pm or by appointment.

Problem Sets:

PS1 (due beginning of lecture on January 31st). Solutions.
PS2 (due beginning of lecture on February 10th). Solutions.
PS3 (due beginning of lecture on March 5th). Solutions.
PS4 (due beginning of lecture on March 19th). Solutions.
PS5 (due beginning of lecture on April 14th). Solutions.
PS6 (due beginning of lecture on April 21st). Solutions.

Topics by lecture (tentative):