# Cardboard SKI calculus

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.

#### Ingredients:

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 three1 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!

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 useful2 programs in!

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