COT 6421 -- Theory of Computation II
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.
. Computer viruses.
. Lower bounds on TM time complexity.
. Minimal NFAs
. One-way hash functions.
. Approximation algorithms.
. Presburger Arithmetic.
Alejandro Mendozo and Rigoberto Fernandez
. Busy Beaver problem.
Jing Zhang and Yingbo Wang
. Immerman/Szelepcsenyi's proof.
. Turing's 1936 paper.
. Kolmogorov Complexity.
. Primes in in P.
. Due Monday, January 31.
. Due Monday, February 14.
. Due Monday, February 28.
. (Plan by end of March).
. Due Monday, March 28.
. Due Wednesday, April 20.
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
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:
Some resources for
Michael Sipser's Fall 2002 Theory of Computation course
Geoffrey Smith's home page