| Lecture Notes |
| Homework |
| Exams |
OK, if you're still reading, you probably want to know what this course is about. The theory of computation examines the questions "What is a computer?" and "What can it do?".
"What is a computer?" Maybe that seems obvious, a computer is that thing that sits on my desk or the notebook I sometimes lug around in my backpack. It runs Linux, or Windows, or MacOS, runs a web browser, a text editor, and some other handy-dandy applications. On of the first times I used a computer was about thirty years ago as a high school student at a summer math program at Whitman college in Walla Walla Washington (thanks to the National Science Foundation of the U.S.). We wrote our FORTRAN programs on punched cards, stood in line to put them in the hopper of a machine about the size of a large desk with 4Kbytes of main memory, and got the output printed by an electric typewriter that was part of the machine. Does that machine have anything in common with today's computers? Can we say anything about what computers can or cannot do that will still be true thirty years from now?
In this class, we'll look at simplified, mathematical models for different kinds of computers. They vary by how much memory they have and how they can access it. A finite state machine has a fixed amount of memory, a pushdown automaton has an infinite amount of memory, but it can only access it by pushing an value onto its stack or popping a value off of the stack, and it only has one stack. A Turing machine has also has an infinite amount of memory, organized as a long tape with a head that can scan back and forth on it. These models are chosen because they have simple descriptions, and for each kind of machine we can show that there are clearly defined classes of things that they can and cannot do.
Here's the punch line: anything the biggest, fasted computer in the world can do, can be done by a Turing machine, and there are things that a Turing machine cannot do. This means that there are problems that no computer can solve! These are known as "undecidable" problems, and their discovery counts in the top 10 intellectual breakthroughs of the 20th century (along with relativity, quantum mechanics, DNA and a handful of others).
So, the theory of computation is profound -- is it useful? Absolutely. First, there are problems that we cannot be solved by a computer: "Is this e-mail attachment a virus?", "Does this program have a bug?". Second, there are problems that can be solved in principle, but would take any computer many times the lifetime of the universe. These problems can be turned around to make secure codes -- they are the basis of computer cryptography, and with it, the enabling technology for e-commerce and providing data privacy. Third, these models are closely connected with how we define programming languages. Compiler writers use tools that automatically generate parts of the compiler from descriptions of the programming language in terms of these simplified machines. Fourth, while it's not possible to prove that an arbitrary program is free of bugs, many bugs can be found automatically in many programs. Such "formal verification" is built on the theory of computation that we study here.
Finally, computers will change. Computers thirty years from now are likely to be as different from today's machines as today's machines are different than that machine with a card-hopper that I used thirty years ago. How will they change? No one has a perfect crystal ball, so we can only guess. One thing we do know is that fundamental physical limits of what can be done with silicon chips means that the improvements won't come just by making the transistors smaller and faster, which has been the main driving force for the past 30-40 years. Parallelism is likely to be of increasing importance. Experiments with quantum computation, molecular computation, carbon nanotubes, and other approaches suggests ways we may be able to build computers that overcome the limits of silicon chips, but they don't compute in the same way. What will you do when programming is done in something much different than Java, C or C++? The simple automata that we study here provide the starting point for understanding what can be done with these other technologies. There is an enormous amount of work to be done to make the technologies practical, to figure out what the right programming languages and paradigms will be, to develop the new compilers, operating systems, and to invent applications and interfaces that take advantage of these technologies and make them useful to people.
So, you can study the theory of computation because it is a beautiful branch of theoretical computer science with elegant and profound results. Or, you can study it to better understand what computers can and cannot do, so you won't waste lots of time trying to write a program to solve a problem that has no solution. You, can study the theory of computation to be better prepared for the changes that we can't predict, but we know that big changes are inevitable. Or you can study it for whatever reason appeals to you.
No matter what your motivation, welcome to CpSc 421. I hope that you
find it to be an interesting and enjoyable term.
Mark