A Mosque at Ground Zero?

A new controversy is currently hotly debated in the press: to build or not to build a mosque at ground zero? I see two arguments, one against and one in favor. The argument against building such a mosque is that it may hurt the feelings of those who lost family, friends or loved ones in the 9/11 bombing. In fact, this seems a very strong argument because irrespective how we feel about the issue, these people will want to visit the site where their loved ones died and that experience can be severely affected by a clearly visible mosque. However, I am not sure the majority of the surviving dependents actually will be offended by a mosque. At the very least their opinion should be polled. And by the way, I am sure many moslims also died in the 9/11 attacks and wouldn't they need a place to mourn their loved ones?

Now the argument in favor. I believe the most appropriate monument we can build that expresses the tolerance of our western society towards other cultures and minorities, and expresses how much we value our constitutional rights (aka liberty of speech, liberty of religion etc.), is to precisely build a mosque at ground zero. It expresses the fact that we do not stigmatize a very large group of well willing citizens and accuse them of the crimes committed by a very small group of terrorists. It expresses the fact that we have learned from history and will not make the same mistakes again (and again). So, please let's build that islamic center at ground zero and use it to create mutual understanding and eradicate the hate that led to 9/11. Let's not think with our gut but with our head for a change.

The Efficient Market Hypothesis

The stock-market is a fascinating beast. It's the largest casino in the world, better compared to a huge online game for adults. If you are able to predict the future price of a stock you are in (big) business. When it rises, you buy that stock and sell later. When it drops you short-sell that stock (basically selling it now before you own it and paying for it at a later time when the price is presumably lower). But the view held by most academics is that markets are efficient, that is, unpredictable. Imagine there is some knowledge out there in the world that makes the price of a stock predictable, then the first person who knows about it will "gamble it away". It takes only a few people (or even one) to remove the predictable pattern (if it were still predictable, gamble some more until it is no longer predictable). And there is little delay in this process too (since potentially millions of dollars are involved investors will act very fast). And so the hypothesis is that the market is a random walk: utterly unpredictable.

So what are all these thousands of investors wasting their time on? A huge paradox is presenting itself here. An army of investors are presumably making money on the market every day, while an army of academics is claiming they can't. What's going on?

Hypothesis 1: the investors are seeing patterns where there are none. They believe they are beating the market but in reality they don't. Perhaps they gamble on more risky stocks which have a higher average return. It is well know that humans tend to see patterns in data where there are none (it can't be coincidence that I met my old friend in Lissabon during the summer). We hear about the successful investors who have survived but they represent 50% of the population. The other half can be found in the gutter.

Hypothesis 2: Any obvious patterns are absent, but there are hidden patterns that are not public on which you can make money. It is a well documented fact that once a pattern is made public, it will instantly disappear because investors will start using it. But it's rather stupid to post your successful trick to make money on the wall (unless you are an academic). So, we must assume investors are using their own secret rules to trade. Some figured out you should trade on the scale of seconds or less, others use complicated rules of thumb at the scale of days/months etc. The mere fact that publicized patterns disappear tells us that before they were made public they were still predictable.

To me, the markets represent an interesting collective artificial intelligence that determines the true value of stocks very efficiently. Markets have even been used to predict other facts. If you want to know the answer to an arbitrary question (i.e. who will be the next president) start a market and let people bet on it. The collective wisdom of the masses supersedes the wisdom of any knowledgeable individual. We should probably be thinking about how to use this idea for better purposes.

Japan

A brief blog about Japan. I have just been to Kyoto and Tokyo. Brilliant experience. I was most impressed with Buddhist gardens. And with Japanese hospitality. Japanese are among the kindest and most hospitable people I know. They go out of there way to show you around and help you in any possible way (thanks to Kazuyuki Tanaka and Kenichi Kurihara). I gave a talk at Tokyo University and the level of interest and the quality of questions was absolutely impressive. I don't know how they do it, but they give you more then anywhere else the impression that you are special and your talk was brilliant. They genuinely care it seems and that is a lasting experience. Our dinner at an Okinawa style restaurant was also very interesting. We had lot's of good conversations about topics that I might have thought were perhaps taboo (the war, their Korean ancestory etc.). And yes, the food is about as good as it gets anywhere on the globe.

