Saturday, September 30, 2006

A mixed hypothesis

Here follows a mixed hypothesis I have devised out of some previous posts, Running Man, Toba Catastrophe and Aquatic Mind.

Studying the conditions of the Japanese pearl divers gives good insight about how life could have been for an early human species living near the coast foraging from the sea. Interestingly the Japanese considers women better suited for diving as they can withstand the cold better with their extra layer of fat, also they were considered to be able to hold their breath longer.

Considering an early sea foraging hominid, maybe it was the women that were the primary sea foragers, diving for abalone and shellfish, and men kept more to the land?

When diving just adding a few feet to the maximum depth can make a huge difference regarding what can be foraged from the sea. This would probably cause their fur to gradually flatten and align itself nicely along the body to minimize drag and allow deeper dives.

Water drains heat to a much greater extent than air and keeping heat in is a major concern for marine mammals. Most marine mammals have kept their fur, and developed body fat. Same thing happened to the hominid group, they developed subcutaneous fat. To be able to dive and hold their breath for extended periods of time they needed to ditch panting as heat regulating mechanism. As they still spent great deal of time on land their eccrine glands developed into a water cooling mechanism.

We are now at ~70000 years ago. The supervulcano Toba erupts and throws many species into population bottlenecks. Life is really hard, especially at the top of the food chain. Many of the human species are decimated so bad that they eventually will go under, they were too dependant on finding prey inland. The semi-aquatic group were lucky though. Their extra income from the sea made them get through the most terrible years and turned them from being a very minor hominid group to the major group, about 2000 individuals.

Many years after the disaster the earth starts to recuperate. The suffocating clouds of ash and sulphur dioxide abides and the sun brings new life to the planet. Now many species find great opportunities arising. The semi-aquatic hominids find that hunting inland is easy. They find that they even can catch prey just by being stubborn and keep running. The prey gets overheated before they do because they have a more sophisticated cooling mechanism.

Spending less and less time in water they find that they don't need their fur anymore. Their fat keeps them warm at night and they can dissipate more heat without the fur when running. The little fur that is left shows the same streamlined pattern as when it was designed for gliding through water.

The gender differences regarding the sea foraging remains and is further accentuated by sexual selection.

Regarding the population bottleneck of the human species 70000 years ago we see that tracing the Y-Chromosome back in time we arrive at that Y-Chromosomal Adam lived between 60000 and 90000 years ago. This is also an indicator of a population bottleneck at this time. Fossil finds also seem to strengthen this hypothesis about a bottleneck.

Friday, September 29, 2006

Meet the Straw Man


Parallel with science there is bad science(BS). With BS I mean the collection of articles that for some reason tries to look like science but don't follow through. You can spot BS quite easily, these articles use 'Theorem' and 'Fallacy' instead of 'I am right' and 'You are wrong'. I'm not sure if they use it to deceive the real scientists or people who don't know science but recognizes the buzz words.

In mathematics you prove a theorem using definitions and axioms. If you disagree with the definitions or axioms then all is fine, if you agree the theorems follow as a consequence. You will spot BS theorems by the fact that the proof part is replaced by rambling and the definitions are nowhere to be seen.

Most sciences don't use theorems at all, mainly because nothing actually can be proven. In those sciences you often have an abundance of theories and ideas and the correctness is decided by majority of vote. The more vague the field the more theories. Physics for example don't state theorems, it's based on empirical knowledge. Physics state equations. A proper equation is generally a formula that states observed facts and is thus empirically true. And a formula is something that obeys the rules of a syntax. In this sense, E = mc^2 is a formula, but so is E = mc^3. Consequently physics has several theories explaining the same things, physicists are not bothered(too much...) about using several different theories in parallel. Sometimes light is treated as a wave and sometimes it is a particle depending on what you want to calculate.

An observation regarding this is that the more vague the field, the more problems the scientists seem to have with accepting several theories at once. I think this has to do with pragmatism. Physics is used in practice to get things done and at the same time provides answers to existential questions. When a field has no practical use only the existential aspect is left which leads to a mentality of belief. Regarding beliefs it is often hard for an outsider to understand what a specific disagreement is about. There is one God but your God is the wrong God because you call him A when he actually is called B. Saying there is no God at all is not as bad as giving him the wrong name, it is only when you enter the election and gather voters that you are a threat.

It is in this circus of vote gathering that the practice of pointing out fallacies has become popular. The formal use of the term fallacy comes from the field of logic. For example stating 'if A then B' and then observing B, it is a logical fallacy to conclude that A must be true. If it rains the grass get wet, observing that the grass is wet and then concluding that it has rained is false. This also applies to set theory, when you say 'All cats have four legs', and then after observing a creature with four legs concluding that it must be a cat is a logical fallacy. Statements are either true or false in logic(although there are paradoxes as in all complete systems as shown by Gödel).

The language of logic appeal to everyone involved in arguments and wish they could throw the fallacy argument at their opponent in a discussion. Detecting a fallacy is not that easy though, normally it is not as straightforward as the cat example above. So what do you do? You expand the list of fallacies and make them more usable. This reminds me of how New Agers have taken over the word energy. When a word gets credibility just hijack it for your own purposes. Therefore the list of fallacies has increased beyond logic. Many scientific fields have gotten their own favorites. When used right those fallacies can be very powerful but unfortunately many fallacies are very vague in their description, the consequence when you are moving away from the formal language of logic.You can find many articles relying on those fallacies in trying to debunk other theories by using them, this is very easy if you get your mind to it and use them in a sloppy way.

Creationists(Believers of a creator) tries to debunk evolution by using the fallacy of "Begging the question" or "Petitio principii" which is it's fancy name. They argue that saying "survival of the fittest" is a clean cut example of the fallacy as fittest means he who actually survive. Very true, a clean cut example of circular reasoning. Is this bad news for evolution? Not really, an interesting thing about "Begging the question" is that this does not say anything about the validity of a statement, only that it is meaningless taken out of it's context. Using a fallacy may very well be a fallacy itself.

