AutomataAndComputability

The goal of this course is to understand the foundations of computation. We will ask some very basic questions, such as • What does it mean for a function to be computable?
• Are there any noncomputable functions?
• How does computational power depend on programming constructs?
These questions may appear simple, but they are not. They have intrigued scientists for decades, and the subject is still far from closed. In the quest for answers to these questions, we will encounter some fundamental and pervasive concepts along the way: state, transition, nondeterminism, redu.ction, and u.ndecidability, to name a few. Some of the most important achievements in theoretical computer science have been the crystallization of these concepts. They have shown a remarkable persistence, even as technology changes from day to day. They are crucial for every good computer scientist to know, so that they can be recognized when they are encountered, as they surely will be.