X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=topics%2Fweek3_what_is_computation.mdwn;h=b5c9d5ba265aa1113fda8c398d5dc5a270822272;hp=0c9c5c5431a09124fabcf1b9ec1869a283dd5e59;hb=78cfc3595320d328af3892701b8ba7973a1538e3;hpb=63156a22b401c0fdbe7a6b98ac0e402977ec8a5b 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