Interactive Computer Science

Table of Contents

1. What is a computional problem?
1. Computational problems
2. Alphabets and strings
3. String encodings
4. Languages
2. Programs can solve (some) problems
1. SISO Python programs
2. Programs that analyze other programs
3. Impossible programs
3. Turing machines are a model of computation

---

4. WIP: Finite automata

Introduction

An introductory course in Theoretical Computer Science, built for the modern, interactive world. The topic of Theoretical Computer Science gets to the bottom of what it means for a computer to do something. It turns out there are many ways to formalize the concept of computation. What's surprising, however, is how quickly we run into fundamental limits!

Goals & audience

This book and its associated resources are based on my experience teaching students the subject. There are plenty of classic books on the topic, so this book is not for everybody. My goals are:

• Make the subject truly interactive. Not only does this promote understanding of key concepts, I can scale the class by providing quick feedback without me present.

• Walk students through how to learn higher math. Ideally, students should have ample experience by the time they get to this course. But this doesn't always happen. The styling, structure and the interactivity in this book is designed to promote a more engaged approach from the ground up. As a simple example, definitions are emphasized visually and followed by an interactive example that forces students to understand the definition before moving on.