I had a spare day yesterday so, rather than clean my house, I made a model of the *SKI* combinator calculus out of a pizza box.

[youtube url=http://www.youtube.com/watch?v=fZQMmgElRMI]

#### Ingredients:

- this sheet of combinator tiles
- some cardboard (I used an old pizza box, which was a terrible, smelly idea)
- glue
- blu-tack
- a quick read of the Wikipedia page on the SKI calculus

You’ve almost definitely heard of Turing machines and Turing completeness. You *might* have heard of the *λ*-calculus, which was invented by Alonzo Church around the same time as Turing was thinking about machines, and has exactly the same computing power (the Church-Turing thesis!) but looks very different. *λ*-calculus deals purely with functions and function application, in a very abstract algebraic way, so unlike with Turing machines it’s very hard to fix in your head a physical model of how computations happen.

The *SKI* calculus boils *λ*-calculus down to just three operations, or *combinators*. Those three^{1} are enough to recreate every expression you can create with *λ*-calculus. I’ve been meaning to get my head round it for a while, but implementing it on a computer wasn’t very enlightening.

So I had a brainwave recently, which was that I could make tiles representing the combinators, and the way they fit together would dictate how they act. I just about worked out something reasonable yesterday, which is why I decided to record a video. I hope you found it interesting!

#### Further reading:

A nice page by Mike O’Donnell introducing the SKI calculus and explaining why it’s so great.

A browser-based SKI expression evaluator (it uses a different notation to the one I used in the video)

Lazy K, an SKI-based programming language you can use to write actual useful^{2} programs in!

- in fact you only need
*S*and*K*or, if you’re really Zen, you can create a single combinator which does everything [↩] - subject to your definition of the word ‘useful’ [↩]