## Binary search in the Old Testament

### August 10th, 2015

The lot is cast into the lap,
but its every decision is from the Lord.
(NIV Proverbs 16:33)

 …“Lux et Veritas”… Seal of Yale University image from Wikimedia Commons.

The seal of Yale University shows a book with the Hebrew אורים ותמים (urim v’thummim), a reference to the Urim and Thummim of the Old Testament. The Urim and Thummim were tools of divination. They show up first in Exodus:

Also put the Urim and the Thummim in the breastpiece, so they may be over Aaron’s heart whenever he enters the presence of the Lord. Thus Aaron will always bear the means of making decisions for the Israelites over his heart before the Lord. (NIV Exodus 28:30; emphasis added)

Apparently, the Urim and Thummim worked like flipping a coin, providing one bit of information, a single binary choice communicated from God.1 Translations of Urim as “guilty” and Thummim as “innocent” indicate that the divination was used to determine guilt: “Thummim you win; Urim you lose.” An alternate translation has Urim “light” and Thummim “truth”, hence “Lux et Veritas” in the Yale seal’s banner.

Saul, King of Israel and father-in-law of King David, uses the binary choice provided by Urim and Thummim divination in 1 Samuel to unmask the party who violated the king’s oath:

Then Saul prayed to the Lord, the God of Israel, “Why have you not answered your servant today? If the fault is in me or my son Jonathan, respond with Urim, but if the men of Israel are at fault, respond with Thummim.” Jonathan and Saul were taken by lot, and the men were cleared. Saul said, “Cast the lot between me and Jonathan my son.” And Jonathan was taken. (NIV2 1 Samuel 14:41-42)

Saul executes a small (and highly unbalanced) binary search. He first divides the population into two parts. He and his son Jonathan are assigned Urim and all the rest get Thummim. God responds with Urim. Then to decide between Saul and Jonathan, the process is repeated, and Jonathan is fingered as the guilty party. (The method apparently works; the preceding verses of 1 Samuel give the story of Jonathan’s transgression.)

The universality of binary as an information conveying method has a longer history than one might have thought.

1. The Old Testament Urim and Thummim should not be confused with the “higher bandwidth” device of the same name that Joseph Smith claimed to use to receive the translation of a now lost 116 pages of the Book of Mormon. This device purportedly resembled a pair of spectacles with transparent rocks for lenses, a kind of “oraculus rift”. For the extant Book of Mormon, Smith changed his method to scrying with a “seer stone” placed in his hat. A photograph of the stone, coincidentally, has just recently been released by the LDS church.
2. The use of a Septuagint-based version of the Bible, here the New International Version, is important, as this verse is considerably shortened in versions such as the King James based on the Masoretic text, leaving out the use of Urim and Thummim to make a binary decision.

## The two Guildford mathematicians

### February 18th, 2015

 …the huge ledger… Still from Codebreaker showing Turing’s checkout of three Carroll books.

The charming town of Guildford, 40 minutes southwest of London on South West Trains, is associated with two famous British logician-mathematicians. Alan Turing (on whom I seem to perseverate) spent time there after 1927, when his parents purchased a home at 22 Ennismore Avenue just outside the Guildford town center. Although away at his boarding school, the Sherborne School in Dorset, which he attended from 1926 to 1931, Turing spent school holidays at the family home in Guildford. The house bears a blue plaque commemorating the connection with Turing, the “founder of computer science” as it aptly describes him, which you can see in the photo at right, taken on a pilgrimage I took this past June.

 …the family home… The Turing residence at 22 Ennismore Avenue, Guildford

And this brings us to the second famous Guildford mathematician, who it turns out Turing was reading while at Sherborne. In the Turing docudrama Codebreaker, one of Turing’s biographers David Leavitt visits Sherborne and displays the huge ledger used for the handwritten circulation records of the Sherborne School library. There (Leavitt remarks), in an entry dated 11 April 1930, Turing has checked out three books, including Alice in Wonderland and Through the Looking Glass, and What Alice Found There. (We’ll come back to the third book shortly.) The books were, of course, written by the Oxford mathematics don Charles Lutwidge Dodgson under his better known pen name Lewis Carroll. Between the 1865 and 1871 publications of these his two most famous works, Carroll leased “The Chestnuts” in Guildford in 1868 to serve as a home for his sisters. The house sits at the end of Castle Hill Road adjacent to the Guildford Castle, which is as good a landmark as any to serve as the center of town. Carroll visited The Chestnuts on many occasions over the rest of his life; it was his home away from Christ Church home. He died there 30 years later and was buried at the Guildford Mount Cemetery.

 …through the looking glass… Statue of Alice passing through the looking glass, Guildford Castle Park, Guildford

