117b – Undecidability and incompleteness – Lecture 7

February 13, 2007

Define essentially undecidable theories as those theories (of arithmetic) that are recursively axiomatizable but such that any recursive extension T is undecidable and therefore incomplete. We showed that if S is essentially undecidable then there are continuum many complete extensions of S, none of which are c.e. The argument gives an example of a complete binary tree recursive in {\bf 0}' with no c.e. branches.

We showed that if \varphi is \Sigma^0_0 then its characteristic function is primitive recursive and that if R is a c.e. relation, then it is the range of a primitive recursive function. We used this to prove Craig’s trick showing that a theory admits a c.e. axiomatization iff it admits a primitive recursive axiomatization.

We defined (numeralwise) representability and binumerability of a relation by a formula in a given theory. Next lecture we will show that there is an essentially undecidable finitely axiomatizable theory that represents all c.e. relations and binumerates all recursive relations. This will be the key to the proof of the incompleteness theorems.


February 8, 2007


Subtitled eine Symphonie des Grauens, `A symphony of horror’, this 1922 German film is very different visually from most other expressionist films from this period. As mentioned during my entry on The cabinet of Doctor Caligari, the imagery (usually expressed in the visual look of the sets of the movie)  plays an important role in expressionist films. It tends to consist of highly artificial sets and there is almost no use of exteriors. In contrast with these common techniques, a large portion of Nosferatu is shot outdoors, and naturalistic images play an important role in the tone and mood of the film. There are some really beautiful scenes of dusk, and a couple of scenes where we see spiders advancing on their prey, or carnivore plants; I imagine these scenes were significantly difficult to achieve with the technical restrictions of the early 1920s.

The DVD commentary contained some nice details that added to my appreciation of the film. For example, night scenes used to be shot during the day, and then the film was painted on, usually with blue tones, to simulate darkness. Again, the musical score in the DVD was recorded specifically for it, and it was very carefully done and a great addition to the overall effect of the story.

Nosferatu is based on Dracula. This is acknowledged during the opening credits, but the names of the main characters, locations, and situations are sufficiently changed so that Enrico Dieckmann and the other producers felt confident there was no need to acquire the rights to use the story. Apparently, they had tried to do so unsuccessfully, and later Stoker’s widow tried to sue the company. Unfortunately for her, Dieckmann’s company had gone bankrupt so instead of money she tried to ensure that all existing copies of the movie were destroyed. Luckily for us, her efforts proved futile.

The story stays closes to Dracula in style and plot. We have therefore an offscreen narrator telling us the events as he has finally been able to understand them, several different fonts used on screen to represent letters or books the characters read, as opposed to dialogue between them which, while present, is kept to a minimum. There are significant differences in how the story ends and on the effect of the vampire (Nosferatu, count Orlock) on the townfolks. Also, instead of London, part of the action is translated to Schleswig-Holstein, Germany.

The relatively recent revival of the vampire genre probably originates with Stephen King’s ‘Salem’s Lot. Clearly inspired by Dracula, Nosferatu is also an acknowledged influence for this novel. We see for example that Barlow, King’s vampire, relocates to Jerusalem’s Lot with the help of a local businessman, Mr. Straker, corresponding to Knock, the real estate agent of the movie.

Many elements of vampire lore are incorporated into the film, some without being mentioned explicitly. Thus, a river stops Orlock from leaving his castle, and only by having other people carry him across can he journey. Also, he cannot enter a place unless their owners invite him in. There are also references to the power of vampires to transmute, and people refer to a werewolf in the area which seems to actually be Orlock himself.

Very well made and sufficiently creepy, this is a really good movie. There were a few odd details with how the story is told. For example, Bulwer, the Van Helsing character, has a very small role and his scenes, though quite beautiful and useful to set the tone of the story, seem completely unnecessary from the point of view of the actual tale. And Hutter, the Harker character, really comes out as a clueless buffoon, although his character is actually more complicated and his relationship with his wife is rather strange and indicative of serious problems and shortcomings on his part. At the end, events happen to him and very little is the result of his own actions.

Nosferatu, played by Max Schreck, is itself a very scary figure, his grotesque features becoming more exagerated as the story progresses. Now I think I should rewatch Shadow of the vampire to see how close Dafoe comes to capture Schreck’s nuances.  

117b – Homework 2 – Solution to problem 3

February 8, 2007

Problem 3 of Homework 2 seems to have been harder than expected (there was a slight inaccuracy in its formulation, which may have somewhat contributed to this difficulty). Here is a reasonably detailed solution to this problem. It looks longer than it actually is, since I spend some time trying to explain where the requirements we use come from.


(There is a small typo on page 5, line 6. Instead of `sup’ it should be `union.’)

117b – Undecidability and incompleteness – Lecture 6

February 8, 2007

We briefly discussed the problem of generalizing the proof of unsolvability of Hilbert’s tenth problem to other (recursive) rings. (For a technical and thorough discussion of this topic, see

We proved a version of the first incompleteness theorem as a consequence of the unsolvability of the tenth problem: If S is any recursive set of axioms strong enough to prove a very weak fragment of arithmetic (the addition and multiplication tables for {\mathbb N} suffice) then either S is not true of {\mathbb N}, or else S is incomplete. The reason is that if S is true of {\mathbb N}, then the set of consequences of S is an undecidable r.e. set (by the unsolvability of the tenth problem), but the set of consequences of a complete theory is decidable.

Additional references:

  • The incompleteness theorems,  by C. Smorynski. In Handbook of mathematical logic, J. Barwise, ed., North-Holland (1977), 821-865.
  • Models of Peano Arithmetic, by R. Kaye. Claredon Press (1991).
  • Aspects of incompleteness, by P. Lindström. Springer (1997).
  • On formally undecidable sentences of Principia Mathematica and related systems (German: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. I.), by K. Gödel. Monatshefte für Mathematik und Physik  38 (1931), 173-198. Reprinted in several places. See for example Collected Works, vol. I, K. Gödel. Oxford University Press (2001).

117b – Undecidability and incompleteness – Lecture 5

February 8, 2007

We completed the proof of the undecidability of Hilbert’s tenth problem, and discussed some of its consequences, tying up with the general theory of the degrees and leading directly into the second part of this topic: The incompleteness theorems.


February 5, 2007


This movie was horrible. Not Soul plane horrible or even My super ex-girlfriend horrible, but I had to pause for a second to come up with those two examples. Unbelievable that Salma Hayek actually appears with a straight face in a small special in the DVD explaining how Penélope Cruz and herself wanted for so long to collaborate, to make this movie together. How insulting! Avoid it like the plague.

World War Z

February 5, 2007

World War Z

Subtitled An oral history of the zombie war, this book was certainly a gratifying surprise. Never having been particularly interested in zombies or horror, I am not sure why I took a look at this book in the first place. What immediately caught my attention, the reason why I decided to give it a try, was the style in which the story is being told. The framework is a series of transcripts of interviews being conducted around the world by a United Nations representative (presumably somebody named Max Brooks) about a decade after the end of the war. It should immediately remind the reader of Studs Terkel’s “The good war”.

I really enjoyed the book, although talking of enjoyment feels incorrect. It is a stark story, with many depressing passages. It is not a horror novel, and there is not more gore here than what you would expect to find in war fiction. What you have instead is snapshots of how people cope with the events being related. Apparently a virus is responsible for the first few cases; although this is not stated explicitly, it seems clear that it is the product of the Chinese chemical warfare industry. The Chinese government tries to keep the first few incidents quiet by removing victims and witnesses, and as a result many people in early stages of infection try to illegally emigrate. There is some description of the pathology of the virus, of which not much is known, but it kills the victim in the traditional sense, while keeping the brain somehow running. The infected “reanimate” and attack and only by destroying the brain can they be stopped. Of course, nobody pays much attention to the first few cases, and by the time concerned voices go public (and are finally believed) it is too late. The book describes effectively how standard war tactics and artillery are of no use, and how people try to escape in huge herds, producing the largest exodus in history (and casualties in the millions). Rather than what I was fearing when I began to read—namely, countless descriptions of zombies overrunning poor families trapped in dark allies—a big part of the gloom of the story comes from how governments and individuals react, of the many terrible things they do to survive or of how meanness and greed are ever-present.

If I had to classify the book as anything, I would say it is a good example of what now is called mundane science-fiction (or is it mundane-science fiction?). There are many neat examples throughout the book of how the events described affect the world, its climate, ecology, economics, politics, language. We see examples of several genuinely new psychiatric disorders and a few unexplained events (the ultimate fate of North Korea is perhaps the most haunting). It is not a comedy by any means (although a few passages are witty and humorous) but apparently is presented in some libraries in the humor section, something I do not understand at all. Quite well researched, Brooks also uses the formal framework to his advantage, so we do not see many technical descriptions or statistics and a few important events are left out of the picture. Something worth mentioning is how many details are told by omission, how we understand some of the events precisely because they are not described. Some of the passages where this device is used are the most effective of the book. The framework Brooks chooses to tell his story presents serious storytelling difficulties: With many voices to present, there is the risk of different voices becoming indistinguishable, but this actually does not happen. And I kept expecting first-person problems, which is how I describe the series of narrative shortcomings almost always present in first person narratives; the most serious of these is to have people say too much, to compensate for the lack of omniscient descriptions. I was glad to find my fears unfounded. 

As surprising as I find typing this, I recommend this book without reservations.