Chaitin’s books online

A few weeks ago I heard that Chaitin tries to put everything he has ever published online, and most of the stuff via arXiv. Over the weekend I gave it sometime and found some of his books:

I own “Meta Math!“. I bought it by chance. While in the bookstore, I opened it and stumbled upon LISP code. This is a really nice book. It is a personal log of Chaitin‘s career, an introduction to Kolmogorov complexity0 (which was independently invented by Chaitin too), algorithmic information theory, thinking about randomness (and in a way first presented to me years ago by a long time friend), LISP1, useful comments on NKS2, Polya‘s “How to Solve It!” and an introduction to the thought of Leibniz3.

Of course the book has irritating parts: Having invented a field independently of Kolmogorov, somehow puts you in the shadow of the man and Chaitin constantly tries to get out of the shadow and stand not on the shoulders of Turing and Goedel but next to them (when in fact such effort is not needed).

I loved the book4. It is the kind of book that reminds you why you loved Mathematics. Even Chaitin’s personal effort to stress the importance of his work (that annoys many) contributes to this. For he unquestionably loves Mathematics.

(Must make time and read “The Limits of Mathematics”; Time there is not…)


[0] – More about it at “An introduction to Kolmogorov complexity“.

[1] – Link to the Lisp interpreter that Chaitin has developed for his needs.

[2] – See also this presentation on NKS by S. Wolfram.

[3] – An essay on Leibniz by Chaitin.

[4] – I also loved “Title: Algorithmic information theory: Some recollections“.

Poor man’s milter-ahead

I have blogged before that the reason that I like MIMEDefang is that it gives the Postmaster a Perl interpreter (a programming language that is) and a library of functions that can be used to filter and manipulate incoming and outgoing email.

Of the functions available I believe that md_check_against_smtp_server() deserves special mention since it can be used to quickly implement a poor man’s milter-ahead or milter-sender. Of course milter-ahead implements many features (caching among others), but with some effort most (if not all) of the functionality can be implemented withing mimedefang-filter.

Then again, milter-ahead does not cost much (€90) even for small organizations, so the not invented here syndrome can be supressed.

Plato’s Republic

A friend suggested that I could use The Book Depository as an Amazon alternative, which was a very helpful tip especially for books over €50. As it happens to many who buy books from online bookstores, sometimes what you get is not what you ordered. In my case I had ordered “The Travelling Salesman Problem” and got “Plato’s Republic“. After some friction with their support service (Amazon is way better in this kind of issues) the order was completed and The Book Depository told me that I could keep “Plato’s Republic” too.

Now since it is highly unlikely that I will ever find time to read this version, I will gladly send it to anyone interested. If nobody shows any interest, I will donate it to a library.

This is a weekend’s work

More often than I would expect, I run into conversations about certain IT and web related projects where someone will say, with a bit of authority:

– This is not a big deal! It can be done over the weekend.

Once I was told that a certain feature that needed to be implemented was “only two hours work”! And this came from a person that had no knowledge of the software stack in use.

Another time upon protesting (and basically saying “Put your money where your mouth is!”) I got the best exit:

– I did not say that I can do it over the weekend. I said that it is possible to be done in a weekend by you!

Like I do not have better things to do in my weekends…

So if you have ever claimed that something is possible over a weekend (and can be delivered as a working beta) the weekend is not far. Shut up and prove your point. You can even use Friday afternoon as extra time.

But on Monday please call the guy that said it will take him a week, a month or more and apologize.

Practical Reusable Unix Software

(I think I bought mine sometime in 1997. The price tag says £26.50 which means that I had UrBaN buy it for me.)

