Logic

XXIIVV — logic

A certain enchanted forest is inhabited by talking birds.

Combinatory logic demonstrates that even without anything as crude as digits and operators, arithmetic and computation can emerge. Combinatory Forests are inhabited by talking birds, which speak words delimited by parentheses. We always listen to the left-most bird first.

T▲(◆●) • ◆●▲C(WK)x(yz)

▲ The Bekimet Forest

Within the Bekimet forest, we find the B, KI, M, and T birds. Each bird listens to a message, and answers with another. The first bird that we observe is the Mockingbird, which repeats the first word.

M▲◆● • ▲▲◆●W(WK)xyz

The second bird that we observe is the Kite, which omits the first word.

KI▲◆● • ◆●K(WK)xyz

The third bird that we observe is the Thrush, which swaps the first and second words.

T▲◆● • ◆▲●C(WK)xyz

We can't quite make out the fourth bird, but we observe that it is the Bluebird, which is also found in the next forest, so let's continue.

Mockingbird	x x y z	Duplicates the first word
Kite	y z	Discards the first word
Thrush	y x z	Swaps the first and second words

◆ The Becekew Forest

Within the Becekew forest, we find the B, C, K, and W birds. The first bird that we observe is the Warbler, which repeats the second word. This bird's song is similar to the Mockingbird, which repeats the first word.

W▲◆● • ▲◆◆●Wxyz

The second bird that we hear is the Kestrel, which omits the second word. This bird's song is similar to the Kite, which omits the first word. Here is the Kestrel, followed by the Warbler:

KW▲◆● • W◆● • ◆●●KWxyz

The third bird that we hear is the Cardinal, which swaps the second and third words. This bird's song is similar to the Thrush, which swaps the first and second words. Here is the Cardinal, followed by the Kestrel:

CK▲◆● • K◆▲● • ◆●CKxyz

The elusive Bluebird takes three words, and parenthesizes the third word into the second word.

B▲(◆◆)(●●) • ▲(◆◆(●●)) Bx(yy)(zz)

Warbler	x y y z	Duplicates the second word
Kestrel	x z	Discards the second word
Cardinal	x z y	Swaps the second and third words
Bluebird	x (y z)	Composition of x and y applied to z

● The Sekei Forest

Within the Sekei forest, we find the S, K, and I birds. The simplest of these birds, appears to have no intelligence at all, and so it is called the Idiot bird since its response to hearing any word, is that same word.

I(▲◆) • (▲◆) (WK)(xy)

The Kestrel is also found in this forest, but we're already familiar with this one. Let's take a moment to see how words can be grouped by parentheses and transformed as if they were a single word. For instance, the Kestrel omits the second group of parenthesized words:

K▲(◆◆)(●●) • ▲(●●) Kx(yy)(zz)

The Starling does parenthesising, reordering, and duplication. Applied to three combinators, it applies each of the first two combinators to the last, then applies the first result of that to the second:

S▲◆● • ▲(●)(◆(●)) B(B(BW)C)(BB)xyz

Idiot	x	x	Returns its word
Starling	xyz	xz (y z)	Returns x(z) applied to y(z).

Conversion

Some birds can replicate the behaviors of others:

Bekimet-Becekew	Becekew-Sekei	Sekei-Becekew
KI	K(WK)	B	S(KS)K	S	B(B(BW)C)(B B)
M	W(WK)	C	S(S(K(S(KS)K))S)(KK)	K	K
T	C(WK)	K	K	I	WK
	W	SS(SK)

Continue deeper into the forest. To see a list of famous birds, see the Birdwatching Manual.

The Ornithomicon is the infamous grimoire of Avian Arithmetic.

Before progressing deeper into the enchanted forest, you should be familiar with the 9 birds of the Bekimet, Becekew and Sekei forests.

Avian Booleans

The Kestrel takes two words and always selects the first, this is the Avian Binary for True:

K▲◆ • ▲Kxy

The Kite takes two words and always selects the second, this is the Avian Binary for False:

KI▲◆ • ◆KIxy

Avian Bitwise

The Cardinal takes two words and flips them, this is the Avian Bitwise for NOT:

C(KI▲◆) • ▲C(Kxy)

The Mockingbird takes 2 booleans and returns True if at least one of them is True, this is the Avian Bitwise for OR:

M(KI)(K)▲◆ • ▲W(WK)(KI)(K)xy

