## COT 6421 -- Theory of Computation II## Spring 2005 |

- 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.

- 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 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.

- 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
^{1730}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.

Back to Geoffrey Smith's home page.