Revisiting “On editing text”

2014-06-19 § 1 Comment

This document is an incomplete draft.

About two years ago I wrote about a category-theoretic treatment of collaborative text editing. That post is unique in the history of Bosker Blog in having been cited – twice so far that I know of – in the academic literature; so it’s a little embarrassing for me to have to explain that it is almost entirely wrong. The good news is that the core idea can be rescued, and the corrected story is quite interesting. Other writers on this subject seem to have made at least some of the same mistakes I did, so I hope this will be useful to at least a few other people too. « Read the rest of this entry »

Decoding the mysterious symmetry of the bicycle lock numbers

2014-02-25 § Leave a comment

Suppose you have a lock of this sort bicycle lock that has n dials and k numbers on each dial. Let m(nk) be the minimum number of turns that always suffice to open the lock from any starting position, where a turn consists of rotating any number of adjacent rings by one place.

In the previous post, we found an algorithm for computing these bicycle lock numbers, revealing a mysterious symmetry, « Read the rest of this entry »

The bicycle lock problem

2014-02-18 § 3 Comments

Giant bicycle lock

Photo: WickedVT


Don’t lock your bicycle with a combination lock. Someone will steal it: I learnt this the hard way. It’s quite easy to open a combination lock by feel, without knowing the combination. Try it: with a bit of practice, you can open the lock with your eyes shut. (It’s easier to do this with an old wobbly lock than a tight-fitting new one.)
« Read the rest of this entry »

Beyond Bézier curves

2013-11-13 § 4 Comments

There is a new feature of Pages and Keynote, not mentioned in any of Apple’s publicity nor in any press coverage I’ve seen, that is really very interesting. Perhaps it will even one day prove to have been revolutionary, in a quiet way. « Read the rest of this entry »

The algebra of Unix command substitution

2013-08-16 § 6 Comments

Shadab Ahmed raised an interesting question. Open a Unix command shell, type : '!!' and press return. Then type : "!!" '!!' and press return. Now repeat the following a few times: press the up arrow, and press return.

« Read the rest of this entry »

“Venn diagram” partitioning

2013-07-10 § Leave a comment

Paddy3118 wrote about partitioning elements in the same way a Venn diagram does. So, if we have sets AB and C, the partitions are

Image

« Read the rest of this entry »

Adrift is NP-complete

2013-03-13 § Leave a comment

There’s a lovely new puzzle game for the iPhone called Adrift. I got it last week when I was in bed with flu, and it’s a fun way to spend a few hours.

The puzzles look like this:

Image

And you solve them by connecting the coloured stars with paths of the same colour:

board1-solved

You can play a few demo levels on the web. This is a very simple example. Some of the more difficult ones are pretty fiendish.

« Read the rest of this entry »

John H Conway and the invention of the filing cabinet

2012-10-27 § Leave a comment

Conway is incredibly untidy. The tables in his room at the Department of Pure Mathematics and Mathematical Statistics in Cambridge are heaped high with papers, books, unanswered letters, notes, models, charts, tables, diagrams, dead cups of coffee, and the most amazing assortment of bric-a-brac, which has overflowed most of the floor and all of the chairs, so that it is hard to take more than a pace or two into the room and impossible to sit down. If you can reach the blackboard there is a wide range of coloured chalk, but no space to write. His room in college is in a similar state. In spite of his excellent memory he often fails to find the piece of paper with the important result that he discovered some days before, and which is recorded nowhere else. Even Conway came to see that this was not a desirable state of affairs, and he set to work designing and drawing plans for a device which might induce some order amongst the chaos. He was about to take his idea to someone to get it implemented, when he realised that just what he wanted was standing, empty, in the corner of his room. Conway had invented the filing cabinet!

Richard K Guy on John H Conway, in Mathematical People

I originally posted this to Posterous on 27 October, 2012. Posterous is closing down, so I have migrated it here on 13 March, 2013.

The Prisoner’s Dilemma

2012-07-23 § 23 Comments

The Prisoners’ Dilemma

The Prisoner’s Dilemma is a game, but a game that seems to bear lessons for the conduct of human affairs more generally, and it has attracted a great deal of attention from men not noted for their frivolity. It was discovered in 1950 at the RAND corporation, a military think-tank established after World War II by the United States Air Force to conduct a “program of study and research on the broad subject of intercontinental warfare”.

photo: DenisNata / Shutterstock.com

So it is a serious game, but a simple one for all that. It requires two players, let’s say you and me. There is only one move. Each of us must make a choice, to “cooperate” or “defect”, without knowing what the other has chosen. Perhaps each of us takes, from a chess board, one black and one white pawn, and as we face each other I put my hands behind my back and proffer a closed fist containing the pawn I have chosen. You make your choice, too, in the same way. Together we open our hands, and reveal what we have chosen. The black pawn represents the black heart of the defector, the white the innocence of the cooperator.

Now, the reckoning. Should we each reveal a white pawn, we have cooperated and each of us wins £20: a fair and happy outcome. If we both are blackhearts with black pawns in our hands, we win nothing. But wickedness is not without its rewards in this game, for if I hold black and you white then I win £40 – and you, looking sadly at the white pawn in your hand, must pay £10 for your naivety. « Read the rest of this entry »

On editing text

2012-05-10 § 16 Comments

Editing text is the opposite of handling exceptions; or, to put it another way, editing text is like exception handling but backwards in time. I realise this is an unexpected claim, so I hope you will permit me to explain. Although it has the ring of nonsense, there is a perfectly good sense in which it is just straightforwardly true.

Added 2014-06-18: it turns out that the story is more interesting than I realised when I wrote this, and that almost all of the technical details below are wrong. I am in the process of writing an account of what I currently believe on this subject.

Ah yes, category theory. Our old friend. Elucidating structural connections between apparently disconnected topics since 1945. Let me tell you a story.

« Read the rest of this entry »

Where Am I?

You are currently browsing the Mathematics category at Bosker Blog.

Follow

Get every new post delivered to your Inbox.

Join 743 other followers