Guildford plays up its connection to Carroll much more than its Turing link. In the park surrounding Guildford Castle sits a statue of Alice passing through the looking glass, and the adjacent museum devotes considerable space to the Dodgson family. A statue depicting the first paragraphs of Alice’s adventures (Alice, her sister reading next to her, noticing a strange rabbit) sits along the bank of the River Wey. The Chestnuts itself, however, bears no blue plaque nor any marker of its link to Carroll. (A plaque formerly marking the brick gatepost has been removed, evidenced only by the damage to the brick where it had been.)

 …The Chestnuts… The Dodgson family home in Guildford

Who knows whether Turing was aware that Carroll, whose two Alice books he was reading, had had a home a mere mile from where his parents were living. The Sherborne library entry provides yet another convergence between the two British-born, Oxbridge-educated, permanent bachelors with sui generis demeanors, questioned sexualities, and occasional stammers, interested in logic and mathematics.

But there’s more. What of the third book that Turing checked out of the Sherborne library at the same time? Leavitt finds the third book remarkable because the title, The Game of Logic, presages Turing’s later work in logic and the foundations of computer science. What Leavitt doesn’t seem to be aware of is that it is no surprise that this book would accompany the Alice books; it has the same author. Carroll published The Game of Logic in 1886. It serves to make what I believe to be the deepest connection between the two mathematicians, one that has to my knowledge never been noted before.

 …Carroll’s own copy… Title page of Lewis Carroll, The Game of Logic, 1886. EC85.D6645.886g, Houghton Library, Harvard University.

After watching Codebreaker and noting the Game of Logic connection, I decided to refresh my memory about the book. I visited Harvard’s Houghton Library, which happens to have Carroll’s own copy of the book. The title page is shown at right, with the facing page visible showing a sample card to be used in the game. The book was sold together with a copy of the card made of pasteboard and counters of two colors (red and grey) to be used to mark the squares on the card.

The Houghton visit and the handling of the game pieces jogged my memory as to the point of Carroll’s book. Carroll’s goal in The Game of Logic was to describe a system for carrying out syllogistic reasoning that even a child could master. Towards that goal, the system was intended to be completely mechanical. It involved the card marked off in squares and the two types of counters placed on the card in various configurations. Any of a large class of syllogisms over arbitrary properties can be characterized in this way, given a large enough card and enough counters, though it becomes unwieldy quite quickly after just a few.

 … marked off in squares… The game card depicting a syllogism. Lewis Carroll, The Game of Logic, 1886. EC85.D6645.886g, Houghton Library, Harvard University.

(The photo at right shows the card and counters that came with the book. I’ve placed the counters in such a way as to depict the syllogism:

 No red apples are unripe. Some wholesome apples are red. ∴ Some ripe apples are red.         )

To computer scientists, this ought to sound familiar. Just six years after checking out The Game of Logic from his school library, Turing would publish his groundbreaking paper “On computable numbers”, in which he describes a system for carrying out computations in a way that is completely mechanical. It involves a paper tape marked off in squares, and markings of at least two types placed on the tape in various configurations. Any of a large class of computations over arbitrary values can be characterized in this way, given a large enough tape and enough markings, though it becomes unwieldy quite quickly. We now call this mechanical device with tape and markings a Turing machine, and recognize it as the first universal model of computation. Turing’s paper serves as the premier work in the then nascent field of computer science.

Of course, there are differences both superficial and fundamental between Carroll’s game and Turing’s machine. Carroll’s card is two-dimensional with squares marked off in a lattice pattern, and counters are placed both within the squares and on the edges between squares. Turing’s tape is one-dimensional (though two-dimensional Turing machines have been defined and analyzed) and the markings are placed only within the squares. Most importantly, nothing even approaching the ramifications that Turing developed on the basis of his model came from Carroll’s simple game. (As a mathematician, Carroll was no Turing.) Nonetheless, in a sense the book that Turing read at 17 attempts to do for logic what Turing achieved six years later for computation.

I have no idea whether Lewis Carroll’s The Game of Logic influenced Alan Turing’s thinking about computability. But it serves as perhaps the strongest conceptual bond between Guildford’s two great mathematicians.

Update February 25, 2015: Thanks to Houghton Library Blog for reblogging this post.

## A document scanning smartphone handle

