Overview

This is a copy of the draft book written by the late James Arvo for CalTech/UCI courses on Theory of Computation.

Chapters

• Chapter 1: Introduction
• Chapter 2: Mathematical Preliminaries
• Chapter 3: Recursive Functions
• Chapter 4: Alphabets, Strings, and Languages
• Chapter 5: Finite Automata
• Chapter 6: Grammars and Pushdown Automata
• Chapter 7: Turing Machines
• Chapter 8: Undecidability
• Chapter 9/10: The Theory of NP-Completeness

Legal

I'm somewhat oblivious to the legal implications of distributing an unpublished copy of a draft book. I'll just leave it at that.