Kurt Gödel in popular culture and answers to Thursday’s problems

 Levi Weaver source

Kurt Gödel may yet make it to Broadway. He already splashed across the silver screen in the 1994 Meg Ryan-Tim Robbins comedy I.Q. as the roly-poly sidekick of Walter Matthau playing Albert Einstein. He was pressed into retro vinyl by Levi Weaver for his 2011 album The Letters of Dr. Kurt Gödel. He features in the major Japanese manga series Negima! These borrowings may be incomplete or inconsistent, but with Gödel that’s par, no?

Today we consider Gödel’s impact on popular culture and give answers to the conjectures in Thursday’s post.

The play Ghosts in Princeton by Daniel Kehlmann gives serious focus to Gödel’s life. Although it travels Gödel to various times in his life, it is anchored in 1936–1939 with Gödel still in Austria despite the assassination of a close Jewish friend, the Nazi Anschluss of Austria in March 1938, and the outbreak of war in September 1939. It puts in Gödel’s mouth the logical antinomy,

If nobody believes you’re not X, then arguably you’re X;

where X = being Jewish. The Nazis treated all members of the Vienna Circle as Jewish and it took Gödel “punishably long” to wise up. The play bounces its themes off Einstein including a re-enactment of the “always freezing” Gödel’s walks with him in Princeton between the Institute and Einstein’s home. When by himself, Gödel speaks in tones fit for Halloween:

For twenty days no stars, no sun. All black. The world is extinguished. Actually, that is beautiful.

## Ghosts and Madness

Kehlmann’s play draws its title from Gödel’s own belief in ghosts, that one could communicate with them. It portrays the beginnings of his madness. Gödel had his first documented breakdown while returning from lectures he gave at Princeton in 1934. His paranoia was boosted by the killing of his Jewish friend and Gödel himself being set upon by a gang of Nazi youths when he was merely strolling with his wife.

The play also shows the paradox that madness comes from Gödel’s unflinching engagement with reality, aspects of which we tried to explain in our Gödel post a year ago. It has him say:

From the need to question there is no shrinking back afraid. Not even in the face of madness. One sees a mirror that is itself reflected in a mirror and one wishes to turn away. But one does not. And suddenly one begins to understand.

There are parallels here to how the movie “Pawn Sacrifice” attempts to show a partial origin of Bobby Fischer’s madness in how he saw certain policy matters in black and white. Both the play and movie, however, also show the more immediate impact of paranoia. It was rooted in some events—WWI-style poison gas for Gödel, (anti-) communist surveillance for Fischer—but assumed its own primal power.

Janna Levin’s award-winning novel A Madman Dreams of Turing Machines connects the engagement more closely to the mathematical content of Gödel’s theorems. We might say more about this novel’s portrayal of Gödel and Alan Turing. What I find a missing key, however—ironically in Fischer’s case—is the relative absence of an instinct for play. Play can be good for both balance and focus.

So turning away from serious themes, we’ll go back to being light. Our man is gaining stature on stage and screen and in music and novels, even what used to be called “comic books.” All he needs now is his own line of merchandise. Actually there already is one in his name, a gift shop in Niagara-on-the-Lake only 30 miles from my house:

## Answers to Thursday’s Conjectures

Three of the problems we discussed have strong connections to Princeton. John Conway—himself an apostle of play—is there, and Edward Scheinerman’s doctoral thesis was under Douglas West, whom I was also fortunate to have as advisor for my Princeton undergraduate thesis. Janusz Brzozowski, who features prominently in the star-height problem, also did his PhD at Princeton. The two solvers of the equitable coloring problem still hail from nearby Rutgers University. Only the road coloring problem seems to escape a New Jersey connection, which is ironic for a state whose unofficial motto is, “What exit?

${\bullet}$ The Angel Problem is a win for the angel even with ${k=2}$. Although Conway’s paper evoked the maxim “fools rush in where angels fear to tread,” the angel in Oddvar Kloster’s strategy wins by rushing right at the devil, always keeping her left hand touching territory that is marked or otherwise forbidden. Kloster’s overall page includes a downloadable Java application showing his strategy in action. It also describes three other winning strategies, including another for ${k=2}$ by András Máthé.

These neat slides by Stijn Vermeeren discuss the problem and Kloster’s proof and some further variations and open problems. On a 3D grid the proof can be implemented by a chess king (${k=1}$ in 3D) using the ${z=0}$ and ${z=1}$ planes only. Whether a king that always moves to a higher plane can survive is open. There are also open problems about the complexity of determining whether a given board position is a win for the angel or devil.

${\bullet}$ The Equitable Coloring Problem was solved in the affirmative by András Hajnal and Endre Szemerédi in 1969 while in Budapest. Several strengthenings of the original conjecture, however, are still open.

${\bullet}$ The Star-Height Problem for a binary alphabet was solved fairly quickly in 1966 by Françoise Dejean and Marcel Schützenberger: no finite ${k}$ suffices. This too was the direction of the original conjecture. Still amazingly open, however, is the generalized problem of whether a finite ${k}$ suffices when complement is allowed as a basic regular operation. Then some expressions that seemingly require stars, such as ${a^* b^*}$, can be written without them by complementing: ${(\sim\emptyset) = \Sigma^*}$ and so ${a^* b^* = \sim(\Sigma^* ba \Sigma^*) = \sim((\sim\emptyset)ba(\sim\emptyset)).}$

