Today I Learned

Some of the things I've learned every day since Oct 10, 2016

49: Church Numerals

In Church encoding, an encoding system using lambda calculus, the Church numerals are the representation of the natural numbers. The distinguishing feature of the Church numerals is that the natural numbers are not treated as a primitive type, as they would typically be, but are simply represented by higher-order functions. Each higher-order function \boldsymbol{n} representing the number n takes two arguments — a function f and a second argument to be passed to f — and returns the n-fold composition of f.

Examples:

0 is represented as \boldsymbol{0} = \lambda f . \lambda x . x, which given any function f returns a function which simply returns x without applying f at all.

1 is represented as \boldsymbol{1} = \lambda f . \lambda x . f x, which given any function f returns a function which applies f once to x.

2 is represented as \boldsymbol{2} = \lambda f . \lambda x . f (f x), which given any function f returns a function which applies f twice to x.

3 is represented as \boldsymbol{3} = \lambda f . \lambda x . f (f (f x)), which given any function f returns a function which applies f three times to x.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: