## 116b- Lecture 3

We defined Ackermann’s function and showed it is not primitive recursive. We showed that $\Delta_0$-formulas have a primitive recursive characteristic function, and defined the class ${\sf R}$ of recursive functions.