This course has two primary objectives. The first is content-based. We
hope to teach students the fundamental concepts of formal language
theory and computability theory. In formal language theory, we study
languages from several different viewpoints and prove general
properties about various types of formal languages. This is a critical
area of study as we need to understand what types of languages
computers will be able to understand. In computability theory, we
construct general models of computation and explore the fundamental
capabilities and limitations of digital computers. This is a critical
field of study as we learn there are important practical problems we
can never expect computers to solve for us.
The second objective is skill-based. In CPS 260, you are taught
some basic skills such as how to prove theorems. In this course, we
hope to teach you how to apply these skills in "real-life"
situations. Furthermore, we hope to teach you the importance of a
careful, methodical approach to the construction of proofs and
algorithms.