{\huge Ghosts in Princeton}

Kurt Gödel in popular culture and answers to Thursday's problems \vspace{.5in}

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 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:

\includegraphics[width=3.5in]{GodelStore.jpg}

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?''

$latex {\bullet}&fg=000000$ The Angel Problem is a win for the angel even with $latex {k=2}&fg=000000$. 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 $latex {k=2}&fg=000000$ 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 ($latex {k=1}&fg=000000$ in 3D) using the $latex {z=0}&fg=000000$ and $latex {z=1}&fg=000000$ 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.

$latex {\bullet}&fg=000000$ 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.

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

$latex {\bullet}&fg=000000$ Scheinerman's Conjecture was proved by Jérémie Chalopin and Daniel Gon\c{c}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.

$latex {\bullet}&fg=000000$ 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 $latex {n}&fg=000000$ 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? Well how bout this annual time-change ritual which I witnessed every year of my study and research at Merton College, Oxford?