From 78cfc3595320d328af3892701b8ba7973a1538e3 Mon Sep 17 00:00:00 2001 From: jim Date: Sat, 14 Feb 2015 17:53:32 -0500 Subject: [PATCH] add names for omega and Omega --- topics/week3_what_is_computation.mdwn | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/topics/week3_what_is_computation.mdwn b/topics/week3_what_is_computation.mdwn index 0c9c5c54..b5c9d5ba 100644 --- a/topics/week3_what_is_computation.mdwn +++ b/topics/week3_what_is_computation.mdwn @@ -135,11 +135,13 @@ pathological examples where the results do not align so well: (\x. x x) (\x. x x) ~~> (\x. x x) (\x. x x) ~~> (\x. x x) (\x. x x) ~~> ... In this example, reduction returns the exact same lambda term. There -is no simplification at all. +is no simplification at all. (As we mentioned in class, the term `(\x. x x)` is often referred to in these discussions as (little) ω, or sometimes **M**; and its self-application ω ω, displayed above, is called (big) Ω.) + +Even worse, consider this term: (\x. x x x) (\x. x x x) ~~> (\x. x x x) (\x. x x x) (\x. x x x) ~~> ... -Even worse, in this case, the "reduced" form is longer and more +Here, the "reduced" form is longer and more complex by any reasonable measure. We may have to settle for the idea that a well-chosen reduction system -- 2.11.0