Saturday, December 20, 2008


A recent Ted talk, by Susan Blackmore, discusses the idea of memetics. She offers the best explanation of memetics that I've heard yet, and goes on to make the claim that the idea of evolution (Darwin's) is the best idea anyone ever had. I really have to agree with her: it is a beautifully elegant way to describe an incredibly powerful process. She also lays out a very concise description of the requirements for evolution, which I will paraphrase:

"A system in which information is copied, with variance, followed by selection, must produce evolution."

For clarity, a definition of terms is warrented. Evolution is a universal process, and is not specific to biology, so I'll use the word "unit" rather than "organism" to describe a packet of information, which participates in the evolutionary process. I use the word "population" to describe a collection of units (similar to the idea of "species").

Evolution is the process of adaptation to a selection process. Multiple diverse units, where each is equally adapted to a static selection process, are no more or less evolved with respect to each other. Winners and losers emerge only when the selection process changes, thus "evolving" the population.

Variance means that the information is not copied perfectly, but there is some (low) probability of a small copying error, during each copy operation. If the copying process leads to too high of an error rate, then the new units will be so different from their parents that they will be poorly adapted to the subsequent selection process.

Selection is the process by which units are selected for inclusion in the subsequent population, as a function of their characteristics. The selection process must be slowly time varying with respect to the copying rate of the units, in order for them to adapt. Otherwise, a new set of copies may be adapted to a very different (older) selection process than the one currently in place. A perfectly static selection process (one which does not change over time) will not result in evolution. The units will adapt to it, and then will remain equally adapted from then on. Their information may appear to change over time, due to the gradual accumulation of copying errors, but they will remain equally adapted to the selection process. A biologist might say that this is an example where the genotype varies, but produces a static phenotype. Of course, there may be instances where multiple phenotypes are equally adapted to a given selection process, but that's more detail than I want to get into. Periods of selection stasis lead to the accumulation of variance. If the selection process suddenly changes, a population's variance gives it the resources to quickly adapt to the new selection process, thus squeezing it through the "evolutionary bottleneck". The absence of sufficient variance, in such a scenario, results in extinction.

Friday, December 12, 2008

P vs NP for dummies

One of the "great" outstanding problems in computer science is the question of P vs NP. In layman's terms, P represents all problems whose solution can be found in polynomial time. NP represents all problems whose solutions can be verified in polynomial time. Polynomial time just means that the time to find the solution has a polynomial relationship with the size of the problem. For instance, a particularly terrible sorting algorithm may take n^2 seconds to sort an arbitrary list of names, where n is the number of names in the list. This is a second-order polynomial of the form a+b*n+c*n^2, where a = b = 0, and c = 1.

The question, does N = NP? asks whether all problems which can be solved in polynomial time, can also be verified in polynomial time. Back to the list sorting example, verifying that a list is indeed sorted properly may only take n seconds, so this is also polynomial. In this single example, the problem was solvable in polynomial time, and its solution was verified in polynomial time.

For further reading, take a look at Wikipedia's entry on this topic. It also addresses the topics of NP-hard and NP-complete.

Tuesday, December 9, 2008

Crap is King

I've heard this song many times, but tonight was the first time I truly listened to it. I never realized it was a critique of mass media, specifically, journalism. Due to mass-media consolidation, it isn't too often that you hear lyrics these days which criticize such powerful institutions. I hope that the internet can one day support a fluorishing "ecosystem" of musical expression, where critical messages can be conveyed un-molested by the powers that be. Recent legislation has been preventing this from happening, and I'm uncertain as to the potential of current movements to enact any meaningful change.