Uncertainity Principle(s)

Most people know a formulation of the uncertainity principle in quantum mechanics (by Heisenberg), where it basically gives a bound (in terms of the standard deviations of ~) for simultaneous measurements of complementary properties (i.e. measurement operators with non-negative commutator).

There are a number of other places where the principce turns up. It comes from an application of the cauchy schwarz inequality to the fourier transformation. Here's a set of (german) slides from a lecture. Recently Terry Tao posted on a a formulation of the principle due to Mongomery, which has applications in analytic number theory.

Reading Speed: Chinese vs English

I always wondered about mankind's languages and writing systems, one of the reasons I looked into Lojban (quite) a while ago. In an earlier post about writing systems I expressed my fascination about non-linear systems. But even with linear systems, we have alphabetic, syllabic and logographic systems. But it turns out the our systems are optimal in the sense that our cognitive abilities won't let us process more optimized systems, at least that is indicated by a study on reading speed with Chinese vs English - two major examples of logographic and alphabetic writing systems.

Complexity Theory related surveys

Some complexity related survey-ish papers:
A CACM article from September 2009 titled "The status of the P versus NP problem" available here.

Mentioned in the above survey, two more interesting papers:

• an article by Scott Aaronson on the independence of the P vs. NP question
• a paper by Impagliazzo giving a personal view on the average case complexity

I did not have enough time to read more of the cited works in the CACM article, but I'll add more as I have time to read it.

Coalgebraic Logic

Due to recent needs, I looked up some stuff on coalgebraic logic, a generalization of modal logics. If you're unfimiliar with the notion of coalgebras, read the good 'tutorial on coalgebras and coinduction' by Jacobs and Rutten.
I keep extending this post to contain a small collection of useful reading material, staring with this list:

• Moss - Coalgebraic Logic

For modal logics per se, have a look at the handbook of modal logics.

Random Numbers and Certified Randomness

A rather recent edition of the ACM TechNews contained a short report/link on a German team which developed a hardware random number generator [1], that

uses an extra layer of randomness by making a computer memory element, a flip-flop, twitch randomly between its two states 1 or 0. Immediately prior to the switch, the flip-flop is in a "metastable state" where its behaviour cannot be predicted. At the end of the metastable state, the contents of the memory are purely random.

Whereas this device gives me more security, it does not solve the problem of someone sending me supposedly "random numbers" which he might have prepared in advance to even pass statistical tests. A neat solution is provided by quantum mechanics which allows to check randomness of numbers via the violation of the Bell inequality [2] using entangled states.


[1] "A meta-level true random number generator" in Int. J. Critical Computer-Based Systems, 2010, 1, 267-279

[2] Random Numbers Certified by Bell's Theorem

Banach-Tarski-Theorem

I wonder why I did not post this when I first read it, but because I just crossed that topic again, here is a nice, even though not formal and not technical sketch of a proof of the banach tarski theorem at irregular webcomic.

Completness and compactness theorems

Nice article with draft of proofs:

http://terrytao.wordpress.com/2009/04/10/the-completeness-and-compactness-theorems-of-first-order-logic/

Speed math game

http://www.jimmyr.com/blog/speed_math.swf

Are you a genius, too? There are some videos on youtube teaching how to apply the speed arithmetic method the author uses, but you don't need to use in order to get all stars in that game.