These type of fallacies must be used with reason because there is no formalism behind them. Used in a bad way it becomes deceiving rhetoric. Sometimes you see a long list of fallacies that are supposed to apply to arguments by proponents of a certain theory, no examples, just an appeal to bow before the power of logic. Using the language of logic and the language of mathematics in many cases is just a desperate effort to lend credibility to arguments the writer thinks needs some artificial leverage. Just putting Theorem in front of a statement does not make it a theorem. So, next time you encounter the Straw Man there is a good chance you are reading BS.

Thursday, September 28, 2006

The Running Man

When time comes for the Olympics many scientific magazines likes to show how inferior humans are compared to other animals. High jumpers would not stand a chance against the Snow Leopard. Long jumpers would be an easy match for the kangaroo. Speed runners would be crushed by the cheetah and swimming fast certainly is not something humans do well compared to the Tuna. But there is one thing that humans do really well that would earn a medal at the animal Olympics.

Humans have great stamina and can outrun almost any animal over long distances. This is actually one of the benefits you get from being bipedal. Bipedalism is more energy conserving than walking on four legs. We have abundant sweat glands(eccrine) for cooling, those glands also have an endurance feature as they can keep on producing sweat without any recharging phase. This thermal eccrine system in humans is quite unique. Our Achilles tendons, our big knee joints and our muscular glutei maximi makes us very well designed for long distance running.

How would a man fair against a horse over a distance of say 22miles? Actually there is a yearly competition between man and horse in the Welsh village of Llanwrtyd Wells. In June 2004, for the first time ever, the human won.

Among the people who rejoiced at this outcome were University of Utah biologist Dennis Bramble and Harvard University paleoanthropologist Daniel Lieberman. Bramble had noticed that humans certainly are not adapted for speed, humans are comparably pitifully slow, a chimp can run at 60km/h while humans tops at 30km/h. So we certainly didn't go bipedal for speed. Also, bipedal speed runners all have tails. The tail is a major balancing organ for those animals.Bramble says.

In the whole history of vertebrates on Earth—the whole history—humans are the only striding biped that's a runner that's tailless.

So when did we become marathon runners? Most scientists agree that the chimp like Lucy, the 3.2-million-year-old hominid, couldn't have been a good endurance runner. Homo erectus(40.000-1.8million years ago) on the other hand had much longer legs, he had the disposition to run, but did he have the eccrine thermal regulation of modern humans?

Many animals use panting for heat regulation, this means increasing the breathing frequency to vent out heat. Experiments on chimpanzees show that they increase their breathing frequency when temperature increase, and sweat very little. This process has two major disadvantages. It needs muscular work, which itself increases heat, and it causes an excess loss of carbon dioxide from the lungs which in turn cause alkalosis. Heavily panting animals regularly become severely alkalotic. Cooling by sweating has the disadvantage that you loose precious water. This means that animals that sweat a lot need access to water to a greater extent than panting animals.

For long distance running the thermal regulation issue is very important, it is overheating that causes many animals to stop running. Suppose hominids started to travel long distances. Moving long distances gives you the advantage to adapt to changing environments i.e. move to areas that provide better opportunities for survival.But in this case, why give up panting? Wolves wander long distances and use panting for heat regulation which reduces their need for water.

Many animals can not control their breathing, studying panting animals you see that they follow a certain pattern, the respiratory system is elastic and has a natural frequency of oscillation. If it were not so the panting mechanism would generate more heat than it dissipates. Humans can control their breath, evolving from apes, this could mean that humans abandoned panting in favour of breath control if there were any benefits to gain. What benefits are there to be able to control your breath? It allows you to dive and it allows you to speak. Maybe it was the path through controlled breathing that led to a change in heat regulation in human evolution. This in turn led to humans, who already had the disposition to run, being able to exploit the niche of distance running and further develop in that direction.



Wednesday, September 27, 2006

The Toba Catastrophe


Around 70–75,000 years ago the Toba caldera in Sumatra Indonesia erupted. This was a supervulcano eruption, probably the largest eruption within the last two million years. The climatic effects of this event led to a decrease in average global temperatures by 3 to 3.5 degrees Celsius for several years. This massive environmental change made life very hard for many species and created population bottlenecks. This accelerated differentiation of the isolated human populations, eventually leading to the extinction of all the other human species except for the branch that became modern humans. Genetic evidence tells us that all today living humans descend from a population of about 1000-10000 individuals living at the time of the Toba event.

Population bottlenecks increase the rate of genetic drift. The Polar Bear for example could have evolved in this way. A Brown Bear group could have ended up on an arctic island at the end of the last Ice Age. Beneficial traits such as color, size, swimming ability, cold resistance, and aggressiveness could develop in just a few generations.

What kind of environment were these humans living in after the Toba disaster? Finding prey inland could be hard if many species were decimated. Could it be that it was this occasion that led humans to seek food predominately in coastal areas and those humans who were best suited for this survived? Maybe a strand of humans had already embarked on the aquatic path and went from being a very minor group to the one that became our ancestors.

Tuesday, September 26, 2006

The chords

When I chose the name for this site I thought "Fields of Gold" was quite nice as I indented to write about many topics which I find interesting. The song by Sting being one of my favourites also may have had something to do with it. Now that the site has gotten a few hits on google I see that all of them tried to find chords for the song. So I will not disappoint them. The chords below was set by a dear friend of mine.

Monday, September 25, 2006

Cornfield revisited

The pilot has found the best route out of the cornfield.

