Re-gifting An Old Theorem
An old theorem re-packaged?
Emily Post was America’s premier writer on etiquette for much of the 20th Century. The Emily Post Institute, which she founded in 1946, carries on much of her legacy, directed mostly by family at the “great-” and “great-great-” grandchild level. It features a free online “Etipedia.” Alas searches for terms that would relate to theory research etiquette come up empty. This makes us wonder whether a service could be named for Emil Post, the famous co-founder of computability theory. I believe there is no connection between Emil and Emily, except for the obvious one.
Today, known as Boxing Day in British culture, is often re-boxing day in the US and everywhere, as we return gifts that are not-quite-right. But instead I wish to talk about the alternate practice of re-gifting, which raises issues of relevance to both Emily and Emil. Read more…
A Pardon For Alan Turing
I beg your pardon
Elizabeth Mary, Queen Elizabeth II, is the Queen of the United Kingdom and of the other Commonwealth realms. She has just today granted Alan Turing a posthumous royal pardon under the rule of “royal prerogative of mercy.”
Today Ken and I want to add our thoughts to this event. Read more…
What Is Best Result Of The Year?
What do you think?
Charles Lindbergh is famous for his solo non-stop flight that left Roosevelt Field in Long Island on May 20, 1927 and arrived the next day at Le Bourget Field in Paris. He covered a distance of almost 
Today Ken and I want to talk about not about making solo flights, or air travel, or jumbo jets; but about selecting the
“Person Of The Year.” Read more…
Who Knew The Secret?
Controlled release of secret information
Peter Winkler is a world famous mathematician who works mostly on combinatorial problems. He is famous for many things, but his series of puzzle book are terrific—see here. Also he is “notorious” for his discovery that cryptography could be used in contract bridge. Amazing.
Today Ken and I want to talk about his paper on “Cryptogenography” to be presented at the ITCS Conference this coming January. It is joint with Joshua Brody, Sune Jakobsen, and Dominik Scheder. They have made up the word from cryptography and steganography. Read more…
A Negative Impossibility Theorem
A positive result on clustering
Ravi Kannan is a long-time friend, a brilliant theorist, and a wonderful speaker. He has won numerous awards, including the Fulkerson Prize and the Knuth Prize, for his ground-breaking research.
Today I wish to talk about a recent presentation that Ravi gave at Tech on clustering, which contained a negative impossibility theorem. Read more…
Judging A Book By Its Coverage
Flaws in constitution
|
|
Cropped from book page. |
Rebecca Goldstein is the author of the book Incompleteness: The Proof and Paradox of Kurt Gödel. She obtained her PhD in Philosophy from Princeton University, and has also written several novels set in academia, including The Mind-Body Problem and Properties of Light: A Novel of Love, Betrayal and Quantum Physics. The latter draws on the life and concerns of the physicist David Bohm.
Today Ken and I wish to talk about Kurt Gödel’s journey in getting his USA citizenship, and his journey since then in the interpretation and implications of his research. Read more…
Isomorphism Is Where It’s At
Isomorphism at the SODA 2014 conference
Ronald Read and Derek Corneil are Canadian mathematicians and computer scientists. Read earned a PhD in Mathematics from the University of London in 1959, while Corneil was one of the inaugural PhD’s in the University of Toronto’s Department of Computer Science. Read is also an accomplished musician and composer—indeed our photo comes from his entry with a sheet-music publisher in England—and here is a music-themed paper. Corneil became Chair at UT DCS and has done much liaison work with Canadian IT companies and international education. Together they wrote a survey paper in the 1977 first volume of the Journal of Graph Theory titled “The Graph Isomorphism Disease.”
Today Ken and I would like to take issue with one of the words in their title. No, not “disease,” but rather: “graph.”
Theorems From Physics?
Can information physics extract proofs from reality?
|
|
IEEE source |
Rolf Landauer was a physicist and computer engineer who spent most of his career at IBM north of New York City, becoming an IBM Fellow in 1969. According to his longtime colleague Charles Bennett, Landauer “did more than anyone else to establish the physics of information processing as a serious subject for scientific inquiry.” One was was his discovery and formulation of a principle connecting non-reversible computation steps and thermodynamic entropy, which according to Wikipedia’s article is widely accepted as a physical law.
Today Ken and I want to talk about the possible role of physical laws in generating proofs of complexity assertions, even 
Read more…
Finding Patterns In Ancient Objects
Ancient mathematical objects can still contain secrets
|
|
Recreational Mathematics source |
David Singmaster is a mathematician who is now retired from London South Bank University, England, but he is not British—he was born in the USA. As a metagrobologist, he has a huge collection of mechanical puzzles, books on puzzles, and more. For a quick puzzle, can you name another word—of definite relevance to this blog—that ends in “-bology” (and not “-biology”)?
Today Ken and I wish to talk about Pascal’s Triangle, and a beautiful conjecture of Singmaster on the structure of the famous triangle.
The Graph of Math
The last part of our interview with Gödel two years ago
|
|
src |
Kurt Gödel is said to have been a latecomer to appreciating the power of Model Theory. He was of course the greatest architect of Proof Theory, which stands in contrast to Model Theory. Model Theory concerns itself with what could be true, while Proof Theory deals with what can be proved. The latter sounds more definite, but they are supplementary: a statement is capable of being true somewhere precisely when its negation cannot be proved. The question is, where is that somewhere? And when?
Two years ago by our reckoning, Dick and I put that question to Gödel, at the close of our interview whose first and second parts we posted at this time the past two years.
Read more…
