Reduction = computation.
Example:
(λx. x) 4 → 4
The function returns its input.
Another example:
(λx. x + 2) 5 → 5 + 2 → 7
Normal form = cannot be reduced anymore.
Example (NOT normal):
(λx. x) 7 → can still reduce → not normal
Example (Normal):
λx. x → nothing to reduce → normal form
Two expressions are convertible if they reduce to the same result.
Example:
(λx. x) 5 → 5
So:
(λx. x) 5 = 5
Some expressions never stop.
(λx. x x)(λx. x x)
This keeps reducing to itself forever → no normal form.
Q1: Reduce (λx. x) 4
Q2: Reduce (λx. x + 2) 5
Q3: Reduce (λx. x) ((λy. y) 3)
Q4: Is (λx. x) 7 in normal form?
Q5: Is λx. x in normal form?
Q6: Are (λx. x) 5 and 5 convertible?
Q7: Does (λx. x x)(λx. x x) ever stop?