### March 13th, 2014

 …my solution to the problem… (Demonstrating the Scan-dle to my colleagues from the OSC over a beer in a local pub. Photo: Reinhard Engels)

They are at the end of the gallery; retired to their tea and scandal, according to their ancient custom.

William Congreve

For a project that I am working on, I needed to scan some documents in one of the Harvard libraries. Smartphones are a boon for this kind of thing, since they are highly portable and now come with quite high-quality cameras. The iPhone 5 camera, for instance, has a resolution of 3,264 x 2,448, which comes to about 300 dpi scanning a letter-size sheet of paper, and a brightness depth of 8 bits per pixel provides an effective resolution much higher.

The downside of a smartphone, and any handheld camera, is the blurring that inevitably arises from camera shake when holding the camera and pressing the shutter release. True document scanners have a big advantage here. You could use a tripod, but dragging a tripod into the library is none too convenient, and staff may even disallow it, not to mention the expense of a tripod and smartphone tripod mount.

My solution to the problem of stabilizing my smartphone for document scanning purposes is a kind of document scanning smartphone handle that I’ve dubbed the Scan-dle. The stabilization that a Scan-dle provides dramatically improves the scanning ability of a smartphone, yet it’s cheap, portable, and unobtrusive.

The Scan-dle is essentially a triangular cross-section monopod made from foam board with a smartphone platform at the top. The angled base tilts the monopod so that the smartphone’s camera sees an empty area for the documents.[1] Judicious use of hook-and-loop fasteners allows the Scan-dle to fold small and flat in a couple of seconds.

The plans at right show how the device is constructed. Cut from a sheet of foam board the shape indicated by the solid lines. (You can start by cutting out a 6″ x 13.5″ rectangle of board, then cutting out the bits at the four corners.) Then, along the dotted lines, carefully cut through the top paper and foam but not the bottom layer of paper. This allows the board to fold along these lines. (I recommend adding a layer of clear packaging tape along these lines on the uncut side for reinforcement.) Place four small binder clips along the bottom where indicated; these provide a flatter, more stable base. Stick on six 3/4″ hook-and-loop squares where indicated, and cut two 2.5″ pieces of 3/4″ hook-and-loop tape.

When the board is folded along the “fold for storage” line (see image at left), you can use the tape pieces to hold it closed and flat for storage. When the board is folded along the two “fold for use” lines (see image at right), the same tape serves to hold the board together into its triangular cross section. Hook-and-loop squares applied to a smartphone case hold the phone to the platform.

To use the Scan-dle, hold the base to a desk with one hand and operate the camera’s shutter release with the other, as shown in the video below. An additional trick for iPhone users is to use the volume buttons on a set of earbuds as a shutter release for the iPhone camera, further reducing camera shake.

The Scan-dle has several nice properties:

1. It is made from readily available and inexpensive materials. I estimate that the cost of the materials used in a single Scan-dle is less than $10, of which about half is the iPhone case. In my case, I had everything I needed at home, so my incremental cost was$0.
2. It is extremely portable. It folds flat to 6″ x 7″ x .5″, and easily fits in a backpack or handbag.
3. It sets up and breaks down quickly. It switches between its flat state and ready-to-go in about five seconds.
4. It is quite sufficient for stabilizing the smartphone.

The scanning area covered by a Scan-dle is about 8″ x 11″, just shy of a letter-size sheet. Of course, you can easily change the device’s height in the plans to increase that area. But I prefer to leave it short, which improves the resolution in scanning smaller pages. When a larger area is needed you can simply set the base of the Scan-dle on a book or two. Adding just 1.5″ to the height of the Scan-dle gives you coverage of about 10″ x 14″. By the way, after you’ve offloaded the photos onto your computer, programs like the freely available Scantailor can do a wonderful job of splitting, deskewing, and cropping the pages if you’d like.

Let me know in the comments section if you build a Scan-dle and how it works for you, especially if you come up with any use tips or design improvements.

### Materials:

(Links are for reference only; no need to buy in these quantities.)

1. The design bears a resemblance to a 2011 Kickstarter-funded document scanner attachment called the Scandy, though there are several differences. The Scandy was a telescoping tube that attached with a vise mount to a desk; the Scan-dle simplifies by using the operator’s hand as the mount. The Scandy’s telescoping tube allowed the scan area to be sized to the document; the Scan-dle must be rested on some books to increase the scan area. Because of its solid construction, the Scandy was undoubtedly slightly heavier and bulkier than the Scan-dle. The Scandy cost some €40 (\$55); the Scan-dle comes in at a fraction of that. Finally, the Scandy seems no longer to be available; the open-source Scan-dle never varies in its availability.  ↩