Arriving to his own farm he decides to fence his own cornfield. His cornfield is not rectangular but he decides to fence it in with a rectangle. While he is doing this he finds that independently of how he tries to build the fence using as little wire as possible he always ends up with a square with a side of 100m. He curses his bad luck as his cornfield is area wise the smallest possible cornfield that has this property.

What is the area his cornfield?

PS: The cornfield is compact, it does not contain any patches of grass or anything else.

Solution: See Spinning triangle.

Sunday, September 24, 2006

Unlur, a gem among games


In 2002 there was held a competition for abstract game developers. The main objective was to develop a game of unequal forces which means that the objective for the players are different. In Chess for example the goal for both players is to mate the king and both players follows the same rules, this leads to one player always have the same advantage at the start of the game. To make a game interesting you don't want this advantage to be too big. In Go which is a game of points you can adjust this advantage by giving one of the players a point handicap. In a game like Hex which is severely biased to the starting players favour this bias is negated by the second player having the option to swap colors. This swapping rule forces the first player to make a move that is not too good and at the same time not too bad, this adjust things very good but still in this case the second player has a tiny advantage.

In the competition Jorge Gomez Arrausi entered with the game of Unlur. This game has many similarities with Hex. It is played on a hexagon-shaped tessellation of hexagons. The game is played by placing white and black stones inside the hexagons, there is no restriction where to place the stones as long as the hexagon is not previously occupied. The goal of the game is different for the two players. White has to connect two opposing sides of the tessellation and black has to connect 3 sides that are not adjacent. After the first black move the next player has the option to either play a white piece, pass or swap color i.e. take the black pieces. By passing the black player places another stone and the next player again has the choice to play,pass or swap. After the second player chooses not to pass anymore the colors are decided. This nice contract opening of the game makes it possible to make the game very even.

In my opinion this game has a lot of appealing qualities. The board itself is very nice, it has six symmetry lines and six rotation symmetries, this is more than both Chess and Go. The game can't end in a draw, by stopping one player from creating his objective you automatically fulfill your own objective. The rules are very simple but the game has great depth. It is easily scalable, just increase the size of the board and you have the same game, just more complex.

There is a Spanish site called Ludoteka which allows you to play Unlur for free, unfortunately it is hard to get a good game as few plays it, but have patience and you might get lucky. Try this game out, you won't be disappointed.

Saturday, September 23, 2006

The mating game

Among males and females there is an asymmetry regarding the care for the child. For most animals it is the female that give birth and take the responsibility for the child. A major concern for her is to get the male to stay and help out raising a family. If we view this in a game theoretic way we say there is a cost for raising a child and a gain which is the child itself. Initially there does not seem to be a game going on, the female chooses a man and he helps out raising the child. The thing is that this setting is not stable in an evolutionary sense because soon there will appear males that just leaves after the child is born. In a game theoretic sense it makes sense for them not to pay the cost and at the same time gain the benefits. How should the females respond to this? They want to protect themselves from the philandering males by testing the presumptive male beforehand, they start insisting on a period of courtship before mating. This makes it harder for the philanderers, if they meet a coy female(females insisting on courtship) there will be no babies. Now we have four players in our mating game. The so called fast females who don't insist on courtship, the coy ones, the faithful men who court the females and finally the philandering males who leaves after the mating and don't spend time courting. If we study this in a game theoretic sense we assign some values to the gains and the cost involved.

Suppose the payoff to each parent of babies is +15, and the total cost of raising babies is −20. Suppose the cost of a long courtship is −3 to each player. What would this figures lead to? If a coy female meets a faithful male there would be an equal net gain of 15-3-(20/2) = 2 points for each player. If a coy female meets a philanderer nothing happens and both gets zero points. If a fast female meets a faithful man both get 15-(20/2)=5 points. If a fast female meets a philanderer the female will gain 15-20= -5 points while the philanderer gains 15 points.

Looking for equilibrium, what would the relation be between the number of faithful and philandering males? This fraction can be calculated from the fact that a mixed strategy would be optimal when the expected payoff from either coy fast females are equal. Suppose the males are faithful with probability x, we would then have a probability (1-x) for the philanderers. Setting up the expected gain for the females we would have

Coy: 2*x + 0*(1-x) = 2x
Fast: 5*x + (-5)*(1-x) = 10x-5

From this we get x = 5/8 and (1-x)=3/8. So for every 8 males there would be 5 faithful ones and 3 philanderers.
Doing the same calculation for the expected gain for the men with x being the probability to encounter a coy female and (1-x) the probability to encounter a fast one

Faithful: 2*x + 5*(1-x) = 5-3x
Philanderer: 0*x + 15*(1-x) = 15-15x

From this we get x = 5/6 and (1-x) = 1/6. So for every 6 females there would be 5 coy ones and 1 fast one.

The interesting thing with this result is that it is not Pareto-optimal with regard to males and females as a whole. Not Pareto-optimal means that both parties can change strategies and gain more. With the figures above the net gain for the females is 5/4 points and 5/2 points for the males. If all females were fast and all men were faithful the parties would have a net gain of 5 points. Both males and females would struggle to get out of this mess. It is tough to be a bird.

More in depth info about this can be found in 'The selfish gene' by Richard Dawkins.

Friday, September 22, 2006

Evolving a Nim player


In the post Most Human Human I suggested that you could program a computer randomly and actually make the computer do something you didn't explicitly program it to do. I propose here an example of how this could be done.

First I will introduce you to the game of Nim. Nim is an impartial two player game in which you alternate taking matches from one or several piles of matches. The goal of this version of the game is to be the player not taking the last match from the board. In this example I will use the simplest version where you only have one pile of 21 matches and you are forced to take one, two or three matches when it is you turn.

How should we design a scheme that a Nim player can follow which is appropriate for random programming? Every position in this version of Nim can be expressed by a number 1,2,3,...,21. Some of these positions will be loosing and some will be winning. So lets use a scheme where every number is assigned a 1 if it is loosing and 0 if it is a winning position for the player to move. A program could look like the sequence below where the value of a pile with 1 stick is represented by the number to the left, and the value of a pile with 21 sticks is the right most number.

