# SK numerals

--

# Church Numerals

Church numerals are the standard way of representing natural numbers in the lambda calculus. Cn, the Church numeral for n, iterates a given function n times on a given argument. So we have

`C0 f x = f⁰ x = x`

C1 f x = f¹ x = f x

C2 f x = f² x = f (f x)

etcetera. We can define a successor function “Csucc” which iterates a given function one more time than a given numeral does:

`Csucc = λn.λf.λx. f (n f x)`

(λn.λf.λx. n f (f x) works equally well). Each Church numeral Cn is thus itself the n’th iterate of Csucc on C0:

`Cn = Cn Csucc C0`

The best thing about Church numerals is the ease of defining arithmetic operators. It is straightforward to verify that

`add = λm.λn.λf.λx. m f (n f x)`

mul = λm.λn.λf. m (n f)

pow = λm.λn. n m

work as advertised.

E.g. pow C2 C3 = C3 C2 = λf. C2 (C2 (C2 f)) = λf.((f²)²)² = λf.f⁸ = C8

Much less straightforward is the predecessor operator, that takes C(n+1) to Cn and leaves C0 unchanged:

`Cpred = λn.λf.λx. n(λg.λh. h(g f))(λu. x)(λu. u)`

Wikipedia tries to explain its operation in detail.

Even less straightforward is the following division operator that springs from the creative mind of Bertram Felgenhauer:

`div = λn.λm.λf.λx.n(λx.λf.f x)(λd.x)(n (λt.m(λx.λf.f x)(λc.f(c t))(λx.x))x)`

whose operation is illustrated in this Algorithmic Information Theory github repository.

# SK Combinatory Logic

Combinatory Logic is concerned with terms consisting of the 2 basic combinators

`S = λx.λy.λz. x z (y z)`

K = λx.λy. x

combined through application. It turns out that any closed lambda term is equivalent to a combinator. For example, the identity combinator can be obtained as

`I = S K K`

since I x = S K K x = K x (K x) = x.

While reading Stephen Wolfram’s latest book, I came across an interesting alternative to Church numerals for Combinatory Logic:

`F0 = K`

F1 = S K

F2 = S (S K)

F3 = S ( S (S K)))

etcetera, so S iterated n times on K, or Fn = Cn S K.

This takes economy to an extreme, by using the 2 primitive combinators S and K as the very building blocks of numbers:

`F0 = K`

Fsucc = S

We have

`F0 x y = x`

F(n+1) x y = S Fn x y = Fn y (x y)

so that

`F1 x y = y`

F2 x y = x y

F3 x y = y (x y)

F4 x y = x y (y (x y))

etcetera, which can be shown by induction so satisfy the Fibonacci recurrence

`F(n+2) x y = (Fn x y) (F(n+1) x y)`

with sum replaced by application! Consequently, there are exactly fib(n) occurrences of variable y in Fn x y.

In honor of this close connection we denote these SK numerals with the letter F . Curiously, F0 and F1 coincide with the standard representations of booleans

`True = K`

False = S K

The big question, though, is whether they work as numerals. The ultimate test of that is the ability to convert them back into Church numerals. Wolfram’s book suggests a way to do that by applying an SK numeral to x and y that are both Church numerals, perhaps C3 and C2, which leads to all applications working as powers. For example, F3 C3 C2 = C2 (C3 C2) = C2 C8 = C256. And from that we could work our way back to the 3, resulting in a size 181 conversion combinator.

A more elegant conversion can be obtained by defining predecessor and iszero operators, and using these to count down to zero

`Fpred = λn.λx.λy. n (K y) x`

Fiszero = λn. n False I S K

F2C = λn. Fiszero n C0 (Csucc (F2C (pred n)))

We may check that

`Fpred F1 x y = F1 (K y) x = x`

Fpred F2 x y = F2 (K y) x = K y x = y

and by induction, Fpred F(n+1) = Fn holds for all n. In fact, it works so well, it lets us venture into the negative numbers:

`F-1 x y = Fpred F0 x y = F0 (K y) x = K y`

F-2 x y = Fpred F-1 x y = F-1 (K y) x = K x

F-3 x y = Fpred F-2 x y = F-2 (K y) x = K (K y)

etcetera. And Fsucc works on these negative numerals too.

Fiszero however works on non-negative numerals only, as follows:

`Fiszero F0 = F0 False I S K = False S K = K = True`

Fiszero F(n+1) False I S K = S Fn False I S K = Fn I I S K = I S K = S K = False

Using the optimal Y combinator S S K (S (K (S S (S (S S K)))) K), F2C is combinator of size 69, a huge improvement.

But it turns out we can do better still, courtesy of good old Bertram:

`pair = λx.λy. λp. p x y`

F2C = λn.(λp. n p(p p) False) (pair (λf.λy.λx. pair f (Csucc y)) C0)

This size 60 combinator

`S (S (K (S S (K (K (S K))))) (S S (S K))) (K (S (S (S K K) (K (S (K (S (K (S (K (S (K (S (K (S (K (S S (K (S (K (S (K (S (K K))) S)) (S (K (S (K S) K))))))) K)) S)) K)) S)) (S (S K K)))) K))) (S K)))`

applies the SK numeral to x and y that are both pairs of some function and a church numeral. Applying one such pair to another results in the function applied to itself and the two numerals:

`(pair f Cm) (pair f Cn) = (pair f Cn) f Cm = f f Cn Cm`

so all function f has to do is take the successor of the right Church numeral and wrap it back up into a pair. In the F2C definition above, p is a wrapped C0 and (p p) becomes a wrapped C1.

And that wraps us our brief exploration of SK numerals.