MAIN IDEA: Combinator Calculus

## primitive recursion vs general recursion

primitive recursion is a form of recursion whereby you don’t get to modify the amount of recursion after the loop is defined. general recursion have control flow.

## non-termination

all forms of general recursion either

## rewrite system

- \(\to\) is a single rewrite
- \(\to^{*}\) stands for the reflexive, transitive closure of \(\to\) (i.e. zero or more rewrites—“we skipped the middle”)