# Interactive Computer Science

Avik Das## Table of Contents

- What is a computional problem?
- Computational problems
- Alphabets and strings
- String encodings
- Languages
- Programs can solve (some) problems
- SISO Python programs
- Programs that analyze other programs
- Impossible programs
- Turing machines are a model of computation
- 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.