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