${\bullet}$ Scheinerman’s Conjecture was proved by Jérémie Chalopin and Daniel Gonçalves in their STOC 2009 paper, “Every Planar Graph is the Intersection Graph of Segments in the Plane (extended abstract).” Still open, however, is the question of doing so using only 4 directional orientations of segments as hinted in our post.

${\bullet}$ The Road-Coloring Problem was also solved recently, in a paper of that title by Avraham Trahtman. His proof is surveyed nicely in this short note by Weifu Wang. There are no other impossible graphs besides those rules out by common divisors of the lengths of their cycles (or by having no cycles). Many problems about the related topic of synchronizing words in finite automata and other similar automata remain open, such as whether cubic upper bounds on their length relative to the number ${n}$ of states can be tightened to match quadratic lower bounds. We may cover this topic in the near future.

## Open Problems

What do you think of the current open problems associated to the ones that were solved?

I flew across the Atlantic last night to join Dick and friends in London and Oxford. Would it be madness if I said I flew during the time change on Halloween to test Gödel’s time-travel equations by communicating with him again via spinning neutrinos at 35,000 feet to avoid the anomaly described in our previous post—but was thwarted by lack of Internet on British Airways crossings? Well, how about this annual time-change ritual which I witnessed every year of my study and research at Merton College, Oxford?

5 Comments leave one →
1. November 2, 2015 5:47 pm

The German translations are mine; I did not have access to the English translation of the play. Left on the cutting-room floor: Janna Levin’s book being among effects seized from Bruce Ivins in the 2008 FBI probe of the 2001 anthrax attacks; the irony with the “Godel Gift” shop that “Gift” is German for poison which is what Gödel was most afraid of (as the play brings out).

November 15, 2015 7:31 am

There is also the graphic novel Logicomix that deals with Gödel’s theories. You might find it interesting!

• November 15, 2015 10:54 pm

I’ve read it! It does not have Gödel as a character though—not even as much as Cantor. This reminds me however that Gödel’s theorems do figure majorly into the plot of the novel The Difference Engine, which is most credited for delineating “Steampunk” and features Charles Babbage and Ada Lovelace as main characters.

You made me wonder whether Russell and Gödel ever talked or corresponded. I found an answer over on Russell’s Facebook page:

Bertrand Russell versus Kurt Gödel:

“I used to go to Einstein’s house, once a week to discuss with him and Gödel and Pauli. These discussions were in some ways disappointing, for, although all three of them were Jews and exiles and, in intention, cosmopolitans, I found that they all had German bias toward metaphysics. Gödel turned out to be an unadulterated Platonist, and apparently believed that an eternal ‘not’ was laid up in heaven, where virtuous logicians might hope to meet it hereafter.”

—Bertrand Russell, The Autobiography of Bertrand Russell (1967–1969), Ch. 13: America, 1938-1944, p. 466.

As a response to this, Gödel wrote:

“As far as the passage about me in Russell’s autobiography is concerned, I have to say first (for the sake of truth) that I am not a Jew (even though I don’t think this question is of any importance), 2.) that the passage gives the wrong impression that I had many discussions with Russell, which was by no means the case (I remember only one). 3.) Concerning my ‘unadulterated’ Platonism, it is no more ‘unadulterated’ than Russell’s own in 1921 when in the Introduction to Mathematical Philosophy he said ‘Logic is concerned with the real world just as truly as zoology, though with its more abstract and general features.’ At that time evidently Russell had met the ‘not’ even in this world, but later on under the influence of Wittgenstein he chose to overlook it”.

• November 17, 2015 12:48 pm

Another recent Gödel-fiction (a really excellent one, as it seems to me), is Yannick Grannec’s The Goddess of Small Victories (2014). Q  Is it really true that Stanley Kubrick and Kurt Gödel corresponded in regard to a planned Kubrick film upon the theme of strong AI? According to Grannec, the answer is “yes” … and her narrative is deeply grounded in archival research.

Further math $\oplus$ literature readings are given (philosopher) Jim Holt’s Lovecraft-titled essay At the Mountains of Mathematics, which will appear in the coming December 3 New York Review of Books. In particular, Holt thoughtfully reviews (mathematician) Michael Harris’ book Mathematics Without Apologies: Portrait of a Problematic Vocation (which is yet another really excellent math-centric book, as it seems to me).

Holt concurs with Harris that the entangled (and often tragic) lives of mathematical luminaries like Noether, Gödel, von Neumann, Mac Lane, and Grothendieck “cry out for fictional treatment (in Harris’ phrase). And it is undoubtedly the case, that many more such narratively constructive $\otimes$ mathematically deconstructive works are in the pipeline.

Nowadays, aren’t all of us STEAM-workers —including the modern-day narrative engineers whose profession was formerly called “writing” — guided by the performative principle that (in Harris’ words as quoted by Holt)

“Knowing an object is tantamount to knowing its relations to all other objects of the same kind”

The swiftly rising tides of immersive fiction and immersive mathematics are acting jointly to help raise our collective 21st century cognition toward a more nearly immersive understanding of the human condition.

Needless to say in this holiday season, books like Grannec’s and Harris’ make thoughtful gifts for the mathematicians in your life … as do subscriptions to the New York Review of Books!