Recent News

[click here to zip down to the schedule of public lectures]

Happy Turing Year to All!

Many celebrations are being planned in 2012 to commemorate the centennial year of Alan Turing, one of the principal “fathers” of computer science, who was born in 1912. By coincidence, my own biological father and mother were also born in that year. I plan to make cameo appearances at ACM's event in San Francisco and at the major symposium in Manchester, both in June (see below).

For the secret of the Turing number 885205232, see pages 45 and 53 of Selected Papers on Fun and Games.

Nomenclaturing: Let's Ture to the Max!

Christos Papadimitriou's recently published reminiscences [“Alan and I”, Communications of the ACM 55.9 (September 2012), 42--43] include the fascinating story of how he learned about Turing Machines: As a bored undergraduate in a Greek university, he happened to see the definition buried within an article about pattern recognition, and he was immediately entranced.

I longed to learn more about it, but I had no access to a scientific library. I looked up in my English--Greek dictionary the verb “to ture” (I really did).

“To ture”: We should assign a meaning to this wonderful verb before it's too late!

Idea #0. “to ture” = opposite of “to flase”.


Idea #1. “to ture” = to compute as an automaton does.

This idea has positive (but ε) merit. Notice, for example that the first important exploration game was named ‘adventure’, and it was based on a finite-state model of a cave and its inhabitants/treasures.

Idea #2. “to ture” = to use the Internet.

Aha, this one immediately looks terrific. Not only does it honor Alan in an entirely appropriate way, it also fills a real need: The English language currently has no verb with this meaning, and such a verb becomes more necessary as each day passes.

“We couldn't ture at home this morning because the wireless was down, so we tured at the coffeehouse instead.”

