The slashdot experience

An SVG-ified version of Image:SlashdotEffectGr...
Image via Wikipedia

Last night I submitted a story on this blog – about P=NP – to Slashdot and today the submission was accepted and in a few hours I have had perhaps five times more visitors than in the previous two and a half months.

But, thanks to there was no “slashdotting” – instead the site has stayed up and running throughout.

Slashdot has a reputation for flame wars and ignorance, but actually the discussion has been great – I wish I could get a few more articles from the blog on to /. as then I would benefit from the clever people who hang out there: yes there is a lot of noise, but there’s also good signal.

The other thing it has reminded me of is the need to avoid imprecision in scientific writing. A few flames have been aimed at me and articles on the blog: one item being called horrible when, actually, what I think what was really wrong was a few corners cut in an effort to make the exposition a little less cluttered.


Gödel, Turing and decidability

Portrait of Kurt Gödel, one of the most signif...
Image via Wikipedia

I am still wandering around in the world opened to me by The Annotated Turing
– perhaps a little lost, but I have been reading some guide books.

The most recent of these has been Gödel’s Proof which gives a gentle(ish) introduction to Gödel’s incompleteness theorem.

This is a short, but fascinating book that I repeatedly made the mistake of trying to read when tired or not able to give it my full attention (eg on a flight from London to Budapest last week when three days of hard work had really taken it out of me). But I finally managed to finish it last night.

I think the really startling point it makes – which admittedly Charles Petzold’s book also makes but I didn’t fully grasp at the time – is about the nature of the human mind.

Gödel’s theorem states that no consistent system of axioms whose theorems can be listed by an “effective procedure” (such as a computer program) is capable of proving all facts about the natural numbers.

Before I read the book I had not really thought about what this meant: after all Turing and Church had shown that most numbers/mathematical problems were not computable and so this seemed of a part with that conclusion.

But the key thing here is that metamathematics can show the correctness of theorems that axiomatic proofs cannot. In other words – I think – that computer programs are actually a poor model of our ability to solve mathematical problems.

Did not quite waste the whole weekend

Common connectors on a Graphics card. Left to ...
Image via Wikipedia

