## Archive for **December 2009**

## Coding Russell’s paradox: let’s ask Prof. Wittgenstein.

[This post is only 72% serious]

*“Like all men of the Library, I have traveled in my youth;
I have wandered in search of a book,
perhaps the catalogue of catalogues…”*

Jorge Luis Borges, “The Library of Babel”

…Some of the books in the Library are catalogs that list other books. Some of the catalogs list other catalogs. And some of the catalogs list themselves. Such catalogs are called “funny catalogs”. And those catalogs that don’t list themselves are called “boring”. There is one book in the Library named “A Complete Catalog of All Boring Books”. A boring title indeed … or is it? What’s funny about it, is that it was very easy to write, but quite difficult to read. And until you finish it, you cannot really tell whether it’s funny or boring. So it can provide you entertainment (or boredom) for eternity. It is really the only book you’ll ever need. It doesn’t loose its value even if you throw away all other books in the Library.

class Russell { public List<IEnumerable<object>> Library; public Russell() { Library = new List<IEnumerable<object>>(); Library.Add( //the only book you'll ever need: //a catalog of all non-self-referential catalogs (from catalog in Library where !catalog.Contains(catalog) select catalog).Cast<object>() ); } }

//now let's read it var russell = new Russell(); var paradox = russell.Library[0].ToList();

**Of course, this is cheating! **You get a Stack Overflow simply because of the self-reference, not because of Russell’s paradox! If you remove the NOT operator and try to obtain a genuinely “boring” Complete Catalog of All Funny Books, you’ll still get a Stack Overflow.

Now let’s see what our friend Prof. Wittgenstein has to say on this subject:

“The reason why a function cannot be its own argument is that the sign for a function already contains the prototype of its argument, and it cannot contain itself. For let us suppose that the function F(fx) could be its own argument: in that case there would be a proposition ‘F(F(fx))’, in which the outer function F and the inner function F must have different meanings, since the inner one has the form O(f(x)) and the outer one has the form Y(O(fx)). Only the letter ‘F’ is common to the two functions, but the letter by itself signifies nothing. This immediately becomes clear if instead of ‘F(Fu)’ we write ‘(do) : F(Ou) . Ou = Fu’. That disposes of Russell’s paradox.” (

Tractatus Logico-Philosophicus, 3.333)

Hey, didn’t he cheat as well? I think he cheated even more than I did. He simply banned the self-reference on the language level by proclaiming type invariance. If you noticed, I worked around type invariance of my language by adding that little .Cast<object>(). But I could use covariant collections. Self-reference is not an issue for programming languages. Well, considering that Bertrand Russell himself called Wittgenstein a genius, let’s admit that Wittgenstein correctly understood that the naive set theory was flawed on the syntax level, and that indeed had to be fixed (and was fixed) by restricting the type system.

Believe it or not, I had not been planning to mention Wittgenstein when I started this post. But I found the quote in Wikipedia and couldn’t resist the urge to make fun of Professor.

I was particularly fascinated by the **F(Fu)** part. I think I’ll make this my email signature:

“F(Fu)”– Ludwig Wittgenstein,Tractatus Logico-Philosophicus, 3.333

Speaking of Wikipedia, I ran into the following nonsense at http://en.wikipedia.org/wiki/Russell’s_paradox

“The Barber paradox, in addition to leading to a tidier set theory, has been used twice more with great success: Kurt Gödel proved his incompleteness theorem by formalizing the paradox, and Turing proved the undecidability of the Halting problem (and with that the Entscheidungsproblem) by using the same trick.”

Gödel’s proof has almost nothing to do with the Barber paradox, with the Liar paradox, or with Russell’s paradox. It has to do with Quine’s paradox (http://en.wikipedia.org/wiki/Quine%27s_paradox) which **does not involve any self-reference** on the syntax level. In the same manner, a program that can print out its own source code, is not self-referential.

Too bad I couldn’t find any good anagrams on the subject. And Wittgenstein could probably find meaning in any anagram. Professor even claimed that he could “readily think what Heidegger means”!

Have a consistent and sound New Year! (“Sound” means that no wish comes false) 🙂

## Gödel-Penrose-Franzen: an “eternal golden tree”

Popular texts which describe or exploit Gödel’s Theorems are full of inaccuracies. I’d like to describe one out of many widespread erroneous claims related to Gödel’s Theorems. Not that it’s a particularly important one, but its content is purely mathematical (as opposed to philosophical), and it’s somewhat non-trivial.

The sentence Con(PA) (that means “Peano Arithmetic is consistent”) is proved to be undecidable in PA. So we can add either Con(PA) or its negation ~Con(PA) to Peano Arithmetic as an axiom and obtain new consistent theories. So far so good. “*Let’s keep adding axioms stating consistency or inconsistency of the theory itself to those new theories*” – the authors say – “*and we can build an infinite tree of consistent theories*”.

That is wrong.

Consider the theory PA^{–} = PA + ~Con(PA). It is consistent, and it proves that PA is inconsistent. Let’s add the axiom Con(PA^{–}) to PA^{–} :

PA^{-+} = PA^{–} + Con(PA^{–}).

Is PA^{-+} consistent? **No**. It can prove both Con(PA^{–}) and ~Con(PA^{–}). It proves ~Con(PA^{–}) because PA^{–} itself proves ~Con(PA^{–}). Because it proves ~Con(PA):

PA^{–} |- ~Con(PA) –> PA^{–} |- ~Con(PA^{–}) -> PA^{-+} |- ~Con(PA^{–})

Confused? Let’s go back to PA^{–}. It proves that a part of it (PA) is inconsistent. So it proves its own inconsistency. But didn’t I say that it **is **consistent? Sure it is consistent. But it is **unsound **– it proves a falsehood.

But what about Gödel’s 2nd Theorem? Doesn’t it guarantee that a consistent theory can’t prove/disprove own consistency? Well, not quite. In order to ensure that the theory T + Con(T) is consistent, it is not enough to assume that T is consistent. We need to require some stronger conditions. Without going into details (omega-consistency or 1-consistency), I’ll just say that the semantic property of soundness (not proving any falsehoods) is a sufficient condition. The 2nd Theorem is full of nuances. It is not a simple consequence of the 1st Theorem, as many popular books present it. In essence, the 2nd Theorem relies on the ability of Peano Arithmetic to prove (formally, syntactically, on its own) the equivalence between the Con sentence and the Gödel sentence G. And that is a very subtle matter.

So you can’t really build an “infinite tree of consistent theories” by keeping adding Con and ~Con. You can only build some infinite chains.

It wasn’t a surprise for me to see the above described fallacy in Roger Penrose’s “Shadows of the Mind”. Penrose plays with logic in order to justify his philosophical ideas which are indeed entertaining.

But I was unpleasantly surprised to encounter it in Torkel Franzen’s brilliant “…Incomplete Guide…”. If you don’t believe me, here it is: http://www.amazon.com/Godels-Theorem-Incomplete-Guide-Abuse/dp/1568812388/ (highly recommended), 2.8, page 52, last paragraph. 😦 😦

“Hero gets model” – anagram of “Godel’s theorem”, via Xworder.

## Integer Partitions

Today I give you the algorithm for generating integer partitions, which is used for anagram generation. Behold:

List<int> GetNextPartition(List<int> p) { //mutates the list p to produce the next partition in // reverse lex order, first partition being a single number n,

// and the last one is n ones. int len = p.Count; //there is a tail of ones. count it and cut it off. int tailLen = 0; while(tailLen < len && p[len - tailLen - 1] == 1) { p.RemoveAt(len - tailLen - 1); tailLen++; } if (p.Count == 0) //all values were 1, this is the last partition return null; //all numbers in p are now > 1. //decrement the last (smallest) element; int cutValue = p[p.Count - 1] - 1; p[p.Count - 1] = cutValue; //now we have to add back all the 1s that we cut off int remainder = tailLen + 1; //append the 1s, clumped into groups of non-increasing size. //e.g. 3,1,1,1,1 becomes 2,2,2,1 (which in turn will become 2,2,1,1,1). while (remainder > 0) { if (remainder > cutValue) { p.Add(cutValue); remainder -= cutValue; } else { p.Add(remainder); remainder = 0; } } return p; }

OTHER POSTS IN THE “ROAD TO FULL ANAGRAMS” SERIES:

https://bbzippo.wordpress.com/2009/11/27/inside-xworder-the-road-to-full-anagrams/

https://bbzippo.wordpress.com/2009/12/06/inside-xworder-the-road-to-full-anagrams-2/

https://bbzippo.wordpress.com/2009/12/18/integer-partitions/

https://bbzippo.wordpress.com/2010/01/06/generating-combinations/

## Descriptive names considered harmful

Ten years ago I was able to understand mathematical texts so much better than I’m able to now. And it is neither AD, nor ADD, or tequila that I blame. I blame descriptive identifier names in program code. I have become spoiled by them. I expect to see long and descriptive identifiers in equations rather than single letters with overload resolution based on typography. And since I’m also spoiled by intelligent code editors, I expect to be able to trace a symbol’s definition without having to go five pages back and re-reading them.

For instance, I haven’t been able to understand what the heck the Einstein field equation really means, no matter how many times and how many texts I read. Let me tell you that by convention, a boldface **R **is the Riemann curvature. But sometimes it’s written as R_{abcd}. And R_{ab} is the Ricci curvature. But when you see just an R (not bold and without indices) – it is the scalar curvature. Needless to say that all those Rs are closely related, and if you confuse some of them just for a second – you fail.

So in order to restore justice I want a programming language that differentiates names by typography (bold, italic, script, double struck, lower and upper indexes, Greek and Gothic alphabets, some Hebrew too) and has context-based overload resolution. And it should be named ℂ^{ω} or something.

## Caching pattern

The following pattern is wrong:

(pseudocode) if GetDataFromCache() is Nothing then CacheData(GetDataFromDatabase()); return GetDataFromCache();

The data could be removed from cache between the two operators and the code will return Nothing. This will likely cause hard to debug NullReferenceExceptions.

This is not improbable in web apps. The cache manager uses heuristics based on many factors. When the app is under high load, items may be removed from cache right after they are inserted. The correct pattern is

data = GetDataFromCache(); if data is Nothing then { data = GetDataFromDatabase() CacheData(data); } return data;

Note that in this case the object is always referenced and even if it gets removed from cache we don’t lose it

## Large Hadron Collider

“Angel hail Lord record” is an anagram of LHC (via Xworder).

Not sure why the mainstream media isn’t reporting this, but the LHC has already smashed a few protons at a record energy of 2.36 TeV: http://atlas.web.cern.ch/Atlas/public/EVTDISPLAY/events.html

## Zen of Requirements Definition

namespace Mind { class Hand { void Clap() {

無門曰 A young Analyst invited a Design Master for a consultation. They were having a tea ceremony and the Analyst was asking the Master questions:

– How do I analyze the Subject Area?

– Subject Area is Emptiness. How can one analyze Emptiness?

– But how do I build Models?!

– Models are forms of Emptiness in Customers minds. It’s like tea: it has different forms when in a cup and when in a pot. Do you understand?

– Yes! You are saying that the subject area doesn’t matter and only requirements matter.

The Master took the teapot and started pouring hot tea onto the Analyst’s pants.

– Now, do you understand?

– Yes! Requirements are important and the subject area is important too!

Then the Master dropped the teapot on the floor. It broke.

At that moment the Analyst got enlightened.