010010010101001100100

A player could use this scheme to know which move to make in every position. The example above tells the player that the initial position of 21 sticks is a winning position as the last number in the sequence is a zero. How does he know how many sticks to take when it is his move. He looks at the scheme and sees that the three following positions are numbered 010. This means that if he takes two sticks he will give the opponent a position with value 1 which he would think was a loosing position. If he have multiple options he chooses randomly between those. Note that this representation is not always consistent, but let evolution take care of that.

Now lets create an initial random population of creatures who's genome are the same as the scheme above. Cross breeding two creatures would be done by choosing a random position in the genome and swap the genes just like nature does it. Below '-' marks the crossoverpoint.

P1: 10011001 - 1010100101001
P2: 01001001 - 0101001100100

gives two possible child creatures.

C1: 10011001 - 0101001100100
C2: 01001001 - 1010100101001

Sometimes we also will change a bit randomly, this is called a mutation and allows new traits to emerge in a stagnant population. When the initial population is in place we can start matching up creatures against each other playing Nim for their life, losers will be replaced by offspring generated from parents chosen randomly from the population. After a few generations we will see that almost all creatures will have the same gene in the left most position. The total gene pool can be described like this

1XXXXXXXXXXXXXXXXXXXX

where the 1 means that every creature now know that when there is only one stick left you have a loosing position, you are forced to take it and therefore loose. The creatures that had a failing gene here would succumb fast to the more sophisticated ones. After running the program for a few more generations you will see that consensus have emerged with regard to a few more genes, like this

1000XXXXXXXXXXXXXXXXX

Now evolution has arrived at the notion that when there are 2,3 or 4 sticks left these positions must be winning as a player faced with these values always have the possibility to leave the next player with the loosing position of one stick left. After running some more generations all the creatures will look the same(except for a few random mutated ones that always will be a minority). The final dominant genome will look like this.

100010001000100010001

So, the computer have randomly, guided by evolution, arrived at a strategy to play a perfect game of Nim. The interesting thing here is that the programmer of the genetic algorithm may very well be unaware of this optimal strategy beforehand. This is different than the algorithms used in chess programs which are designed to search deep, evaluating the board from preset patterns designed by humans. If on the other hand the evaluation function was designed by an evolving population of competing chess programs we maybe could arrive at a chess program who has better understanding of chess than any human.

Thursday, September 21, 2006

Declaration of Digital Rights


One application of Digital Rights Management(DRM) is to supply digital content such as text, music, video or executable, and preventing that this content is used in an inappropriate way. Copying and sharing could be prohibited and even how and when you have access to the data. The basic ingredient here is to encrypt the media using a bulk cipher. A bulk cipher is an algorithm that is fast and appropriate for encrypting large amount of data. Often you also want the decryption to be able to start at an arbitrary position in a file, then you will have to use a so called block cipher. Today the most common such algorithm is called AES which is a symmetric key(encryption key is the same as the decryption key) cipher available in CBC(Cyclic Block Cipher) mode and stream cipher mode. No asymmetric fast algorithms are known, RSA, the most common asymmetric cipher, is about 1000times slower than AES in most implementations. If an asymmetric cipher is invented that is fast enough and available for block and stream ciphering this could make many cryptographic protocols much easier. The advantage of the asymmetric algorithms is that the key transportation issue becomes easier, you can share the public part of the key. Therefore RSA and other asymmetric algorithms such as El Gamal and Diffie-Hellman are used to transport symmetric keys to be used for the actual bulk data decryption, this is done in a similar way as the one described in the sharing a secret post.

So, assuming a symmetric encryption, you have an encrypted media file, and you somehow must get hold of the key to decrypt the media. Passing the key can be done in three ways. Either you send the key along with the content and hope that the device that receives the content won't allow anyone to read the file. It has a great flaw in that if someone catches the file before it reaches a safe environment the key can be read by anyone. Another way is to have a method for generating the key based on a password. When you purchase the file a password is supplied and you will receive a specially designed content file just for you. A problem with this scenario is that the security here is based on obscurity, which means that once the key generation method is discovered the whole system breaks. This is basically what has happened to MS-DRM and forces MS to supply patch after patch of new key generation methods. Some solutions allow the user to choose a password himself. The flaw with this is that a malicious user can distribute his password and then everyone can use the file. The eReader DRM tries to circumvent this by using the credit card number of the user as input for the key generation method. This is quite smart as most users are not keen on giving their credit card numbers out to everyone. Still the flaw of security by obscurity remains. The third solution to the key transportation issue is to deliver the key separately in a license file. This allows the content provider much more flexibility and can be made very safe. This is used in OMA V2 DRM and to some extent in OMA V1, but in OMA V1 the licenses just contains the keys in plain text so it is not really safe. OMA V2 describes a much more sophisticated way of building and acquiring the license. This system requires a protocol called ROAP to be followed. This protocol is quite similar to SSL/TLS protocols used for safe transactions on the Internet, using digital certificates for authentication. These solutions relies heavily on asymmetric ciphers for key transportation.

The system with a license catches the essence of DRM. The license describes the rights granted by the issuer. This means that scenarios where the content itself plays a minor role appears. You can focus on the rights and use the license on its own to prove your rights. I think many speakers who have put forward the notion that DRM actually should be called 'Digital Restrictions Management' have totally missed this important fact about DRM.

Content providers using the simpler versions of DRM still have one more card up their sleeve. They can use digital watermarking. If a user cracks a certain file and this file is distributed unencrypted the content provider can track the file to a certain user. A digital watermark can be described as changing the original digital content in a way that does not distort the content. Take a picture for example. Every pixel in the picture is described by a number. Usually this number can range from 0 to 65535 or more. This number describes the color and intensity of the pixel. Two numbers that are close are very hard for the human eye to distinguish. This means that some of the pixels can be changed my a minute amount and no one can tell the difference. The content provider who has the original picture can compare the two digitally and see the difference, the hidden code will point to a specific user.

