1 month ago
source link: https://wiki.xxiivv.com/site/logic.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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.

Mockingbirdx x y zDuplicates the first word
Kitey zDiscards the first word
Thrushy x zSwaps 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)
Warblerx y y zDuplicates the second word
Kestrelx zDiscards the second word
Cardinalx z ySwaps the second and third words
Bluebirdx (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
IdiotxxReturns its word
Starlingxyzxz (y z)Returns x(z) applied to y(z).


Some birds can replicate the behaviors of others:


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.


Reference of combinator birds.

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

λabcdefg.a(bcd)(efg)ÊBald EagleB(BBB)(B(BBB))
λab.aKKestrel (True)
λab.bKIKite (False)KI
λab.ab(ab)M2Double MockingbirdBM
λabc.b(ac)QQueer BirdCB
λabc.a(cb)Q1Quixotic BirdBCB
λabc.b(ca)Q2Quizzical BirdC(BCB)
λabc.c(ab)Q3Quirky BirdBT
λabc.c(ba)Q4Quacky BirdF*B
λabc.cabVVireo (aka Pairing)BCT
λab.baaW1Converse WarblerCW
λa.a(λa)YWhy Bird (aka Sage Bird)SLL
λab.abI*Identity Bird Once RemovedS(SK)
λabc.abccW*Warbler Once RemovedBW
λabcd.abdcC*Cardinal Once RemovedBC
λabcd.acdbR*Robin Once RemovedC*C*
λabcd.adcbF*Finch Once RemovedBC*R*
λabcd.acbdV*Vireo Once RemovedC*F*
λabc.abcI**Identity Bird Twice Removed 
λabcd.abcddW**Warbler Twice RemovedB(BW)
λabcde.abcedC**Cardinal Twice RemovedBC*
λabcde.abdecR**Robin Twice RemovedBR*
λabcde.abedcF**Finch Twice RemovedBF*
λabcde.abecdV**Vireo Twice RemovedBV*
λab.bbKMKonstant MockerKM
λab.aaC(KM)Crossed Konstant MockerC(KM)

Incoming: forth thue 2022

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

About Joyk

Aggregate valuable and interesting links.
Joyk means Joy of geeK