Το βιβλίο γράφτηκε το 1995 και είναι ενδεικτικό των εργαλείων, αλλά και της φιλοσοφίας που επικρατούσε στην AT&T Research εκείνη την εποχή. Χάρη σε αυτό έμαθα για το graphviz (που με βοήθησε να φτιάξω ένα από τους πρώτους χάρτες του 6BONE αλλά και του irc.gr), το UWIN (οπότε και κατάφερα ένα από τα πρώτα native ports του netcat), τη vmalloc (που πάντα ήταν χρήσιμη όταν κάποιο πρόγραμμα είχε προβλήματα memory allocation – π.χ. το CLP(R) με κάποιες GLIBC της εποχής). Το σημαντικότερο όμως που μπορεί να προσφέρει αυτό το βιβλίο ακόμα και σήμερα, 14 χρόνια μετά και με μερικά από τα εργαλεία που παρουσιάζει όχι και τόσο χρήσιμα, είναι ο τρόπος σκέψης: ορισμός προβλήματος, προσέγγιση, αρχιτεκτονική και λύση. Και αυτά in a system administrator’s way.

Το βιβλίο είναι διαθέσιμο σε μορφή PDF και το software που περιγράφει (αλλά και άλλο νεώτερο) βρίσκεται στο http://www.research.att.com/sw/tools

[via]

Scale-Free Networks: A Decade and Beyond

Barry Wellman posted on SOCNET a link to “Scale-Free Networks: A Decade and Beyond” by Albert-László Barabási. I quote two excerpts that I find interesting:

“the scale-free nature of networks of key scientific interest, from protein interactions to social networks and from the network of interlinked documents that make up the WWW to the interconnected hardware behind the Internet, has been established beyond doubt“

Regarding the scale-free nature of the Internet much has been written. However lately I came across two papers that specifically refute Barabási’s opinion on the matter:

  • Mathematics and the Internet: A Source of Enormous Confusion and Great Potential [pdf]
  • The ‘‘robust yet fragile’’ nature of the Internet [pdf]

So at least for the Internet the scale-free nature has not been established beyond doubt (The links for these papers were posted on Interesting-People). If anyone wishes to dive more into Internet topology stuff (and related mathematics) go read them! They provide a wealth of references too.

However, the second excerpt that I singled out is a prediction and a fascinating one I must say:

“If I dare to make a prediction for the next decade, it this: Thanks to the proliferation of the many electronic devices that we use on a daily basis, from cell phones to the Global Positioning Systems and the Internet, that capture everything from our communications to our whereabouts, the complex system that we are most likely to tackle first in a truly quantitative fashion may not be the cell or the Internet but rather society itself.”

Hmm… I think we know what the (long term) target of the next papers by Barabási’s team will be.

A glimpse at Christos H. Papadimitriou

Via Machinations we learn that the current issue (Volume 3, Issue 2, May 2009) of Computer Science Review is devoted to celebrating the research contributions of Christos H. Papadimitriou. The first article “A glimpse at Christos H. Papadimitriou” (by Marios Mavronicolas and Paul G. Spirakis) has a lot of information not only on Papadimitriou’s path, but also on how CS evolved in Greece and how it was influenced by Papadimitriou*. This is a must read, especially if you are a NTUA student which means that there are at least two people that you can go to and ask for more (or better yet work with them). UoA students can ask Elias Koutsoupias.

As the authors say, there is stuff missing from the paper, since a 30+ years fruitful career cannot be covered in a few pages. But since both the fact that the TSP is a recurring theme in his research and the late Kanellakis are mentioned, I think their work on the ATSP should have been mentioned. What can I say, I’ve grown to a TSP junkie the last few years.

Also, for those interested, in the same issue Costis Daskalakis surveys their recent joint work on Nash Equilibria and complexity.

P.S. Elsevier told me that a hardcopy of this issue costs €66.50 for Greece, so it is best to go to your University’s library and access it online.

Related posts:


[*] – For example when two guys asked him right after graduation (~1982) on what to do, his advice was to work with databases (and I know this first hand).

ksh script template

Dave Taylor (author of elm) asked:

need to write my Linux Journal shell script programming column and am sitting here without a topic/script in mind. Suggestions?

My suggestion was to write about scriptt.sh which I first encountered in this BigAdmin article:

Writing a script template with the most frequently used functions one time and reusing it for your scripts makes life easier. Doing this as shell script instead of, for example, perl, ensures that you can just copy the script to a new machine and have it work.