Nature's Computer

Today, I try to form some arguments about computational nature of nature itself. From previous post on Emperor's new mind it is clear that out brain is non-computational in nature. What do we mean by non-computability? It's a subtle concept,but I try to define it for laity(Bye the way, I am too a laity :)). Imagine your computer has been empowered with infinite RAM and infinite hard-disk by some magical means. Now anything this computer can compute is said to be computable on the condition that it never uses whole of the infinite resources, it can use as much RAM as it wants and as much hard-disc as it wants but it has to be finite at every step of its operation. We don't care about the speed of this computer, as long as it can do something in finite time, that thing is by definition computable even if the time taken is trillions of years. So we know that our brain is non-computational, means that it can't be simulated by a computer. It seems pretty logical to me that our brain and we as whole follow the rules of nature(some of the rules we know by physics, some we don't know). Nature would be partial if it allowed humans to violate it's laws. So nature along with brain must be non-computational. So now can we imagine anything in nature that seems to be non-computable?. The model of the nature(universe) proposed by Einstein and Newton can easily be simulated on a computer given enough resources. If we have to have even a bit of trust in our knowledge of nature's laws, we have to find at least one problem which is impossible for our magic computer to solve but nature solves that problem easily. Can you think of anything?. Now I will try to show a problem of this kind. It's none other than random number generation. I believe that our magical computer can't generate purely random numbers. What do I mean by purely random?. By purely random I mean that it's impossible to predict the outcome even theoretically. Some might say that every programming language provides a random number generator function, that seems to be purely random. But reality is that internally these functions calculate these pseudo random numbers by many parameters( may be system clock's time, RAM usage,number of processes etc.). Although practically it seems quite impossible to predict the output yet if a person knows values of these parameters at the time of random number generation, he/she can easily predict the output. So how nature solves this problem?. It's pretty easy for nature. Let's say we want any number from 1 to n purely randomly. All we have to do is construct a quantum system which has n eigen states in superposition. When we perform a measurement, it jumps to a particular eigen state purely randomly. So nature provides a pure random number generator. There are no parameters. What can be the implications of this for other non-computable problems. For example, halting problem is non-computable. Is it possible that nature has a solution for halting problem also?. I don't know the answer to that question. I would like to add one more example of nature's majestic computational powers. This one comes from one of the very few classes I attended in college. Suppose we have n numbers, we want to sort them. The minimum number of steps that a computer will take to solve this problem is roughly (n log(n)). Nature can do it in almost 1 step. Everybody must have heard of prism, the magical device which forms aesthetic spectrum from sun light. The prism is basically doing the sorting of different wavelengths to produce that spectrum. That way nature solves sorting problem in 1 easy step. Of course I am assuming is that even if visible light would have consisted of 10 colors instead of 7, prism would have taken same time to produce the beautiful spectrum. This assumption does not seem far-fetched to me. With this, I hibernate my brain's non-computational computer.

The quantum amusements

Quantum mechanics started as an attempt to concoct a discretized model of nature. Einstein's explanation of photo electric effect by using Plank's quanta model of light provided the ignition quantum mechanics needed to rock the scientific community. When the whole scientific world was busy celebrating the success of Einstein's General relativity and Special relativity, the few other scientists very busy creating their share of history. The success of Einstein's General relativity had huge impact on how physics and in general science had to studied and discovered. The rules were simple and elegant, define some properties for any physical object and try to concoct a theory on how these properties and variables were going to evolve with time. Einstein's General relativity dealt with position, velocity and acceleration as these variables. Somehow, some other great scientists such as Bohr, Schroedinger, Heisenberg did not get the memo of these rules. They themselves devised a theory which questioned the very existence of these variables and their values. Einstein's universe was purely a deterministic universe. If state of the universe at any particular moment is known, then there exists physical laws which will determine universe's state at any time of future and past. Here by "State", we mean the values of these "Properties" or variables(position, velocity, acceleration , spin etc.) for every particle of this universe. Einsteins idea was simple, even if we don't know the values of these variables in current state and we also don't know the physical laws according to which these variables evolve, there are some values of these properties which are there and also are laws according to which these variables evolve. Einstein's deterministic universe left no space for any free will which we feel. Einstein used to call "free will" as an illusion of human prejudices. Then came Heisenberg's uncertainty principle which said that natures itself introduces randomness to values of these variables. Heisenberg uncertainty principle asserts that it's not merely practical limitation on some value's calculation, in fact that it's meaningless to ask for the value of that variable before the measurement has been made. Basically, it says that there is no reality evolving with time unless you make a measurement. And what value we will get on measurement, is purely random. We can only know the probabilities. Bohr was ardent supporter of this idea. Einstein was totally against this idea. "God doesn't play dice with universe", He Said. He proposed that toss of dice also looks probabilistic from the first glance, but if we exactly know all the variables(velocity, spin , air friction etc) at the time of toss, we can exactly predict which number we are going to get with the toss. He asserted that such variables should also exists for quantum mechanics which will predict the outcome of quantum measurements correctly in each case rather than just assigning probabilities. In 1927 Solvay conference, Einstein came up with several thought experiments which tried to show shortcomings of Heisenberg Uncertainty principle. For every thought experiment, Bohr had answer. Interestingly, in one of the answers, Bohr used Einstein's General relativity to controvert the Einstein's thought experiment. Einstein's continued his quest to prove that quantum mechanics did not provide complete picture of nature's mechanism. In 1935, He published a paper known as EPR paradox. I will not go into the details, but paper basically demonstrated a thought experiment which showed that reality exists even before you measure it. For once it seemed that Einstein had controverted quantum mechanics. This time even great Bohr had no answer. Einstein died thinking that quantum mechanics was an incomplete theory. In 1964, Bell came with an inequality which has to hold for any theory which is local in nature(all effects are local) and which assumes some real values of variables even before measurement. It was found that Quantum mechanics violates that inequality. So indirectly it was proved that no one could concoct a theory in agreement with quantum mechanics which predicts the variables before measurement and which is also local in nature. Einstein's dream died with this theorem. We constantly talk about reality, but it does not even exists before we measure it. Reality or locality, make a choice!!

Emperor's New Mind

This is my first attempt at not-so trivial art of blogging. I fail to understand why people blog or even read blogs for that matter. I decided to get my hands dirty to understand the very reason. For the first post, I have nothing interesting to write. So I guess I will start with some of the activities I am doing these days. Recently I finished the book The Emperor's New Mind. It was certainly a great read. Mr. Roger Penrose (Yeah, the same guy who is responsible for Penerose diagrams we study in General relativity and black holes). The debate is this book is the same old formula used by many sci-fi robot movies, only the approach is different. The debate is on Will robots ever be able to emulate humans. First of all, the definition of behaving like humans is not clear at all. The only definition or test we can use is Turing Test proposed by the great British mathematician Alan Turing. The test is basically an interrogation test, A judge interrogates two players A(Human) and B(Machine). Both try to prove that they are Humans. If B can succeed in convincing that judge that it is a human, it deserves to be called human. In this test also, the kind of interrogation that can be performed is also not very clear. So still the definition is not very clear. But we move on with this definition. Penerose argues for the fact that Robots will never emulate humans. The reasons he gives are very convincing. The most convincing reason is the Godel's Incompleteness theorem. In 1900, the great German Mathematician David Hilbert proposed a program to formalize all of mathematics with some basic axioms and some inference rules(Which are so intuitively true that No one doubts their validity). He proposed that from these very basic axioms and inference rules, we should be able to prove or disprove any statement that can be stated mathematically. Moreover, this system of axioms and inference rules should be consistent. Here consistency means that you can't infer both a statement and it's opposite from these set of axioms and inference rules. World's finest brains began to work on Hilbert's Dream. Whoever could do this , was guaranteed a name in golden letters in mathematics history. But in 1931, Kurt Gödel the austrian genius dropped a bomb on mathematics whose damage won't be recovered till the eternity. In a very simple and short paper, He proved that no matter what are your axioms and inference rules, in every theory there will be statements whose trueness or falsity will never be determined. If you find that unconvincing, try to think of trueness or falsity of the statement "This statement is false." Moreover, he proved that consistency or inconsistency of the theory cannot be decided by rules or axioms of the theory. On one short paper, he crushed the Hilbert's dream. Penerose forms the very same theorem as base of his argument. The basic argument is that an undecidable statement is true in some sense because if it had not, be would be able to find the counterexample by exhausting out all the cases. Now try this problems on a robot, Give him a "Set of axioms" and "Set of Inference Rules". The robot will keep searching till eternity and won't be able to decide the trueness of some statements. The very fact that we can see the undecidability of such statements makes us different from robots. It seems very convincing to my naive mind. The rest of books deals with problem of determinism and consciousness. He tries to propose a idea for solving quantum measurement problem. He also proposes that very quantum measurement is the process which gives direction to time. And the very direction of time gives meaning to our consciousness. The rest of book is an adventurous trip to the the world of science and mathematics. I would highly recommend this book who is looking for an adventurous and intellectual journey. I would like to sum up this post by a statement which is favorite of mine, Reality is stranger than science fiction.

Bombs

Recently, I came across a wonderful puzzle. The puzzles goes like this. You are given some (let's say m + n) bombs. Each bomb has a push button, bomb explodes by pushing that button. A bomb is faulty if it's push button is jammed, so it's of no use. Every faulty bomb can have only one defect and that is jamming of it's push button, otherwise bomb works. Now assume that some of these bombs are faulty (let's say m)and some are working (let's say n). Can we devise a strategy to get at least one working bomb from these n working bombs?. If we can't do it for sure, can we devise a strategy such that probability for getting a working bomb is maximum?