(To pronounce this word, say tyoor as in ‘picture’ or ‘architecture’. While celebrating Alan's 100th birthday in Manchester this summer I learned to call him Tyooring.)

What think you? If you agree, we could probably plant this word into the world's vocabulary very quickly via social networks. In fact a large percentage of the world could well be turing daily before the end of 2012!

Watch a Video

Here's a recently posted video interview by Daisy Morin that was filmed at my house on 16 November 2009.

The Theory of Traces

I've spent a month this spring learning more about the beautiful theory of traces, which I had planned to discuss in Volume 5 of The Art of Computer Programming but I'm now moving some of it up into Volume 4B. This theory is isomorphic to what Xavier Viennot calls "heaps of pieces"; and I recently learned of a cool video of a lecture in which he explains many of the reasons why I love the subject.

Check Out My Latest Book

This year I'm celebrating the recent completion of a book that I've dreamt about for many, many years:

Companion to the Papers of Donald Knuth

(and you can discover more about it by clicking).

A Blast From The Past

Here are excerpts from the Memorial Day Programming Race organized by John McCarthy on 31 May 1971. (Mentioned at Stanford's McCarthy Celebration, 25 March 2012.)

New Updates to Computers & Typesetting

Spiffy new printings of the hardcover versions of The TeXbook, TeX: The Program, and The METAFONTbook are now available---produced for the first time entirely with modern technology! Hurray! Now is a perfect time to replace any old copies that have become dog-eared after years of (ab)use. (Click here for full details.)

Plus Brand-New Printings of Four Other Unique Books!

Yes indeed, this is a banner year for reissuing books in much-improved form. I'm pleased to announce the fourth printing of Selected Papers on Computer Science (the book that I wrote for non-specialists who are curious about the subject), as well as the second printing of Digital Typography (which contains the full Monty regarding my work on TeX and METAFONT), as well as the third printing of Selected Papers on Analysis of Algorithms (which is about the central research focus of my life), as well as the third printing of Selected Papers on Fun and Games (which is my absolutely favorite book, but don't ask me why).

I'm particularly thrilled to be able to hold the Digital Typography book in my hand, because it incorporates hundreds of refinements to the first printing, and because many technical challenges had to be overcome. In fact, the successful production and publication of such a volume has been sort of miraculous, as several aspects of printing technology have been stretched to the limit, and a great many people deserve thanks for making it possible.

A New Secret Message

Exercise 4.5.4--47 in Seminumerical Algorithms asks readers to decipher a hidden message, which is encrypted with the RSA scheme. When I posed this exercise in 1997, I thought I had chosen parameters large enough that nobody would solve it during my lifetime; I figured maybe my children or grandchildren would some day get a kick out of seeing the answer revealed.

Shock, shock! On September 14 I learned from Greg Childers that he, together with about 500 volunteers in the NFS@Home project, had cracked the code --- and he presented me with the exact answer. Congratulations to them!

Now I've increased the length of the cipher and public key by 50%, so that my grandchildren and/or their kids still can have some fun. In order to save people from the tedium of copying so many digits of data, I've put the new version online, both in decimal form and in hexadecimal form.

A taste of Volume 4B

Volume 4B of The Art of Computer Programming will begin with a special section called ‘Mathematical Preliminaries Redux’, which extends the ‘Mathematical Prelimaries’ of Section 1.2 in Volume 1 to things that I didn't know about in the 1960s. Most of this new material deals with probabilities and expectations of random events; there's also an introduction to the theory of martingales.

You can have a sneak preview by looking at the current draft of pre-fascicle 5a (32 pages). As usual, rewards will be given to whoever is first to find and report errors or to make valuable suggestions. I'm particularly interested in receiving feedback about the exercises (of which there are 78) and their answers (of which there are 78).

Public lectures in 2012

Although I must stay home most of the time and work on yet more books that I've promised to complete, I do occasionally get into speaking mode. Here is a current schedule of events that have been planned for this year so far:

Wednesday, January 11, 13:30pm at Schweizer Tag für den Informatikunterricht (STIU) in St. Gallen, Switzerland
Speaking briefly as I receive the “Ausbildungs- und Beratungszentrum für Informatikunterricht Platinum Gold Medal of Eidgenössische Technische Hochschule Zürich for Computer Science and Computer Science Education”
Saturday, January 14, 14:00pm in Audi Max at ETH Zürich
Speaking at Swiss Olympiad Day, "All Questions Answered" (watch video)
Thursday, January 26, 12:30pm at the Stanford CS Theory Lunch
speaking informally about "The Plastic Constant and Complexity Theory"
Thursday, April 12, 12:30pm at the Stanford CS Theory Lunch
speaking informally about "Reluctant Doubling"
Sunday, April 22, 9:15am at the Adult Forum of First Lutheran Church, Palo Alto
leading an informal discussion of the Bible verse Acts 3:16
Sunday, April 29, 9:15am at the Adult Forum of First Lutheran Church, Palo Alto
leading an informal discussion of the Bible verse 1 John 3:16
Saturday, June 16, 11:15am at the Palace Hotel in San Francisco
Participating in a panel at the ACM Turing Centenary Celebration
Tuesday June 19, 10am
Giving a keynote talk, followed by a break and then a Q&A session, at the SAT 2012 Conference in Trento, Italy (using these slides)
Sunday June 24, 7pm
speaking (impromptu) in connection with the banquet of The Alan Turing Centenary Conference in ManchesterUK
Tuesday September 4, 7:15pm at Berkeley City College Auditorium
participating in a panel discussion at MSRI's Turing Centenary Celebration
Tuesday November 13, 4:30pm in Lecture Theatre B
speaking on "Reluctant Doubling" at the Oxford Comlab as part of the Departmental Seminar Series
Friday December 14, 4:30pm in the NVIDIA Auditorium, Huang Engineering Center
A "Computer Musing" entitled ``Trees and chordal graphs'' [the eighteenth annual Christmas Tree Lecture]
(click here to sign up for live streaming of the webcast)
Sunday, December 16, 9:15am at the Adult Forum of First Lutheran Church, Palo Alto
leading an informal discussion of the Bible verse Luke 3:16

Click here for the ``recent news'' that was current at the end of 2011, if you're interested in old news as well as new news.

Don Knuth's home page

Valid HTML 4.01 Transitional