To return True, when both words are True, we use a combination of Starlings and a Kestrel to create AND:

SSK(KI)(K)▲◆ • ◆SSK(KI)(K)xy

Since True selects the first of 2 words, and False selects the second, we need a way to pass the second and third words to the first one. Therefore, the Idiotbird is the equivalent to the Avian Binary for IfThenElse:

I(KI)▲◆ • ◆I(KI)xy

Avian-Human Numerals

The Kite is the both the boolean False, and the number zero, the Idiotbird is the number 1. These are the Church Encoded numerals, which talking birds only use to communicate numbers to humans who enter the forest.

0	KIfx	x	5	SB(B(WB)(WB))fx	..
1	Ifx	fx	6	B(WB)(SB(WB))fx	..
2	WBfx	f(fx)	7	SB(B(WB)(SB(WB)))fx	..
3	SB(WB)fx	f(f(fx))	8	B(WB)(B(WB)(WB))fx	..
4	B(WB)(WB)fx	f(f(f(fx)))	9	SB(B(WB)(B(WB)(WB)))fx	..

Reference of combinator birds.

Color-coded for the Bekimet, Becekew and Sekei forests.

Abstraction	Symbol	Bird	Combinator
λabc.a(bc)	B	Bluebird	S(KS)K
λabcd.a(bcd)	B1	Blackbird	BBB
λabcde.a(bcde)	B2	Bunting	B(BBB)B
λabcd.a(b(cd))	B3	Becard	B(BB)B
λabc.acb	C	Cardinal	S(BBS)(KK)
λabcd.ab(cd)	D	Dove	BB
λabcde.abc(de)	D1	Dickcissel	B(BB)
λabcde.a(bc)(de)	D2	Dovekies	BB(BB)
λabcde.ab(cde)	E	Eagle	B(BBB)
λabcdefg.a(bcd)(efg)	Ê	Bald Eagle	B(BBB)(B(BBB))
λabc.cba	F	Finch	ETTET
λabcd.ad(bc)	G	Goldfinch	BBC
λabc.abcb	H	Hummingbird	BW(BC)
λa.a	I	Idiot(Identity)	SKK
λabcd.ab(adc)	J	Jay	B(BC)(W(BC(B(BBB))))
λab.a	K	Kestrel (True)
λab.b	KI	Kite (False)	KI
λab.a(bb)	L	Lark	CBM
λa.aa	M	Mockingbird	SII
λab.ab(ab)	M2	Double Mockingbird	BM
λab.b(ab)	O	Owl	SI
λabc.b(ac)	Q	Queer Bird	CB
λabc.a(cb)	Q1	Quixotic Bird	BCB
λabc.b(ca)	Q2	Quizzical Bird	C(BCB)
λabc.c(ab)	Q3	Quirky Bird	BT
λabc.c(ba)	Q4	Quacky Bird	F*B
λabc.bca	R	Robin	BBT
λabc.ac(bc)	S	Starling	S
λab.ba	T	Thrush	CI
λab.b(aab)	U	Turing	LO
λabc.cab	V	Vireo (aka Pairing)	BCT
λab.abb	W	Warbler	C(BMR)
λab.baa	W1	Converse Warbler	CW
λa.a(λa)	Y	Why Bird (aka Sage Bird)	SLL
λab.ab	I*	Identity Bird Once Removed	S(SK)
λabc.abcc	W*	Warbler Once Removed	BW
λabcd.abdc	C*	Cardinal Once Removed	BC
λabcd.acdb	R*	Robin Once Removed	C*C*
λabcd.adcb	F*	Finch Once Removed	BC*R*
λabcd.acbd	V*	Vireo Once Removed	C*F*
λabc.abc	I**	Identity Bird Twice Removed
λabcd.abcdd	W**	Warbler Twice Removed	B(BW)
λabcde.abced	C**	Cardinal Twice Removed	BC*
λabcde.abdec	R**	Robin Twice Removed	BR*
λabcde.abedc	F**	Finch Twice Removed	BF*
λabcde.abecd	V**	Vireo Twice Removed	BV*
λab.bb	KM	Konstant Mocker	KM
λab.aa	C(KM)	Crossed Konstant Mocker	C(KM)

Incoming: forth thue 2022

Devine Lu Linvega © 2022 — BY-NC-SA 4.0