Wednesday, September 20, 2006

Eve the eavesdropper


Thin king and fat king solved their problem with the untrusted messenger by the ingenious trick of using two padlocks. They felt safe for a while but one day thin king heard that one of his gifts hadn't reached fat king, in fact fat king never even got the chest to apply his own padlock on. Thin king soon understood that his messenger once again had tricked him. He had sent his messenger away with the locked chest and soon the messenger had arrived back with another padlock on the chest. He removed his own and sent the messenger away again. In hindsight he remembered that he hadn't really gotten a good look at the second padlock, probably the messenger had created his own padlock and just applied that one instead of allowing fat king to apply his. From that moment on thin king and fat king had to find a way of being sure that the padlocks were indeed theirs and not the messengers. They found out that to do this they had to involve a third party which both of them trusted, this third party could apply non-forgable stamps on the padlocks and he promised never to apply the same stamp to the messengers padlocks.

In the digital world the same problem occurs. Here the solution is called digital certificates. These certificated are used to transport the public part of a public/private key pair. A certificate contains the public key, and some extra useful stuff like validity period, name of the issuer and name of the owner of the transported public key and finally a digital signature. The certificate is created by a trusted third party, a so called CA(Certificate Authority). The CA digitally signs the certificate with his private key and everyone can verify it using the CA's public part, which everyone is supposed to know and trust.

Tuesday, September 19, 2006

Natural optimization

Often we try to find the best solution to a problem. It can be, lowest price for a specific item, the loan with lowest interest or the stock with the highest expectations. Sometimes we even bring out our calculator and try to use maths to get to the answer, for example, how should I construct a can that can hold a certain volume using the least amount of material. Optimization like this can be thought of like finding the highest hill in a vast landscape. If you are lucky there is only one hill and you will get to the top just by walking upwards. If you are unlucky there are many hills and mountains. The problem turns into finding the highest peak in the Alps just by walking about. Just going upwards won't help you as you will just end up on the top of the hill closest to where you started.

How does nature do it? Think of Newton and his apple. The apple will fall to the ground because of gravity. This phenomenon can be thought of as an optimization problem. Nature wants to find the lowest potential energy. In this case nature doesn't do any better than hill climbing, it just finds the closest valley.

But sometimes nature can do better. Think of a cup of water you have put in the fridge. It will freeze. When liquids freeze the molecules line up very neatly in a configuration holding the least energy. How does nature find this configuration? It is done in a process called annealing.Using the mountain range analogy this process can be imagined by replacing Newtons apple with an extremely restless child. It will skip across the mountains randomly and slowly loose energy. The more tired the child becomes less likely it is to go uphill. Finally the child will be totally out of energy and tumble down into the closest valley. This process often comes close to a minimal energy but often the final crystal will have some flaws indicating that a local minimum has been reached.

And then we have the process of evolution. In the mountain range analogy we will have millions of creatures scattered all over the mountain range. The creatures on the hilltops will be called inferior and the creatures in the valleys are superior(or vice versa). Evolutionary selection will remove the creatures on the hilltops to a greater extent and the creatures in the valleys will mix, share traits and create a new creature that will get a position(genes determine position in the landscape) somewhere between the two parents. This process will lead to communities being formed in some of the best valleys, breeding between those will sometimes create a new creature located perhaps in an even better valley and a new community will be formed there. Finally the majority of the creatures will live in the same, possibly deepest valley.

Monday, September 18, 2006

Throw me!

We have all seen the amazing javelin throwers at the Olympics. They throw the javelin so far that they have to redesign it every other year to keep it inside the stadium. But what object has the record for being thrown the furthest by a human without any artificial help, is it the javelin?

It's a Frisbee. The record today is a quarter of a mile. The object was a specially designed Frisbee in the form of a ring, the Aerobie Pro ring. But how does a Frisbee work, what makes it fly?

A Frisbee is a cross between a wing and a gyroscope. Giving the Frisbee speed, it cuts through the air like a wing, and giving it spin it gets stability. Without spin the disc would turn over and fall to the ground. How much the disc spins and the particular design can give the disc very different flying characteristics termed 'understable' and 'overstable'. Understable discs need a lot of spin while overstable needs less.

I heartly recommend the sport of discgolf where you can play with the physics of flying and get a moderate exercise at the same time.

Sunday, September 17, 2006

Lost in a cornfield

A man was flying over his neighbours lands one dark night when the plane all of a sudden started to have problems. He pulled out his parachute and jumped. Soon he landed in his neighbours cornfield, the only cornfield in the neighbourhood. He knew one thing about this particular cornfield and that was the exact layout of the field. It formed a perfect rectangle, 100m wide and very long, several kilometers. Unfortunately he had lost all sense of direction gliding down the night sky.

As he stood there among the corn he thought to himself, how should I walk to be sure to get out of the cornfield as quick as possible, in a worst case scenario?

He is able to walk along any curve he chooses but he has no means of knowing his initial direction. Also, the cornfield is so thick that even if he stands on the very brink of the cornfield he is not aware of it, he must actually step out of it to notice he has succeeded.

Solved by anonymous: Optimal walk is ~227.8m.

The solution is a so called 'yurt' curve.


The optimal value can be found by minimizing


If you place one leg of the yurt in origo and the other leg in u you arrive at the formula above.


Saturday, September 16, 2006

Aquatic mind


