X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=topics%2Fweek3_what_is_computation.mdwn;h=48d231dd4d222048b5d810500ad66de0d4526417;hp=0c9c5c5431a09124fabcf1b9ec1869a283dd5e59;hb=41ff76222e4686a052961903d371afe635fe4f58;hpb=63156a22b401c0fdbe7a6b98ac0e402977ec8a5b diff --git a/topics/week3_what_is_computation.mdwn b/topics/week3_what_is_computation.mdwn index 0c9c5c54..48d231dd 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 "omega", or sometimes **M**; and its self-application `ω ω`, displayed above, is called (big) Ω or "Omega".) + +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