Instructor: John W. Roach

622 McBryde

231-5368

Office Hours: MWF 11am

GTA: Eric Xin Zhou

xin@vt.edu

Final Exam Time — 0745 hours, Friday, 10 December 1999

Textbook: Harry Lewis and Christos Papadimitriou, Elements of the Theory of Computation, 2^nd edition, Upper Saddle River, NJ: Prentice-Hall, Inc., 1998.

Prerequisite: Math 3134 or Math 3034

Grades: Homework + Quizzes 45%

Midterm Exam 25%

Final Exam 30%

What is this course about?

Long ago, far away some people figured out how to build physical devices that could compute…… The question we wish to answer is how they did that. One answer is that they soldered a bunch of wires, resistors, capacitors and vacuum tubes together in a certain configuration that was just right…. This course says almost nothing about circuitry. Before wiring up a circuit, we must first have the right idea about what circuit could possibly realize computation. In other words, we need the right ideas about computation independent of circuitry in order to be able to build a computer. Of course, if we cannot figure out how to turn our ideas about systematic computation into an actual, physical computing device, then that’s a problem.

Why bother? Sounds like a history lesson.

Computational speed is always increasing but there are still many important problems that we want to be able to solve. Perhaps, if we were to change the model of computation from the one we know so well to a different model, then our computations would go much faster.

Is it really possible that some completely new kind of computer might appear and that we would use it?

There are people working to build such a device at this very moment.

Anything else?

Although you may not realize it, quite a lot of the software tools you use are based on ideas found only in a course like this.

Topics:

Finite State Machines

Infinite State Machines

Undecidability