## Guest Post: On Lance Armstrong

### January 22nd, 2013

[I am pleased to present a guest post from my friend Ann Velenchik, professor of economics at Wellesley College, director of their writing program, and expert monologist. This post is reproduced from her private blog, which I am privileged to have access to, in which she has chronicled her experience with her leukemia diagnosis and treatment over the last three years.]

 …one of my idols…“Oprah Winfrey speaks at the launch of the Born This Way Foundation” image by flickr user HarvardEducation.

January 18, 2013 — Despite living with Bicycle Boy, I take no interest in competitive cycling. We were in Paris for the end of the Tour de France in 2008, and while Tom, Becca and Nate all stood on benches to see the riders circle the Arc de Triomphe, I was happily drinking an orangina at a table far from the crowds. Tom has assured me, for years, that Armstrong has clearly been doping, and I frankly didn’t think much more about it.

But I obviously couldn’t escape the news that Oprah would be interviewing Armstrong on TV last night and, because Oprah is one of my idols, I did a little web surfing this morning to find out what was said. And I found something that made me so angry that I had to respond.

In a part of the conversation about why he had started doping, and how he justified it to himself, Armstrong lay some of the blame on the “fighting spirit” he developed during his “battle” with testicular cancer from October 1996 to February 1997.

“That process turned me into a person — it was truly win at all costs,” Armstrong said. “When I was diagnosed, I said, ‘I will do anything I need to do to survive,’ and that’s good. And I took that attitude, that ruthless and relentless and win-at-all-costs attitude into cycling, and that’s bad.”

Let’s leave aside the fact that there’s evidence that he started doping before he got cancer, and that it’s possible that taking a lot of testosterone might have made that cancer worse. Let’s just talk about the idea that the attitude that helped him “win” the cancer battle justifies, or even explains, what the evidence indicates he has done since.

I think it is highly possible that cancer diagnosis and treatment in the prime of his life was a deep and abiding trauma that warped his moral compass. As I have said before, I don’t think cancer is a blessing in disguise, and I don’t think all the lessons we learn there are good ones, let alone worth the price. So I am not even pissed off that he has the audacity to use his status as a cancer patient to explain the appalling way he has treated people.

What pisses me off is his description of the attitude he brought to treatment itself. When he says “I will do anything I need to do to survive…ruthless and relentless and win-at-all-costs…,” as though lying and cheating and doing terrible things to other people were part of the cancer process, that’s when my head starts to explode.

Because, here’s the thing. There isn’t much in cancer treatment that requires lying or cheating, that requires you to sue for libel the people who are actually telling the truth, or that allows you to threaten and bully and defame other people. Yes, there’s a lot of win-at-all costs to be found there, but those aren’t costs you get to impose on other people.

Lance Armstrong misspoke. Cancer treatment isn’t about being willing to do anything to anyone in order to win. It’s about being willing to endure anything onesself. Here’s my guess. Lance Armstrong is a very bad guy who was a bad guy before he got cancer and perhaps a worse one afterward. He doped because he was getting away with it and getting richer and more famous every minute. He lied and intimidated and threatened and bullied because, as I heard one person say, when he got cornered his strategy was to double down. And maybe his experience as a cancer patient was part of the list of things that made him so broken. But that’s about him, not about cancer.

## Why this blog?

### May 22nd, 2009

This blog presents occasional writings on whatever I’m interested in at the moment, which currently includes topics such as:

• scholarly communications and open access, and other university matters
• computer science topics of various sorts
• language, linguistics, and computational linguistics
• pedagogy and writing

I expect that in the near term, I’ll primarily be commenting on open access issues.

I’ve avoided having a blog until now because in the past I’ve been constitutionally incapable of presenting my thinking in any kind of interim state. This blog is my attempt to change this archaic aspect of my personality, and to provide a venue for writings of a more exploratory or ephemeral nature. Still, I expect many posts will be relatively long as compared to a typical blog, though short compared to a scholarly article and more topical.

I chose the word “pamphlet” to describe these writings, as I was inspired to experiment with this style of writing by the pamphlets of Charles Dodgson (Lewis Carroll). The use of the word “occasional” under both of its first two senses was intentional.

The opinions expressed here are my own. I am not speaking on behalf of Harvard or any of its constituent parts, or on behalf of anyone else for that matter.