Most people agree that humans have evolved from apes. There are many differences though between apes and humans. Many of these differences is quite subtle and not everyone is aware of them and some are quite striking. At first glance we notice the nose is different. We have bigger lips and fattier tongues, which allows us to speak with extra help from the larynx, among other things. We are not as hairy and our hair is aligned nicely and it's not furry. We walk on two legs and we have subcutaneous fat just like the whales.

Have you heard about the aquatic ape hypothesis? It states that man during his evolution at some time spent a great deal of time close to, and partly in water. This hypothesis explain all the differences above and many others very nicely. Our nose is turned downward because this prevents water from entering the nose while wading and swimming. Big lips and fat tongue help while eating sea creatures such as mussels and oysters. We lost hair and developed body fat just like the whales. We have a quite strong diving response which can even rival sea creatures like sea lions. We have grown used to water cooling and therefore sweat when warm, our cousin apes don't sweat. Our bipedalism can be a consequence of initially being 'waders'.

I don't claim here that this theory must be correct, just that it's gives quite good answers. Which other theories give plausible answers to these traits?

Some evidence even suggests that humans gave birth in water during this period. Human newborns are coated with vernix, an oily substance produced by the skin. No other land mammal, including the apes, produces vernix-coated neonates, some sea mammals do. Also a baby which is born under water will swim to the surface on its own.

For me diving and free diving in particular gives a great sensation of being calm and free. Is this the aquatic ape inside me giving me the thumbs up?

Thursday, September 14, 2006

Truly parallel

Today it has become common with multicore CPU's. Much discussion has erupted about the average users benefits from this and if it's just a hype. An obstacle in they way of making use of all the cores is that the majority of the programs today is not meant to be running on machines like this, they can't themselves make use of the extra power. This is a quest for the operating system which also have a hard time achieving this as the programs are written in languages which has not been designed for the issue. Sure, Java supports threads and Unix systems allow C programs to fork but it is up to the programmer of every program to design how this is going to be used. As these systems also should be able to run on platforms with only one CPU, it is thus hard for a programmer to make use of the power, the programmer does not know how many cores the system will run on, the operating system will decide how and when the code will run.

I would like to see a new programming paradigm. A paradigm more similar to how nature makes use of parallelism. Take a human cell for example. Every cell contains the exact same program(the DNA) but still the cells can form a complex being out of a single cell. Why does not the human cells act like bacteria that just multiply, making copies of itself.

The secret is that when a human cell divides the program counter, the DNA decoding device, is not placed at the beginning of the code. The child cells will run another part of the code even thought it contains the exact same code. Tom Ray made some initial promising studies on this in his Tierra project. Also he added another piece of the puzzle to his evolving code snippets. He designed a computer language that was very robust to random changes, something the CPU in your computer in front of you is not. Make a random change to a PC program and the program will break.

But isn't this exactly what a fork in a C program does, dividing the code in two and setting the program counter to a new place for the child? Yes, it is, the difference is how the processes communicate. In a PC one process writes to memory and another reads, this has to be controlled very strictly, every process knows what the other processes are supposed to do, and who will listen to a specific message. In a living being the child processes are on their own, no message(chemical) is meant for a specific cell. This approach adds hugely to the evolvability of a system. An interesting thing is that there is nothing in the computers design that keeps us from doing it in natures way, it is just very hard to write programs like these with the languages and operating systems we have today. Ask a Linux kernel developer what he thinks about inter process communication, I think he would welcome something new.

Most human human



You must work very hard to convince the judges that you're human, You shouldn't
have any trouble doing that - because you are human.


This is what Robert Epstein told a panel of five humans who's task was to compete against computers for being most human. The inspiration for this event dates back to the earliest days of computing. In 1950, pioneer Alan Turing proposed that if a computer could successfully impersonate a human being during a free-form exchange of text messages, then for all practical purposes, the computer should be considered intelligent. To really make the humans try hard there was a little side award for the most human human.

You can argue that this "Turing test" really is not the core of the issue about computers being able to think. Many argue that all computers has to be programmed, which is true, and that this implicates that computers never really can think, which is false. The interesting thing here is that a computer really does not need to be programmed by a human. A computer could do the programming. But does this really mean anything? Yes, because programming a computer to do the programming of the second one you can allow the first one to do his job randomly. But, putting a monkey at the keyboard hacking away randomly would certainly not result in a program exhibiting thinking qualities. Yes that is correct, but then you round up a thousand, a million or more of these little programming computers and make them compete in an evolutionary manner. I bet this article would not give me any award for being the most human human, but is is really written by me? Going down for maintenance.

Wednesday, September 13, 2006

The Oak Island Enigma


Have you ever heard of a real buried treasure? This is a story about a real treasure hunt that has not yet come to an end. It started one summer day in 1795 when Daniel McGinnis was wandering about Oak Island outside Nova Scotia in Canada. He came across a curious circular depression in the ground and leaning over the depression was a tree which had been cut in a way which looked like it had been used as a pulley. He went home but came back the next day with two friends and started digging. After 10 feet they ran into a layer of oak logs spanning the pit. The same thing awaited them at 20 and 30 feet. At this point they were not able to dig deeper but returned 8 years later. They continued digging to 90 feet finding oak logs every 10 feet. At this point the pit suddenly filled up with water. The gang had sprung a booby trap.

Later it was found that the pit was connected with sloping tunnels to a bay on the island and the whole bay had once been dammed. It seemed there was a vault down in the pit and the oak logs had been placed to take the load of the ceiling of the vault. If someone dug close to the vault the pit would fill with water. Up to this day the treasure in the vault has not been recovered even though much work has been put into it. What do you think lies buried here? Who put so much work into hiding something on this island?

Tuesday, September 12, 2006

Law abiding words

Does words follow any law? Yes they do, and it is called Zipf's law. This law states that if you count the number of occurrences of words in a text of a natural language these numbers must relate to each other in a certain way. If you order the words in a row sorting by the number of occurrences you will find that the frequency of any word is roughly inversely proportional to its rank in the table.

