On this wikipedia article, there is an explanation of lambda calculus.
In the section of Beta reduction
, there is an Omega
example, which says Omega = (lambda x.xx)(lambda x.xx)
, which
reduces to itself in a single beta reduction, and therefore the
reduction process will never terminate.
At first, I thought the (lambda x.xx)
means a function f(x) = x * x
, but it seems the two (lambda x.xx)
s in definition of Omega
means an application
. If it can reduce to itself, does that mean the xx
in (lambda x.xx)
actually is an application
? So the first lambda term in the definition of Omega
actually means: Give me something and I will apply it to itself ? So the Omega
means:
Give me Give me something and I will apply it to itself
and I will apply it to itself, so it will reduce to:
Apply Give me something and I will apply it to itself
to Give me something and I will apply it to itself
,
and so it will becomes:
Give me Give me something and I will apply it to itself
and I will apply it to itself.
That is the first process again, so never terminate.
Am I right?
If I am, I am wondering why this (lambda x.xx)
term was not written as (lambda x.(xx))
so it will be clearer.
Best Answer
The first part of your thoughts is right. What isn't quite right is where you say that $\Omega$ means "Give me ...". The things that start with "Give me" are the $\lambda$ expressions. $\Omega=(\lambda x.xx)(\lambda x.xx)$ isn't a lambda expression, it's an application (just as $xx$ is, as you rightly deduced). It's the application of
Give me something and I will apply it to itself
toGive me something and I will apply it to itself
(that is, to itself). This application reduces to itself.On your question about why the application isn't enclosed in parentheses, the notation section of the Wikipedia article says that this is done "to keep the notation of lambda expressions uncluttered".