# CSE 6321 - Computability and Complexity

# Spring 2013

## 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:

Extra office hours: Nan Deng, deng.72@osu.edu,
Bolz Hall 0109, Mon Feb 18th, 2:00pm-3:00pm.

## Textbook:

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

## Recommended reading:

## Syllabus:

PDF

## Office hours:

By instructor, Dreese Labs 495, Tue 2:30-3:30pm.

By grader, Nan Deng, deng.72@osu.edu,
Bolz Hall 0109, Fri 1:30pm-2:30pm.

## Problem Sets:

PS1 (due lecture on February 14th). Solutions.

PS2 (due lecture on April 2nd). Solutions.

PS3 (due lecture on April 18th). Solutions.

## Topics by lecture (tentative):