SU-CS242 SEP262024

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