You're reading: cp's mathem-o-blog, Videos

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!

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 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’ []

Leave a Reply

  • (will not be published)

$\LaTeX$: You can use LaTeX in your comments. e.g. $ e^{\pi i} $ for inline maths; \[ e^{\pi i} \] for display-mode (on its own line) maths.

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>