COT 6421 -- Theory of Computation II Spring 2005

Geoffrey Smith

• ECS 320
• 305 348-6037
• E-mail: smithg @ cs.fiu.edu
• Office Hours: Mondays and Wednesdays, 2:00 -- 3:15
  I'll usually be happy to meet at other times. Send email, call, or drop by.

Introduction to the Theory of Computation by Michael Sipser.

Course Syllabus

Class Presentations

• Jose Morales. Computer viruses.
• Miaohua Xu. Lower bounds on TM time complexity.
• Andres Parra. Minimal NFAs
• Alberto Aguilar. One-way hash functions.
• Selim Kalayci. Approximation algorithms.
• Guillermo Guillen. Presburger Arithmetic.
• Alejandro Mendozo and Rigoberto Fernandez. Busy Beaver problem.
• Jing Zhang and Yingbo Wang. Immerman/Szelepcsenyi's proof.
• Paresh Gupta. Turing's 1936 paper.
• Wei Peng. Kolmogorov Complexity.
• Xiaosi Zhou. Primes in in P.

Homework Assignments

• Homework 1. Due Monday, January 31.
• Homework 2. Due Monday, February 14.
• Homework 3. Due Monday, February 28.
• Presentations. (Plan by end of March).
• Homework 4. Due Monday, March 28.
• Homework 5. Due Wednesday, April 20.

Resources

• Here is a link to Heiner Marxen's page describing the Busy Beaver problem. Amazingly, he has now identified a 6-state TM that, when run on a blank tape, halts after more than 10¹⁷³⁰ steps!
• Here is a link to Alan Turing's 1936 paper, On computable numbers, with an application to the Entscheidungsproblem.
• Here's a Java version of the proof that the Halting problem is undecidable: Halt.java.
• Some resources for Michael Sipser's Fall 2002 Theory of Computation course.