Japan has a culture that is about as alien it gets (if we confine ourselves to earth). One in ten Japanse wears a face mask in public. It freaks me out a little I should say (but I got more used to it in the end). You feel like the plague has broken out. Nobody eats in the street (I started to notice it while eating my sandwich going to the bus). Tokyo is an anthill. Not because there are so many people packed together (there are) but because people are organized. They follow the rules. And there are many signs pointing out the rules. You pay your bus fare when you exit a bus and not when you enter (makes lots of sense). When buying a ticket or ordering your coffee (in English) the response is invariably in Japanese. Not just one word, but long sentences of unintelligible Japanse from very friendly smiling faces. I am sure they know I don't understand a word, but it doesn't matter. I think it is just polite this way and it doesn't bother me in the least (given a little more time I would have started to talk back in Dutch). By the way, Japanese is more like singing actually, where the last vowel is extended for a second or so. And lot's of bowing. In the beginning it looks a bit funny but after a few days I found myself bowing quite a bit as well. And then finally, there are the toilet seats... They are high tech devices. Preheated and with a few options to clean your bottom (couldn't figure out how to reduce the temperature though).

Boy, did I enjoy Japan. From it's cherry blossoms, via its temples to its friendly people. Thanks everyone for a wonderful experience.

Time

We take time for granted. It's simply there and flowing forward at a steady and unstoppable pace. In fact all of modern science is dependent on it because it is necessary to define causality: the notation that one things "causes" some other thing to happen. This apparently happens only in one direction. However, there is a huge paradox luring behind the corner, because all fundamental laws of physics are time reversal invariant. The reason for the observed asymmetry of time is the second law of thermodynamics which says that entropy can only increase. That is actually not quite stated correctly. It should say that there is an overwhelming probability that it increases but there can be random fluctuations that make it temporarily decrease.

Where does the second law of thermodynamics come from? Fill a swimming pool with a red fluid and a blue fluid separated by a wall. Now remove the wall and you will notice that the colors mix. The opposite will never happen. Yet the underlying laws are symmetric. What's going on? The issue is that there are very (very very) many more states with colors mixed up that look the same to us than there are states which separate the fluids. So we can imagine the state-space as being build up from cells where all states in a cell all look the same to us. As we randomly wander around in this space we will move from cell to cell but since some cells are so hugely much bigger than others we always tend to wander into those. So, perhaps surprisingly, the second law is "subjective", it depends on us not being able to to distinguish the many states with mixed colors.

How would the world look like if all possible states would look equally different? Imagine just looking at 2 marbles moving around in a box. They reflect off the walls and so now and then reflect off each other. If we play the movie backwards it looks exactly the same. In this world we would have no features available to tell the directionality of time. In such a world the concept time might not even exist for creatures living in it. Hard to imagine isn't it?

Let's go one step further. If entropy is increasing since the conception of the universe, it must have been very small to begin with. In fact, this is exactly, what Roger Penrose proposes in his book "the Emperor's New Mind" (in the less controversial chapters of it). The universe was in a very low entropy state when it was created and has been steadily increasing ever since. The notion of time and the reason we perceive it must be sought at the "time" of the Big Bang. Nobody knows why this is true. In fact, one can easily imagine an opposite scenario where (for some reason) the universe must end in a very low entropy state (perhaps a bizarre version of a Big Crunch) but started out in a high entropy state. In such a universe effects are followed by their causes. Broken glasses magically assemble themselves into whole glasses. In such a world the future looks much more certain then the past.

Try to imagine living such a world. My feeling is that time would be experienced in reverse, but we wouldn't really notice it, because time is all just an illusion anyway. The reality is that the universe is simply there from beginning to end. We occupy a small window of that universe and perceive it as flowing in a certain direction. Very Buddha.

Now for some very controversial experiments that cast doubt on how we might understand time. It seems that there have been quite a few experiments where an experimenter would repeatedly show subjects pictures that were either extremely disturbing or very nice and beautiful. The subject is hooked up to some device measure his/her level of excitement (say fMRI or simply resistance in skin). Disturbing pictures will evoke a much different response then nice pictures after you have seen them. That's not strange. What's strange is that the subjects seem to have a significantly different response before the pictures have been shown. In other words, they seem to anticipate whether a picture is disturbing or not.

I am assuming that the experimenters very carefully ruled out any learning effects (although I haven't actually seen this mentioned). This is important because people seem to be able to learn very complicated patterns completely unconsciously without even knowing it. It's easy to control for this though, because you simply produce a random sequence, or even better show a complicated correlated (i.e. predictable) sequence and then reverse the correlations. If the signal stays you rule out that the subjects were able to predict what image would come next based on correlations. I also assume they did their statistics right of course.

However, if all these things were done correctly it presents a huge puzzle. These subjects seem to know the future, i.e. they "remember" the future. This leads immediately to a paradox.
"suppose one can know the future.
Then one can take action so that that future will not happen.
So it doesn't happen.
Contradiction
So no-one can know the future"
Unless, one could not use the information to change the future.

Ok, all of this is really bizarre. And the first impulse for any scientist will be to reject this out of hand. But I think we should keep an open mind. The notion of time is very strange and paradoxical in itself. And there are other strange cracks in our scientific theories that concern causality. Take the quantum mechanical phenomenon of the collapsing wave-function. If you take two entangled particles with opposite spin and shoot them off in opposite directions of the universe and then measure the spin of one of them, the other one is instantly known on the other side. You cannot explain this by assuming that they already were in a certain spin orientation but that you simply didn't know which one. No, the spin direction is genuinely undetermined until you measure it.

Measuring the orientation of this strange entangled state implies that some kind of signal must be traveling from one end of the universe to other to inform the other particle that it must now be opposite to the value we just measured. If it travels faster than light however, it means that you can identify two observers in the universe traveling with high velocities in different directions for which the causal relationship between the events is reversed! For one observer spin A collapsed first and sent a signal to B, while for the observer spin B collapsed first and sent a signal to A. Now these signals (if they are indeed signals) can never be used by somebody to actually send information because it would result in causal loops again. And indeed, if you try to figure out a way to send information you find that nature is just a bit too smart and prevents this.

One things seems clear from these paradoxes. Our current theories are clumsy when we try to explain these quantum mechanical phenomena. Nobody knows why the wave function collapsed, yet it is ingrained in quantum mechanics and widely accepted. In fact, there are no good explanations for these paradoxes. So keep an open mind, even when it come to things that are at odds with everything you have learned in class. Be critical, but don't dismiss too early. Breakthroughs only happen when the unimaginable become reality.

Maxwell's Demon: Computation & Physical Entropy

The second law of thermodynamics states that we cannot decrease the entropy of a closed system on average. This is important because if it would not hold, one could in principle build a "perpetuum mobile" (a machine that generates energy out of thin air). However, this is not a trivial law as we will see in the following. Physicist have repeatedly tried to construct machines (on paper mostly) that would violate the second law. The result of these thought experiments was that information (in the form of abstract sequences of bits) is intricately tied to the notion of physical entropy.

Let's first define entropy of a physical system. The usual definition counts the number of microstates contained in a macrostate. This means that we first have to define the macrostate and this usually involves coarse-graining of the micro-world.
The easiest example is a sequence of T coin-flips. Every sequence has an equal probably to occur, however if we study the space of the number of times heads comes up we can easily see that the entropy of the state N=T/2 is much larger than that of N=T. This is because there is only one unique sequence with N=T but NchooseT sequences of N heads (and this quantity peaks at N=T/2).

For a more realistic physical system let's imagine that we have contained 2N molecules in some volume, N of them are colored white, the remaining N are colored black. Let's divide the space in two imaginary halves and also imagine that the molecules randomly move around (as is realistic). Macrostates are now defined as counting the number of black balls in the left half and the number of white balls in the right half, which we will denote with B(l) and W(r). Again, B(l)=N, W(r)=N has a much lower entropy than B(l=N/2), W(r)=N/2, simply because there are many more ways to accomplish the second macrostate in terms of microstates.

If we use macrostates as the actual microstates themselves, then the entropy will always stay constant because there is exactly 1 microstate state per macrostate. However, if we use coarse-grained macrostates, then the entropy will typically increase, because you will tend to observe macrostates states that are more likely to occur. Thus in the case of the molecules, you will approximately find an equal number of white and black balls in the left and right halves. The second law says that you will not move back from this state to the ordered state of all black balls to the left and all white balls to the right. (There are fluctuations around the average, but with many molecules they are very small and the odds against fluctuating into the completely ordered state or enormous.)


All good so far. But Maxwell invented a "demon" that would build a separating wall between the two halves and control a gate. If a white ball approaches the gate from the left, the demon quickly opens the gate and lets the white ball through. Similarly for a black ball coming from the right (see Figure). The end result is that all black balls end up to the left and all white balls to the right.

So did we break the second law? To start with, the system of the molecules is no longer closed because it now includes the demon. But how will we treat the demon thermodynamically? Our first guess is that the act of moving the gate up and down and measuring the white and black balls as they approach the gate increase the entropy by a significant amount (more than can the demon can decrease the entropy of the environment). Although this is what will usually happen in practice, it turns out that the demon's trick can actually be achieved by a computer with vanishing increase of entropy (of course the construction is subtle, but you will have to take it on faith).

However, the demon will have to obtain information from the system and record it (say on a tape) in order to be able to operate the gate. As it turns out, one can actually decrease the entropy of the molecules in a vat only at the expense of recording the information about the system. Note that we are talking about an abstract sequence of 0's and 1's here. One can show that the act of erasing this information again will necessarily increase the entropy by an amount more then was extracted from the environment in the first place. Again, this is a very subtle argument, because the information needs to be erased irreversibly and that may not be as easy as it looks. Anyway, we will take it for granted now.

This then restores the second law before and after we recorded and erased the information, but what happened in the middle? Did we beat the second law for an arbitrary long time (the time information was recorded on a tape)? In a way yes, and physicist have been forced to change the definition of the second law to include the abstract (Shannon type) information of the sequence of 0's and 1's living on the tape. The new law says that the total entropy of the physical system plus that of the bit-string will not decrease over time. Hence, we have moved some of the entropy of the physical system onto a computer memory and froze it there. The boarders between the real physical world and the abstract world of computer science have been blurred.

This story re-enforces the opinion that physics can be understood as computation ("it from bit" according to Wheeler). But it also points to a potentially deep connection between intelligence (learning systems) and physics. The demon had to study the system and record the information in his "brain" before he could lower the entropy of his environment. But according to a Bayesian, the amount of information obtained by the demon has only meaning relative to his own subjective prior about the world. Is entropy then in the end a subjective quantity? There are many more indications that at least certain aspects about the world are rather subjectively defined (for instance the collapse of the wave function in quantum mechanics leading to the Schrodinger's cat paradox). Is there even an objective world out there? That will have to wait for another blog (;-).

Leaf Blowers (Suck)

Saturday morning 8:00am. The leaf blowers come. Now, we sleep with our windows wide open. So we wake up. Because leaf blowers make a lot of noise. We call that "noise pollution". Especially Saturday morning at 8:00am.

Now let's review the leaf blower. It moves leafs from A to B. In fact it moves leafs away from places where they belong, namely on the ground between your plants. Once, blown on a pile, they can be shipped off. Now, leafs make humus (degraded organic material in soil). Yes, they rot, but the rotting doesn't smell bad. It's natural (really). And as an additional bonus: it makes your soil fertile.



Leaf blowing removes leafs. So now we have to ship-in degraded, other organic material (that actually does smell strongly and is probably made of your leafs in the first place). We call that mulch. In summary: we use a very noisy machine (at 8am) that uses gas to then remove organic material which is then turned into mulch that needs to be shipped back in from far away, once again, using gas. How stupid is that, given that nature has figured out ways to do that all by itself.

However, what I experienced recently went even further. The leaf blowing humanoid was directing his all-powerful blowing machine into a tree (he was a tree blower). The reason was presumably that he wanted the leafs that had turned a little brown to fall off the tree early. As it turns out, trees have evolved to figure this out all by themselves; they do not need help with that (certainly not at 8am).

One more example of how we have alienated ourselves from nature. Half a year ago or so it actually rained in Southern California. I picked up the following phrase when entering a restaurant: "I am going to move back to the desert". Rain is good for plants. In fact, rain is good for people too. So don't complain if it rains; you only have to endure it about twice per year. Try living in Sudan (no rain) or Ireland (always rain).

I worry: when my oldest child got (consciously) confronted with rain for the first time, and I explained that rain made plants grow she said in surprise: "no daddy, sprinklers make plants grow". Yes, that was actually correct. 60% of our water usage is on watering our lawns. That means that we have to drain the Colorado river to the last drop before it hits Mexico, just to water our lawns (and wash our SUVs). Actually, we also drain the west side of the Sierra's Nevada's resulting in "salt storms" in those regions. So let's get rid of those lawns now and replace them with native plants (almost don't need any watering). Additional advantage: lot's of hummingbirds in your garden!

What Language Does Our Universe "Speak"?

Many profound physicist have come to think of physics at the very tiniest length scale (the Planck length) as a computer or information processor. To name a few: John A. Wheeler, Richard Feynman, Roger Penrose, Gerard 't Hooft. Wheeler expressed this view as "it from bit".

One of the main reasons for this view is the realization that physics at that scale will have to be discrete. If not, it becomes very hard to reconcile relativity and quantum mechanics into one theory. In the continuous domain calculation simply blow up: they cannot be re-normalized. In addition to that, the uncertainty principle of quantum mechanics demands that we can not even pinpoint things down to such precision without creating a black hole which would immediately render any measurement at a scale smaller than its horizon impossible....So these physicist think that physics at that scale is some sort of cellular automaton.

Around the end of every century some people seem the need to make the rather absurd claim that science is coming to an end (I believe we have barely started, but anyway). This century this view is expressed in the book: "The End Of Science: Facing The Limits Of Knowledge In The Twilight Of The Scientific Age" by John Horgan. He argues that there are four recent theories that have shown the fundamental limitations of science:
1. Relativity: anything inside the horizon of a black hole will never get out. So we cannot study the inside of a black hole.
2. Quantum Mechanics: the world is irreducibly random.
3. Chaos: The dynamics of many real physical phenomenon displays extreme sensitivity to initial conditions.
4. Complexity Theory: Godel's theorem of incompleteness of formal systems.

Let's see how these theories would fare in the face of a fundamental theory of "Physics as Computation" (PAC). I think the black hole issue is already close to being resolved. A quantum mechanical treatment of BHs will involve BH-radiation (or Hawking radiation). As such, in-falling matter will cause disturbances on the surface of the BH-horizon that encodes the information of the in-falling matter and which will eventually be radiated out again. No information is lost in the process. (Every BH will eventually die in an explosion that is more violent than the most energetic supernova, but it takes a while..) For the observer that stays outside the BH, the BH horizon is the edge of the universe in a very real sense. It will see his colleague that falls into the BH freeze onto the horizon, get disintegrated and eventually be radiated out again in bits and pieces. For the in-falling observer the edge of the universe is not the BH horizon, but a singularity at the center of the BH. In this case we have to deal with a singularity but it seems evident to me that the final PAC theory will describe that singularity not as an infinitely dense point but rather a sensible finite object.

How the irreducibility of quantum mechanics may be resolved in terms of a cellular automaton was described in my previous blog on "Quantum Mechanics is not the Final Theory".

The phenomenon of chaos in nonlinear dynamical systems makes claims on unpredictability of a more every day nature: for instance the weather patterns are unpredictable because a small error in the initial conditions may result in large differences a few days later (except in California where we don't need weather forecasting). The canonical example is this: x[t+1]=2*x[t] mod 1. This means that at every iteration we move all digits one decimal place to the left and set the number to the left of the dot to 0: 0.12345...

Finally Godel's theorem. It says that within any sufficiently complex formal system there will be true theorems that cannot be proved. I am still thinking about these issues, but I seem to have an issue with the notion of "a true theorem". True can only acquire meaning as an interpretation of the formal system (say mapping sequences to mathematical or physical "truths"). But mathematics is itself a formal system. Truth does not exist outside any axiomatic system and the interpretation that Godel's theorem shows that truth is bigger than formal reasoning just doesn't sit well with me. Anyway, some future blogs will unquestionably be devoted to these deep issues.

It will be very interesting to be able to answer the question: "what is the complexity class of the sequences generated by the cellular automaton that governs our universe". Or phrased more informally: "What language does our universe speak". Here is my prediction: Dutch ;-) (or maybe a language of the same complexity). It seems that Dutch is more complex than context-free languages due to cross-referencing but still decidable in polynomial time. It represents a possible level of complexity where things are not too regular but also not too unwieldy. Anyway, my prediction here should be taken with a huge grain of salt of course.


Soooo, the universe is a huge computer that is computing "something". It is our task as scientists to figure what and how it is computing. Actually, we already know the answer: 42 ;-). But what was the original question? Let's leave that to religion.

Complexity

In the previous blog I argued that a truly random sequence can (should) be defined as an incompressible one. A sequence from which nothing can be learned. Moreover, it can be shown (mathematically) that certain deterministic chaotic dynamical systems can indeed generate these random sequences.

If randomness is a slippery subject, complexity is worse. Complexity has turned into an entire research field of its own but is being criticized for not even having a good definition for the term itself. In fact, there seem to be 31 definitions floating around. Complexity is one of those things for which we seem to have a clear intuition but is hard to capture in math.

Let's try to build some intuition first. Consider the tree-image above and compare that to say a completely white image and an image of white noise (your television screen if it receives no signal). We feel that the white image is boring because it is utterly predictable but the noise image is also boring because there is nothing to predict about it. The tree-image on the contrary seems to interesting. There is lots of structure. We want our complexity measure to peak at the tree-image but vanish at boring images and random images. Therefore, complexity should not be equated to randomness.

An attractive definition was given by Murray Gell-Mann (Nobel laureate and inventor of the quark). I will discuss a slightly adapted version of his story. We return to the MDL principle (minimum description length). Given a string of symbols we wish to optimally compress it. That means, we want to build a model with a bunch of parameters, P, and use that model to predict most of the symbols in the sequence correctly. The symbols that were wrongly predicted will have to be stored separately. One can imagine a communication game where I want to send the string to you. Instead of sending the string, I send the model and only those symbols which where predicted wrongly by the model. If you use my model on your end to generate the predictable symbols you have all you need to generate the original string (use the model at the locations where predictions are correct but use the separate list of corrections where the model was wrong). The trick is now to find the model that has the optimal complexity in the sense that the total information necessary to encode the model and the unpredictable symbols is minimized. In other words, I want the procedure that maximally compresses the original string.

There is something fundamentally important about this procedure because it guarantees that the model will be optimally predictive of future data. If your model was too small, there was more structure that you could have predicted in the test string. If on the other hand you use a more complex model, you will have "modeled" the randomness of the input string (called overfitting) and this is obviously not helpful either. Living things survive because they are able to predict the world (and leverage it). It is our business to compress the input stream of our senses!

We are now ready to define complexity: it is the information necessary to encode the model (parameters), excluding the residual random bits of the string that remained unpredictable. A white image has very little information to start with and even though it can all be predicted by our model (no random bits) so the total is still very small. On the other, a random string is completely unpredictable and even though it carries a lot of information (a la Shannon) the model part is zero. Both cases have vanishing complexity as we wanted to, and the tree-image will have lots of complexity.

Complexity is a relative quantity. For instance, it depends on factors such as the length of the string. For small strings it doesn't pay off to use a complicated model. This is not so bad in my opinion, because imagine a primordial world where all that has ever been created is the string "GOD". The string are just three symbols embedded in nothingness. It will only acquire its structure (meaning) after we read the bible.

Another more serious objection is perhaps the fact that the true complexity is in-computable because it can be shown that one can not decide whether the model you have is really the optimal one in general. Imagine the fractal image below.
The image looks wonderfully complex. Who would have thought that there is a really simple algorithm to produce it? So, practically speaking, complexity is defined relative to how good of a modeler you are.

Then there is the issue of scale. If we view the world at a large scale, it may look very predictable. However, the world is composed of quadrizillions of elementary particles that are moving in chaotic motion. At the small scale the world is random, but at a larger scale order emerges through averaging. This may be best illustrated by going back to the coin-toss. If we are asked to predict the next outcome of a coin-flip, we will be at a loss. However, if we are asked to predict the total number of heads over the next 100 coin tosses we can make a good guess (50 for a fair coin). This is because even though every sequence of 0's and 1's is equally likely, there are many more sequences with 50 heads and 50 tails than that there are sequences with only heads for instance.

Finally there is the issue of the time that it needs to compress and decompress the string. We may have found a great model that does a wonderful job at compressing the input string, but that requires a very long computation time to use for encoding and decoding. This seems important at least biologically. If I have a model of lions that takes 5 hours to use (i.e. make predictions with) then it is not very useful in terms of my chances of survival. As another example, consider the Mandelbrot fractal again. There is very small prescription to generate it but one needs considerable time to actually compute that image (in fact, this connects to the previous point because you would have to first specify the scale at which you want to stop otherwise it would take infinitely long).

In machine learning researchers have also started to realize the importance of computation in addition to prediction quality. They acknowledge that modern day problems are so large that a really good model may require too long to train up and use for predictions. So, the computational budget is factored into the total equation, favoring faster algorithms and models over slower ones even though the latter may be more accurate (it is in this sense that machine learning is really different from statistics and in fact the reason why machine learning is in the computer science department and not the mathematics department).

Should we adapt our definition of complexity to accommodate running time? Gell-Mann thinks so and he argues for a bound on the computation time. There are indeed many definitions of complexity, such as "logical depth" that do just that. But if we include computational complexity, shouldn't we also include the amount of memory we need during computation (since they can be traded off)? Uh-oh we are descending in the bottomless pit call complexity research with its 31 definitions. This may be a good point to stop.:-)

Is A Coin Toss Random?

Randomness is a slippery concept. If you teach it in an AI class you are quick to point out that what we call random is really a matter of ignorance: because we don't know and/or model all the details of the world we lump together everything that is outside the scope of our models and call it a random effect. Under this reasoning the toss of a coin is *not* really random in a philosophical sense.

Unless of course, quantum mechanics has anything to do with it. Imagine we toss a coin through a quantum measurement. Now we are confident to claim true randomness. The quantum world is with a nice world "irreducibly random", meaning that there is no deeper theory from which quantum mechanics would emerge and where the coin toss is once again the result of our ignorance. However, as I reported in an earlier blog, there may even be ways out of the seemingly "irreducibly random" nature of quantum mechanics. In this view we are back to square one: what then is randomness?

There is a beautiful definition of randomness in a mathematical discipline called algebraic complexity. To understand this definition let's consider a very long sequence of coin flips. Now let's try to compress this sequence of "HTTTHHHTTHTTTTHHHTHTHTHHH" into a smaller sequence by building a model. If the sequence where just "HTHTHTHTH..." things would be easy: "I will simply state that head and tails alternate and the sequence starts with H (I will have to count the symbols in this sentence as the cost of encoding it). The sequence is not random because I could compress it. The definition of randomness is thus: a sequence is random if it cannot be described (encoded) using a smaller sequence. In terms of learning theory: one cannot learn anything from a random sequences.

Using this definition, a sequence can be random yet and at the same time be generated by a fully deterministic process. This process will have to be "chaotic" which we will not define here but has nothing to do with quantum mechanics. In fact, it snugly fits the definition of a random coin toss. For instance, if you toss a coin in a deep tank of moving water and record whether it landed head or tails on the bottom, then I am pretty sure that the details of the trajectory of the coin are chaotic. Hence, there is no model that can predict anything about the final outcome. This is not because we don't know how to model moving water in a tank, but because trajectories of coins in these tanks have something inherently unpredictable about them.

I therefore conclude that the flip of a coin toss can be truly random and deterministic at the same time. We don't need quantum mechanics for true randomness, we have something far better: chaotic dynamics. In fact, I predict that the so called "irreducible randomness" of quantum mechanics will in the end be reduced to randomness derived from chaotic dynamics.

On Intelligent Design

Consider the following reasoning I witnessed a while back at a parent meeting. Some trees are so tall that there is no scientific explanation for the fact that these trees can pump water from its roots all the way up to its top (I actually seriously doubts that there is no explanation but let's ignore that for now.) Therefore there exists a upward force that pushes things in the opposite direction as gravity...

What is the problem here. I claim there are two fallacies in the logic. Firstly, the fact that we currently don't have an explanation for some phenomenon in terms of ordinary physics, doesn't mean there is none. A scientist should readily admit that many measurable phenomenon remain unexplained today. It doesn't mean that we have to introduce a new mysterious force. Secondly, the "upward force" feels like a valid explanation, however we have just given the unexplained phenomenon a new name. Instead of saying "I don't know the answer to this question" we say "I know the answer, it is X". It turns out this is just another way of saying the same thing. Giving names to things generates the illusion that we understand it. And people really don't like to not understand things. Our survival depends on it, so it to give us peace of mind to simply delude ourselves.

Isn't this is even true in real science? Apparently, when Feynman asked his father about the reason why objects tend to persist in their straight motion, his father said something of the sort. That's because momentum is conserved. But he warned the young Feynman that giving something a distinguished name isn't the same as explaining it.

When does something become an explanation then? Isn't all we are doing just giving names to things? Well no, the distinguishing factor is prediction. When you can genuinely predict a new phenomenon, then you have found useful structure in the world. Whatever your naming conventions, that predictive power is useful and real.

Now to intelligent design (ID). In ID, the most scientific concept seems to be "irreducible complexity (IC)". This idea should be given a chance. If someone can compute the IC of some complex system as the gap in complexity between the system under study the next simplest version of the system that still performs some useful function, than that seems like a genuine advance. Note though that this is extremely difficult because one would have to search over all possible complex systems that can lead to the system under study and one would have to have a notion of what it means to be useful. I believe these problems basically make the concept of irreducible complexity a non-starter, but we want to be extremely open minded here.

Where things go desperately wrong is when we think we found a system that has a high irreducible complexity and then exclaim that therefore it must be designed by an intelligent designer (aka God). This is like the tree example: we have shown that contemporary science cannot explain the phenomenon and therefore we give the problem another name, namely God. However, stating that God designed certain things in the world does not make us understand and thus predict the phenomenon any better. Our attitude should be: 1) maybe Darwin's version of evolution needs to be improved to properly explain structures with high irreducible complexity, or 2) perhaps our estimate of the irreducible complexity was wrong and we need to look harder for simpler functional structures that could evolve into the "problematic" structure.

Personally, I am very tolerant to religion. It brings some good and some bad things to people, but everyone should make up their own mind on these issues. It would be arrogant to claim there is no God. My hope is that we can teach religion in schools on an objective level. I favor teaching all religions to our children, not just one. However, I do not believe science and religion should be mixed. They live on different planes. Trying to prove the existence of God is a lost battle. Trying to prove that someone performed three miracles and then declaring that person saint is simply silly (at the level of Santa Claus). Declaring the existence of God based on the fact that you (supposedly) cannot explain some natural phenomenon using modern science is equally backward.