1

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.

cmal
  • 135
  • Here's a tutorial for how to typeset math on this site: https://math.meta.stackexchange.com/questions/5020. (Allows you to have proper symbols like $\lambda$ and $\Omega$.) – joriki Jul 03 '18 at 07:59

1 Answers1

1

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 to Give 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".

joriki
  • 238,052