Mathematical logic
Set theory
Order theory
Formal language theory
Enumerative combinatorics
Automata theory


\chapter{Decidability}
\section{Decidable language}

$M$ decides $\mathcal{L}$ iff $M$ accepts $w$ iff $w \in \mathcal{L}$ and $M$ rejects $w$ iff $w \notin \mathcal{L}$


The most immediately interesting automata to study decidability for are Turing machines.

Halting problem
Rice's theorem
- undecidable languages
- mapping reducibility
- Turing machine property
- Rice's theorem
- Rice's theorem

\chapter{Reducibility}

\chapter{Computable functions}

\section{Computable numbers}

\[ \frac{f(n)-1}{n} \leq c \leq \frac{f(n)+1}{n} \]