In virtually all of the courses of the Computer Science curriculum the notion of "computation" is easily understood on a very practical level. Essentially, it is "what a computer does." A machine--the hardware--processes a program in some language--the software. This vague characterization, while adequate for studies of practical, problem-solving methods, is deficient when it comes to taking a close look at what really constitutes the notion of computation. That is what we will be doing in this class. We will build abstract, mathematical models of both computers and programs in the forms of abstract machines and formal languages, respectively. Having built such models we will be able to reason about them in a formal way, proving various properties and precisely characterizing their expressive and computational power. We will be able to compare and contrast different models in terms of these characteristics. Ultimately, we will study Turing machines and the recursively enumerable languages that they recognize. These abstract machines and languages--though conceptually simple--are every bit as powerful in terms of what they can compute as the fastest modern supercomputers. Moreover, it is the accepted theory that these machines formally capture the notion of all that is computable. As such, they will allow us to consider the subject of the existence of problems which no program or computer can ever be designed to solve.
CSC-461 puts into perspective all of the computer science work you have done up to this time, and all that you will continue to do. It is important to grasp the theoretical underpinnings of the discipline if you are to be an effective computer scientist. The course builds directly upon the discrete mathematics concepts studied in CSC-261, and familiarity with them is expected. Though it is primarily theoretical, in this course we will never stray too far from the practical aspects of computer science as well. With each new set of models that we study we will consider its direct application to CS. We will do a lot of problem-solving. Some problems will be solved as homework, and others interactively in class.
We will also be taking a look at the life and contributions of Alan Turing this semester. The primary objective of these readings and discussions will be to get a deeper understanding of the significance of Turing machines by reading a non-academic treatment of them. Readings on Turing's life and other contributions to computer science are expected to be valuable as well. Your regular participation in discussions of all kinds will be expected.