I vowed not to write about politics here, so I won’t. But the Irish election proved an exciting distraction all weekend. Still, I did manage to get somethings done:

  • Fitted a new graphics card on the machine I am using now (the previous one seemed to simply die when I tried to access the “Power Mizer” facilities on the card – Linux users of the nvidia proprietary drivers be warned;
  • Fitted a new heat sink on my kids’ Linux box – they will no longer have the excuse they have to use this (my) computer because theirs has died from overheating (plus they have about 5000 more MIPS on their machine anyway);
  • Wrote to the users of the Inkling prediction market I had started on Vladimir Romanov’s P=NP proposal to tell them it was dead (for now). I doubt many were surprised – the market rated the chances of his “proof” being correct as 0.09% when I cashed it out.
  • Started reading Alone in Berlin
  • And last, but by no means least, actually completed a draft of my MSc proposal. I’ll have to read through the text looking for spelling errors and fix up all the references (I discovered the ability to import from BibTeX via uses of Google Scholar this weekend so no more typing by hand).

I am really pleased about that last one. The Irish election results weren’t so bad either.

No proof of P=NP after all (yet?)

Diagram of complexity classes provided that P ...
Image via Wikipedia

Vladimir Romanov has conceded that his published “proof” of P=NP is flawed and requires further work.

So, it seems internet commerce is safe for now. But Romanov is not throwing in the towel:

Thank you for your attention to my work. You’d better suspend your investigations.
A shortcoming possibly exists in the filtration procedure which requires an amendment.

A book to buy? P, NP, and NP-Completeness: The Basics of Computational Complexity – I admit to being tempted.

Time to ditch Firefox?

The results of the Acid3 test on Google Chrome 4.0
Image via Wikipedia

Just about every internet user, even if they have never used Firefox, owes the Mozilla Foundation an enormous amount for the creation of Firefox.

It’s injection of competition back into the mass browser market stimulated a new drive towards standards and speed that has made a huge difference to all users: Internet Explorer 6 came out in 2001 and languished, largely unimproved until Firefox’s success finally prompted a new version of IE, in 2006 and since then competition has been fierce.

But is Firefox really up to it any more? I have just tried the javascript bench marks on and my copy of Firefox (it is still my browser of choice at home) scored just 89 on average over 10 runs. Google Chrome managed 313 on the same box (a now quite old Pentium D).

And, of course, Chrome is more standards compliant. It doesn’t quite smoothly progress to 100/100 on the Acid 3 test – but it does get there, while my version of Firefox only manages 94/100.

Lifecycle of a Linux page … 2

Took another day’s worth of work to get this right … last night’s effort had a few mistakes in it as well as being not such a great piece of Metapost. So here’s the correct version:

Lifecycle of a pageframe in Linux

As before, the Metapost of this image is available at

Changes at Foyles

The venerable Foyles bookshop on the west side...
Image via Wikipedia

I remember Foyles bookshop in London when, perhaps twenty years ago, it was a warren of books seemingly piled one on top of another and with little order beyond the basic categorisation by subject (that is how it felt anyway).

Buying a book was a rigmarole – you got a chit for the book at one counter, paid at another and then went back to collect the book.

That contributed to the sense that the owners treated their staff abysmally – they seemingly could not trust most of them to run a cash register. I did not like the place and stayed away for many years.

When I did go back, some years ago now, the place was transformed – it really is the best bookshop in London and it is always hard to resist going in there when I pass.

But, I have to be honest. While I maybe buy a book or two there on four or five times a year, more often than not I seem to use its computer section as a sort of glorified library – checking which books look good before ordering them online from Amazon.

Ordering online is not always cheaper in fact – for low volume books Foyles can even turn out cheaper or at least faster at no extra cost as no postage has to be paid. But anything with any sort of volume is usually 50 pence or more cheaper and ordering a few makes the saving worthwhile.

So what to make of the fact they have moved the computer section downstairs to the basement seemingly because more and more computer book buyers do the same and so the computer books cannot be given the more valued retail space upstairs? Should I purchase a book or two just to keep the library open?

Maybe. Because one good thing that has seemingly come from the move to the basement is that there is more shelf space available and, so it seems anyway, more stock to browse.

That is very useful – I was thinking of buying The Little Schemer but having been able to give it a quick browse I can see it does not really fulfil any need for me (I was hoping for a book that would look at the history/thinking behind this dialect of Lisp rather than a cookbook type presentation).

So, what should I plough that saving into?

Slow progress on the project proposal

Crashed payphone -- Linux kernel panic

I have been making slow progress on my project proposal – some times it has felt like a mirage: the further I go the further away the real target seems to be.

But I am getting there – though I seem to have written five pages of dense type explaining how Linux paging developed and works without actually describing any problems or what I intend to do about them.

Well, the plan now – and I am writing this down as an aide memoire/encouragement to actually do it is to move on from where I am now – describing the 2Q-like LRU lists in the Linux kernel, to some of the problems, describing the alternative “working set” approach (eg as used in Windows NT and before than VMS) and then some of the strategies and tactics that could be used in Linux to apply it.


LaTeX frustration…

Knowledge of German as a foreign language (sec...
Image via Wikipedia

Anyone who works on software development and in the FOSS world generally is used to seeing books and documentation in English. It is certainly a great advantage to be a fluent speaker and reader.

But it is not always the case – as I have just found out.

Right now I have returned to writing my MSc project proposal and that means back to using the power of LyX and LaTeX. But with great power comes great complexity and it can be tough navigating all of this.

So I discovered there is an O’Reilly “Hacks” book for LaTeX – LaTeX Hacks.

Great! I was going to order it without even bothering to read a review, so sure was I that it would be helpful and useful: until I discovered it was in German and there is no sign of an English translation.

To make matters worse, it seems that the O’Reilly quick reference – LaTeX – is also auf Deutsch.

And there is even 100 neue Latex Hacks

This all has an odd, and unsettling feel to it. A century ago German domination of the physical and mathematical sciences was near-complete. Think of 1905 and Einstein just for starters.

But since the tragedy and disaster of Hitler we are used to thinking of the Germans as great engineers but the US clearly as the world’s leading centre of scientific research. And when a threat to that is identified it is usually seen as being from China (as Barack Obama said only a few weeks ago in his state of the union address). But maybe the LaTeX domination of Germany suggests there is life in the old world yet.

Either that or O’Reilly need to pull their fingers out on translating this stuff.

(The graph shows the numbers of people in EU members states who speak German as a foreign or second language: I did a year of it at High School but would not claim to know much beyond some very basic vocabulary and grammar).