## Welcome to SI342 - Theory of Computing

Computer Science is no more about computers than astronomy is about telescopes
— Edsger Dijkstra
The Theory of Computing is the theoretical backbone of Computer Science. Like any other science, Computer Science has
its fundamental question. The fundamental question of Computer science is: What is computation, and what can
be computed.

This is the question we will answer by the end of the course.

To do that, we will need to learn about formal languages, finite state machines, pushdown automata,
Turing machines and computability.

We will also — in parallel with learning the Theory of Computing — cover the mathematics that the Theory of
Computing leans on. In particular, we will discuss the set theory, first-order logic, and functions.

A new, a vast, and a powerful language is developed for the future use of analysis, in which to wield its truths so
that these may become of more speedy and accurate practical application for the purposes of mankind than the means
hitherto in our possession have rendered possible.
— Augusta Ada King, Countess of Lovelace
Enjoy!

#### Instructors:

**Dr. Alex Timcenko
(timcenko@usna.edu )**

**Mark Woodcock
(woodcock@usna.edu)**

For general information about the course, take a look at the
Course Policy