The Loom

Mathematical Markings

The Y Combinator.jpg
Mark sent this picture in, with this explanation:

I don’t quite have a science tattoo, but I have a math tattoo. That’s close enough, right?

Now, for the explanation. This is a formula called the Y Combinator. It is a fixed-point combinator in the lambda calculus and was discovered by Haskell Curry, a rather prolific mathematician and logician whose work helped start Computer Science.

What this formula does is calculates the fixed point of a function, which in turn allows for recursion by calling on that fixed point; recursion is perhaps the single most important concept in Computer Science. Being a computer scientist and a mathematician, this formula is very important to me and represents the innate beauty of computer science and mathematical logic.

Four more tattoos added to the Flickr set this week, each with its own story. Check them all out.

Update 9/21 8:30 am: Ouch. jwz hints that Mark forgot a parenthesis. Any comment from math folks out there?

Update, 1:50 pm: Mark says his parentheses are all in order, thank you.


  1. #1 Paul Donnelly
    September 21, 2007

    I got a real kick out of this one, since I’ve finally settled on the Y combinator after trying to think up a Lisp-themed tattoo. I figure it will match the summation I’ve already got nicely. After that, only 22 letters to go, right?

  2. #2 csrster
    September 21, 2007

    Right. But you don’t want to come out of the tattoo parlour and find one of those parentheses missing.

  3. #3 Nathan
    September 21, 2007

    The parens look fine to me :-)

  4. #4 gabeybaby
    September 21, 2007

    ya, that parans look fine to me too. when i visited jwz’s site they’re counting parans with their fingers. Maybe that should have been a clue in itself. ;)

  5. #5 K
    September 21, 2007

    I think JWZ was joking.

  6. #6 Melissa
    September 21, 2007

    It isn’t a math tatoo, it’s a computer science tatoo! (You could argue that it’s math too, of course, but it is much more central to CS — for example, it is way more likely to be covered in a typical undergraduate CS curriculum than by a typical undergraduate math curriculum.)

    Real computer science isn’t programming trade skills, big chunks are cool theory like this.

    If you want to mystify people with cool combinator stuff they probably won’t understand, then you should really write fixed-point combinator write in terms of more primitive combinators. For example, you could say Y = S (K (S I I)) (S (S (K S) K) (K (S I I))) using only the classic S, K, and I, or confuse everyone with John Tromp’s shorter fixed-point combinator using only S and K, S S K (S (K (S S (S (S S K)))) K). But my own short and sweet favorite is Y = C’ (B (S I I)) B (S I I)).

    More at <>.

  7. #7 Mark
    September 21, 2007

    Oh, the parens are correct. I agonised over my tattoo for several weeks after I got it making sure everything was correct. By the way, I am the canvas.

    Re: Melissa. Well, it’s quite easy and quite correct to say that CS is more a branch of mathematics than anything else. So, yes, it is central to CS which in turn makes it a part of mathematics.

    As far as confusing and hilarious fixed-point combinators, I’m a fan of Jan Klop’s comibinator:
    Y = (L L L L L L L L L L L L L L L L L L L L L L L L L L), where L = λabcdefghijklmnopqstuvwxyzr. (r (t h i s i s a f i x e d p o i n t c o m b i n a t o r))

  8. #8 Martin DeMello
    September 21, 2007

    Were I to get a lisp tattoo, I’d probably opt for the mind-hurting ((call/cc call/cc) (call/cc call/cc))

  9. #9 Mark
    September 21, 2007

    Re: Martin. You just described the Lisp implementation of a infamous divergent combinator called the omega combinator. If I remember correctly, that is actually what Alonzo Church used in his paper on the Entscheidungsproblem.

  10. #10 Martin DeMello
    September 21, 2007

    Thanks, Mark! I saw that code snippet in a usenet post years ago, and it twisted my brain into a very strange shape by the time I figured it out :) Didn’t know it had a name, or that there was history behind it – will have to go look up the Church paper.

  11. #11 Stup
    September 21, 2007

    Combinators “eliminate the need for variables”? Can this be an alternative to arrays? I compared a few array-less solutions with typical non-array-less ones, and the array-less solutions were faster (surprisingly). I did this after learning that memory and time are the two basic hindrances. Also, tattoos are dumb.

  12. #12 Alan Kellogg
    September 22, 2007

    Speaking as a one time editor (used to translate Gygax into English), I can confirm that the parenthesis in that equation are all properly closed.

  13. #13 kai
    September 23, 2007

    How do the characters come out so even, does the tattooist use some kind of template, did Mark stick his arm in a needle matrix printer?

  14. #14 Paul Donnelly
    September 24, 2007

    Kai, presumably the tattoo artist drew it on paper with guides lines first, transferred it over, then traced with the needle. I suppose it’s possible that the original was a printout too.

  15. #15 Alexander Fairley
    September 24, 2007

    This seems like rather extreme lengths to go to, just to cheat on your lambda calculus exam.

  16. #16 ruidh
    September 24, 2007

    I just wonder what classes he can’t take because he would be accused of cheating on the final exam. (Yeah, I know, he’s probably *teaching* those classes.)

  17. #17 Isabel
    September 25, 2007

    ruidh: I’d also argue that if he is taking those classes, he almost deserves to get a good grade just because he finds the material so compelling that he was willing to get it inked on him quasi-permanently. (This assumes, of course, that tattoo removal is painful and expensive; if it were cheap and painless one would have to look at this differently.)

  18. #18 den
    December 31, 2007

    This seems like rather extreme lengths to go to, just to cheat on your lambda calculus exam.

  19. #19 Site Ekle
    January 5, 2008

    I can confirm that the parenthesis in that equation are all properly closed.