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”)