Church numerals

Church numerals adalah pengkodean bilangan bulat non-negatif menggunakan lambda terms. Church mendefinisikan Church numeral C_n untuk sembarang n=0,1,2,\dots sebagai berikut.

C_n = \lambda xy.x^ny = \lambda xy.x(x(x(\dots x(xy))\dots)).

Dengan menggunakan definisi C_n, ini kita dapat membuat lambda term untuk fungsi penjumlahan. Jika A merupakan fungsi tersebut, maka akan berlaku

A C_mC_n = C_{m+n} untuk sembarang m,n \ge 0.

Lambda term yang sesuai dengan definisi fungsi A ini adalah:

A=xypq.xp(ypq).

Akan ditunjukkan bahwa A memenuhi. Perhatikan bahwa

AC_mC_n =(\lambda xypq.xp(ypq))C_mC_n

= \lambda pq.C_m p (C_n p q)

= \lambda pq. C_m p ((\lambda xy.x^ny) p q)

=\lambda pq.C_m p (p^nq)

=\lambda pq.(\lambda xy.x^m y)p (p^n q)

=\lambda pq.(p^m (p^n q))

=\lambda pq.p^{m+n}q

=C_{m+n}

sehingga terpenuhi… (bersambung)

Advertisements
This entry was posted in Uncategorized and tagged , , , , , . Bookmark the permalink.

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