**Infinite Loop**

Let us define a term (abstraction) like the following:

*T = λx.x x*

What if we try to evaluate the application

*T T*, let us see:

*T T → (λx.x x) (λx.x x) → (x x) [x := λx.x x]*

*→*

*(λx.x x) (λx.x x)*

*→*

*T T*

As you see, if we try to get the result of this application we get the application itself, in fact, it is kind of an infinite loop,

*T T*is kind of self-applications which usually lead to recursion. This kind of infinite loop is shown by Ω symbol, so you may say that:

*Ω = (λx.x x) (λx.x x)*

**Finite Loop**

OK, we saw that

*T T*represents a recursion but it can be also interpreted as an infinite loop. As we have seen in programming since we have a logical comparison, we can easily define applications which do have some form of

*T T*but with some controlled counter as passed argument we can not let he recursion continues forever.

The typical simple recursive application is the calculation of n! let's name this function

*f.*Before writing the application, remember how we had an if statement in lambda calculus:

*λpxy.p x y*

Which means "if (p == 0) then x else y", now let us see how we can write a factorial abstraction:

*f =*

*λn.(*

*λnxy.(n-1) 1 (n * (f) n-1))*

It seems a bit complex, but it is not. First remember we assumed before that we use infix notation for mathematical expressions, so

*n-1*means

*- n 1*.

*f*is an abstraction if you use it as an application it accepts one argument

*n*and calculates the factorial of it. It first evaluates

*(n-1)*and if finds it zero returns 1 otherwise calls

*f*with

*n-1*and multiplies the result to n and returns it

*,*sounds right, no? By

*(f) n-1*we mean function application that accepts

*n-1*as its argument.

Now suppose we want to calculate 3! we have:

*(λn.(λnxy.(n-1) 1 (n * (f) n-1))) 3 →*

*3 * (λn.(λnxy.(n-1) 1 (n * (f) n-1))) 2 →*

*3 * 2 * (λn.(λnxy.(n-1) 1 (n * (f) n-1))) 1 →*

*3 * 2 * 1 = 6*

## No comments:

## Post a comment