For the English language you will see that the word 'the' is most common and occurs about 7% in a given text. Second comes the word 'of'' with an occurrence of 3.5% and on third place comes 'and' with an occurrence of 2.3%. From this follows also that the major part of all the words occur only once in a given text.

What fun can we have with this knowledge? Actually this is a good tool in cryptography. If you are given a text that you don't recognize you can start counting the words. If you find that they obey Zipf's law the text is probably not encrypted and you just have to find somebody who understands it.

Now this does not always help you. The picture above is taken from a book called the Voynich manuscript. This documents has a very strange history and no one has so far been able to understand the script. Some have wondered if it is actually encrypted, but when you count the words you see that the text obeys Zipf's law. So is this written in a forgotten language seen nowhere else? Maybe you can solve the mystery...

Monday, September 11, 2006

The lucky dozen


Have you wondered why the are twelve notes in the scale? Why not thirteen? This is actually just a lucky mathematical coincidence. The individual frequency of the tones are really not important(in Mozart's days an A was not the same as today), what is important is the relative frequency of the notes. All frequencies does not sound good together, there need to be harmony or chords striving towards harmony. Harmony is achieved when the frequencies relate to each other in sequences of natural numbers like 3, 4, 5 or 4, 5, 6, 7. When the frequencies double up we think they sound so similar so we say they are the same tone just in another octave. When you try to fit these relations together within an octave you will arrive at 12(or 19,31,72 or more) different tones for the tempered scale. Twelve is normally chosen because it accomplishes what is needed and is the least amount that does it. The tempered 12 tone scale is a good compromise because 2^(4/12) is very close to 5/4, 2^(5/12) is very close to 4/3 and 2^(7/12) is very close to 3/2 for example. You can also chose to tone your instruments for the exact chords(Just Interval) but then some of the tones outside the chord or in another octave will sound strange. The interesting thing is that it is not really agreed upon which tuning is the best, there are several rivals 'equal tempered'(most common), 'Just interval', 'Well tempered', 'Mean-tone' or 'Pythagorean'.

This is something to tell those who claim to have the ability to recognize 'absolute pitch'. They simply have a very good memory for frequencies and there isn't really an absolute pitch to remember. Mozart who is said to have had the ability would not recognize the 'A' of today's tunings.

Broom with a wroom



The witches have upgraded their brooms to spaceships. Centuries ago people were abducted by trolls or the devil himself. In those days the woods were actually scary and you could get lost, strange sounds heard were attributed to fantasy creatures. Today we in the west really cant believe in those things anymore, but we still get abducted, just not by the fairies of the woods but by aliens. Space is black and vast and who listens to scientists when you can explain it so much more interesting. Actually scientist have a very plausible explanation why people experience these things, in Japan they call it 'kanashibari', in the west we call it sleep paralysis. Sleep paralysis is not well known in the west, people experiencing it associate it with an abduction like taken away forcefully on a broomstick or taken by aliens, this is what we have been tought. Recent studies in Canada, Japan, China and the United States have suggested that it may strike at least 40 percent or 50 percent of all people at least once. I am still waiting for my first, maybe I just have to upgrade my broom.

Sunday, September 10, 2006

Oden about blogging


Why am I blogging under a pseudonym? I read this in Havamal and think it was quite appropriate for blogging in general.

1. Gáttir allar
áðr gangi fram
um skoðask skyli,
um skyggnast skyli,
því at óvíst er at vita
hvar óvinir
sitja á fleti fyrir.

1.At every door-way,
ere one enters,
one should spy round,
one should pry round
for uncertain is the witting
that there be no foeman sitting,
within, before one on the floor


And then, why am I blogging at all? And see Havamal has something good to say about that also.

47. Ungr var ek forðum,
fór ek einn saman:
þá varð ek villr vega;
auðigr þóttumk,
er ek annan fann;
Maðr er manns gaman.

47 Young was I once, I walked alone,
and bewildered seemed in the way;
then I found me another and rich I thought me,
for man is the joy of man.

Saturday, September 09, 2006

Sharing a secret

When you can't trust the messenger how do you share a secret with someone? This is a key problem in modern cryptography. You are faced with the same problem as thin king and fat king. For the kings there exist an elegant solution.
  • Thin king first applies his padlock to the chest.
  • When fat king receives the chest he can't open it because he don't have the key to the padlock. So he applies a padlock of his own to the chest and sends it back with the messenger.
  • When thin king receives the chest he removes his own padlock and sends the chest back to fat king.
  • Now fat king only has to remove his own padlock from the chest.

In modern cryptography you have to solve the same problem but in the binary world of the Internet. Luckily there exist a mathematical counterpart to the chest and padlock concept. It is called the discrete logarithm problem. If you want to send a secret number to someone on the Internet you can apply a 'padlock' to that number that only you can remove. You apply this padlock by taking the secret number and calculating the discrete exponentiation using your secret key number as the exponent. If you choose large enough numbers no one but yourself can undo this operation and find the secret number because there are just too many solutions to the discrete logarithm.

Wet, wet, wet


Oh my, it sure has been wet lately. And the early summer sure was dry. I read today in the news a poster thought this could only mean one thing and that was the climate had gone awry. I have thought about this before and usually my thinking goes back to the ice ages, climate changes on a big scale. And today I came to the conclusion that I never really understood why the climate has been changing like that through the eons. After looking it up on the net I found that no one really understand this, now I was feeling I was in good company.

The most common truth at least in Sweden is that global warming causes ice to melt and then the oceans to rise. I have always had a problem with that reasoning. Global warming causes more water to be bound in the atmosphere and this water will come down where the air is chilled. Snow that falls on the arctics would add to the ice masses and the ice that has melted would be rebuilt. At this point I start thinking about the ice ages, why did the ice grow then. To explain this we need to have a change in temperature difference between the equator and the arctics. We need a build up moisture in the air and we need cold climate over the arctic region making the buildup of ice greater then the melting.

And today I found that this actually could be the case. In the mid 19th century James Croll, a British amateur scientist, came up with an idea that the gravitational pull from the moon, sun and the planets cause the earth's axis to fluctuate. Sometimes the arctics gets more sun as the axis is tilted more to the sun and the melting gets greater than the ice buildup for a while until equilibrium is reached, when it tilts back the ice sheets start to grow again. I found this quite enlightening and it seems this is the only theory that actually can explain why ice ages come and go cyclically. I guess this theory has other flaws otherwise I suspect Al Gore wouldn't travel the world with his new documentary, please fill me in on this.

Friday, September 08, 2006

Thin King and Fat King


The thin king and the fat king has a problem. Thin king want to pass a gift to fat king but his messenger is not trustworthy. He has previously tried to pass his gift in an unlocked chest but the chest has so far been empty on arrival. The kings decide to padlock the chest so that the messenger can not steal it contents.


Now the kings have a problem, how can the fat king open the chest without thin king passing along the key to the padlock?

Thin king who is rather smart comes up with a working solution. How do they do it?

Update: A clue to the puzzle. Fat king may have a padlock of his own.

Solution: See the post Sharing a secret

Having fun with a switch


Have you had fun with a switch lately?
There is a thing called the Duff device. This is a C programmers dream and the reviewers nightmare. Some say it's abusing the language and some say it's beautiful. Myself I see beauty in most things.

This is how the Duff device looks like

switch (count % 8) /* count > 0 assumed */
{
case 0: do { *to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
} while ((count -= 8) > 0);
}



So what good can you do with a thingy like this? You can actually produce your own lightweight threads library using this construction. Just look at this

#include "pt.h"

struct pt pt;
struct timer timer;

PT_THREAD(example(struct pt *pt))
{
PT_BEGIN(pt);

while(1) {
if(initiate_io()) {
timer_start(&timer);
PT_WAIT_UNTIL(pt,
io_completed()
timer_expired(&timer));
read_data();
}
}
PT_END(pt);
}

Example protothreads code.


This is 100% pure C. The macros actually build a kind of Duff device that incorporates the __LINE__ macro in an ingenious way. If you are interested take a look at http://www.sics.se/~adam/pt/



Thursday, September 07, 2006

Is DRM good or bad?

Today DRM(Digital Rights Management) is mostly used for protecting music and video media. You can also find some java applets that are DRM protected. Most people, especially on the internet, think this is bad news. No more sharing between friends and sometimes the newly purchased media can only be played on the specific device you purchased the media for.

What good can there be for the us the users with a system like that? For the producers of content there would be some benefits, they can make sure they get paid for what they do. Maybe this also causes prices to go down and making media easily available. Still the benefits for the users versus the cost seems to be low, the music owners keep the prices too high for many peoples tastes.

I say we have to wait and see. DRM is in its early stages. The strict device dependancy is overcome by domain functionality in for example OMA V2. And there maybe other uses for DRM that are not around yet that actually can make life easier for us.

Think about bus tickets or season tickets to your favourite sport events.
Those tickets could actually be DRM protected licenses that gives you access. DRM is all about 'rights'.

When you go abroad you could purchase your subway ticket from home, downloading your DRM license and use this to prove your right to use the subway on arrival. The actual content is now of secondary value, it is the license that is valuable, in this case there may not be any content at all.

DRM could be used as a voting ticket. When you are about to vote you will receive a DRM license and you can use this to prove your right to vote.

OMA DRM can already handle these cases today as there are many possible forms for a license. It can be time based or count based. A voting license could have a count for every vote you have the right to place. A season ticket used on the subway could be time based giving you the right to use the subway for a certain amount of time. DRM also allows interval based licensed or accumulated time based licenses. You could have a ticket that gives you use of the subway for a month taken from the first time you use it or you could have a license to use the subway for an accumulated time of say 1 day.

Maybe DRM actually can make life easier for us?

Who was Shuusaku?


Honinbo Shuusaku, born as Kuwabara Torajiro, is a legendary go player. He had an almost magical ability to grasp the whole board. His most famous move was the 'ear reddening move' against Gennan Inseki in a game from 1846. You can see the beauty of the move here.
Go is both the oldest game known, boards from 2000BC has been found, and at the same time the game were humans still outclasses computers. The human ability to recognize shapes and see connections and patterns is fundamental for playing a good game of Go. Although much effort has been made to create strong go programs a human learning the game only needs about 2 months of training to best all known programs.

Is DRM broken?

The simple answer to this is NO.

What is broken is the Windows Media DRM solution as shown by FairUse4WM. But this does not mean DRM as a whole is broken. The problem with WM-DRM is how the private keys are stored. Take OMA V2 DRM for example which is used in many mobile phones. Here the private keys are stored in hardware together with the crypto algorithms. The private part of the key never leaves the hardware. To break this system you need to break RSA or ECC.

The problem with WM-DRM is that the private keys are stored in the normal filesysystem. I suppose this is done this way to be able to use this solution on a PC without any specialized hardware. But alas a solution like this can never be safe. Security through obscurity is never safe.

OMA V2 DRM describes a protocol called ROAP that ensures the safety of the system. Mobile phone technology enables this by using specialized hardware to hold private keys. Licenses contains content keys that is unique to every phone. To be able to decrypt content files access to the private key and an associated license is needed. In a good DRM solution the keys and the algorithm are bundled together so that the keys never have to leave the hardware.

Even in mobile phones the WM-DRM solution is not safe as it does not use the built in secure hardware but depends on scrambling certain part of the filesystem to get hold of the private key. The scrambling process is not easy to understand but, as has been proven by FairUse4WM, a system like this will eventually be broken.