amazon.com amazon.co.uk Amazon Number One
Quantum Introduction The Quantum Casino Quantum Entanglement Quantum Decoherence Reality Is Relative The Block Universe
The Arrow of Time The Anthropic Principle The Mathematical Universe Is the Universe
a Computer?
Living in the Matrix The Intelligent Universe
Back to the main page

"I am thinking about something much more important than bombs. I am thinking about computers." - John von Neumann, 1946

Is the Universe a Computer?

There is a currently fashionable idea in physics to treat the behaviour of the universe as if it were a vast, digital computer. The universe is described by information, and that information is modified over time just like information is transformed in a conventional computer.

We could consider the position (and velocity) of each particle as representing one "bit" of information within the universe, just like a conventional computer contains binary "1"s and "0"s. The universe can then be viewed as an "information processor", just like any conventional computer: the data within the computer (universe) is transformed as time progresses.

So if the universe is a computer, then what, precisely, is it computing? What is its output? Well, the output is the state of the universe: the sum total of all the positions and velocities of all the particles within the universe. As Seth Lloyd says in his book "Programming the Universe": "What does the universe compute? It computes itself". He goes on to say: "The world is composed of elementary particles - electrons, photons, quarks - and each elementary piece of a physical system registers a chunk of information: one particle, one bit. When these pieces interact, they transform and process that information, bit by bit. Each collision between elementary particles acts as a simple logical operation".

It's as if we are stepping through a computer program, each step of the algorithm modifying the states of the computer variables and registers. As John Barrow says: "We now have an image of the universe as a great computer program, whose software consists of the laws of nature which run on hardware composed of the elementary particles of nature."

(Note that this is a subtly different idea to the claim that the universe is some sort of Matrix-style simulated reality created by an advanced simulation. That theory is considered on the Living in the Matrix page. On this page we are just examining the idea that the physical universe can be thought of as behaving as though it was a form of digital computer, with the constituent physical parts of the universe (the particles) behaving as though they were data bits of a computer.)

For further reading on this topic, Jürgen Schmidhuber has written a paper called A Computer Scientist's View of Life, the Universe, and Everything in which he analyzes some of the implications of actually writing a computer program equivalent to our universe. There is also a four-page Wired article: God is the Machine. There is also a Wikipedia entry on this topic: Digital Physics. There is also a video lecture online by Seth Lloyd recorded at the Perimeter Institute: Programming the Universe.

The Universe as Information

There is currently a fashion in physics to treat all of the physical world as though it was information. This certainly ties in with the idea of the universe behaving as though it was a computer: basically we can ask questions about the physical world, but the only response we can ever receive will be in the form of information. The idea was originally proposed by John Wheeler: "About a decade ago, John Archibald Wheeler urged that information should take centre stage. What we call reality, he thinks, arises from the questions we ask about it and the responses we receive. "Tomorrow, we will have learned to understand and express all of physics in the language of information", he said. The atom of information is the bit: the quantity contained in the answer to a yes or no question. If experiments are questions we ask of nature, then the simplest of them have yes or no answers: "Did the photon arrive here, or not?", "Did the counter click, or not?" We can also ask more complex questions, but they can always be built up from simpler yes or no questions like these." (quote taken from here).

I feel the motivation for this approach to physics comes from the difficulty we have in defining what is physical, tangible, reality: what, precisely, is a particle? In the absence of any suitable definition of physical reality, all we have left is the yes/no answer to our questions about the environment around us. At the end of the day, all we really have left is information, and that information is all we have to define our real, tangible universe. Ed Fredkin said: "I've come to the conclusion that the most concrete thing in the world is information" (quoted from here).

So that information effectively becomes our reality. John Wheeler referred to this process by which tangible reality emerges from pure information as It from Bit. The yes/no "bits" of information (in our universe computer) then represent individual particles.

The MP3 Universe
This fashionable trend in physics moving from a physically-oriented view of the world to one of pure information could be considered as being similar to the transition in audio recording formats. These have moved from a physical analogue approach (vinyl records), to a physical digital approach (CD), to a format of pure information (MP3) which is independent of any physical storage medium.

Information is then viewed as more fundamental than any "physical" entity: "Ask anybody what the physical world is made of, and you are likely to be told "matter and energy". Yet if we have learned anything from engineering, biology and physics, information is just as crucial an ingredient. Indeed, a current trend, initiated by John A. Wheeler of Princeton University, is to regard the physical world as made of information, with energy and matter as incidentals" (quote taken from here).

This view of information as being fundamental means information should never get lost (this is a corollary of Landauer's Principle). This has led to the infamous black hole information loss paradox: "Physicists often talk about information rather than matter because information is thought to be more fundamental".

There is a video discussion on this subject recorded at the Perimeter Institute featuring Seth Lloyd, Anthony Leggett, and Leonard Susskind: The Physics of Information.

The Monkey Universe

In his book Programming the Universe, Seth Lloyd considers how the structure of the universe could have been produced by a million monkeys typing on typewriters for ten hours a day. Clearly, the chances of one of them successfully typing the information which defines the universe is almost infinitely small. However, he then considers what would happen if the monkeys typed into computers rather than typewriters. The computer then interprets the monkey's random output not as text but as a computer program, i.e., as a sequence of instructions in a particular computer language. It is now possible for a short program (with a relatively high probability of being typed by a monkey) to produce the vast complexity of our universe. For example, a few lines of computer code can produce the infinite sequence of random digits of , or could produce highly-complex fractals.

Give a monkey a typewriter and you'll just get a load of rubbish ...
... but give him a laptop computer and he might write a (very) simple computer program which could produce something highly-complex.

Hence, this analogy of the universe being a computer proves valuable in providing an explanation as to how the complexity of the universe could arise from a short computer program. (For a technical description of this, see Section 3 of Seth Lloyd's paper Universe as Quantum Computer).

This "Monkey Universe" idea is revisited on the Living in the Matrix page.

The Game of Life

Perhaps we can see the universe behaving like a computer when we consider the Game of Life computer program, which was developed by John Conway in 1970. The Game of Life is a form of artificial life simulation in which cells on a square grid can evolve (live, die, or remain unchanged) according to simple mathematical rules:

  1. A dead cell with exactly three live neighbours becomes a live cell (birth).
  2. A live cell with two or three live neighbours stays alive (survival).
  3. In all other cases, a cell dies or remains dead (overcrowding or loneliness).

The behaviour of the cells is clearly very similar to the development of living cells on a Petri dish.

The Game of Life is an example of cellular automata. The field is dominated by Stephen Wolfram - see this Forbes article. According to that article: "Conway himself, soon began to wonder if a giant Game of Life played on an equally giant computer wouldn't create its own living, breathing universe. Perhaps, Conway and his acolytes mused, we are merely cells on God's great grid."

Game of Life applet instructions

Using your mouse, just click in the grid below to draw yellow shapes and dots, then click the Start button to run the simulation. You can even click inside the grid while it is running!
(You need to have Java installed in your browser to run the applet, so if you cannot see the grid immediately below, go to www.java.com to get the Java Runtime Environment for your browser).
(Applet created by Edwin Martin)

(Your browser does not support Java. Go to www.java.com to get the Java Runtime Environment for your browser. Try the Manual Download if the automatic installation does not work.)

The Turing Machine and Non-Computability

In the 1936, the British mathematician Alan Turing proposed a design for a generalised computer which is now known as a Turing Machine. The machine was composed of a tape on which symbols were imprinted, and that tape could move backwards and forwards in the machine. The symbols on the tape represented instructions for the computer. The machine was capable of reading the instructions off the tape, and writing the resultant output data back to the tape:

Turing Machine

The remarkable and important feature of a Turing Machine is that it is universal in that it can compute any computable function. In other words, if you can compute something on any computer, you can compute it on a Turing Machine (this remarkable discovery led to the general-purpose processor and modern computing). So a Turing Machine is effectively equivalent to one of today's common digital computers - a PC. Indeed, it is perhaps easier to think of what is possible on a PC when we consider the function of a Turing Machine.

The Turing Machine appears technologically primitive, but it was intended as a "thought experiment" rather than a practical implementation. Alan Turing intended it as a means to show that there are some problems which can never be solved by a particular computer, and it is these non-computable problems we will consider next (well, after the next blue box bit).

How Turing's Universal Computer applies to you

So we have discussed how Turing's Universal Computer is capable of computing anything which can be computed on any other computer. This is because the solution to any problem can be computed in a step-by-step manner, each step being a very simple operation (the Turing Machine considers writing simple symbols to a tape).

Now, what is quite fascinating is that your brain is itself a Universal Computer, a form of Turing Machine, in that it is certainly capable of manipulating simple symbols and storing data. So if your brain is a Universal Computer, then your brain is capable of computing (or understanding) anything which can be computed or understood by any other brain.

So you are actually capable of computing or understanding anything which anyone else can understand: even when considering the brain of a genius such as Einstein. As long as a problem is split-up into a series of simple steps, you should be able to follow the steps and come to the same conclusions. (Though it might take you considerably longer than Einstein! The Turing Machine says nothing about how long it takes to compute the solution to a problem, it just considers whether a solution is computable or not).

Of course, this principle is not going to help you win TV general knowledge quizzes (not like me ) which are merely tests of factual recall - an entirely different skill. But it should give you confidence once you realise you are in possession of a brain which can compute, or understand, anything which Einstein could understand.

The Halting Problem

Gödel's Incompleteness Theorem in mathematics states that for a particular, specified Formal Axiomatic System (FAS) (i.e., a mathematical set of theorems built-up from fundamental axioms) then there will always be a theorem which is true but you cannot prove (from those particular axioms). That theorem is then said to be undecidable (for that particular FAS). (For more details of Gödel's Incompleteness Theorem, see the Meta Maths section on the Mathematical Universe page).

Likewise, Turing found a very similar result in computing. Let's imagine we have a computer program and we want to know if it will halt (i.e., return a result) or not (i.e., by getting stuck in an infinite loop). Now, just running the program will not give us an answer for all cases because even if the program does not halt after 1,000 years that does not prove that it will never halt - it might halt after 1,001 years. So there is is no way to tell if a program will never halt just by running it. As Gregory Chaitin says in his book, "Meta Maths": "If it does halt, you can eventually discover that. The problem is to decide when to give up and decide that it will never halt. But there is no way to do that."

So, with this in mind that it is impossible to get a definite answer by running the program, let's try to find an answer by writing a second really intelligent program (let's call it a halting tester) which will tell if the first program will halt or not merely by examining the code, by doing some sort of pattern recognition on the code, but not by running the program.

Now, Turing's Halting Problem result says that for that particular halting tester there will always exist a program which it is unable to tell whether it halts or not: the problem is said to be uncomputable. This will be the case if the algorithmic complexity of the program we are testing is greater than the algorithmic complexity of our halting tester program. Our halting tester will be simply not up to the job - the question is too hard for it.

So there is a very close connection between an FAS in maths (and Gödel's Incompleteness Theorem) and a halting tester computer program (and Turing's Halting Problem). Given a specific FAS or halting tester there will always be a theorem which it cannot prove to be true or a program which it cannot tell if it halts or not.

Proof of the Halting Problem

The proof of the halting problem is beautiful, and it's worth presenting it here. An excellent, clear proof of the halting problem is presented in Understanding the Halting Problem, and this is adapted into graphical form here:

The first step of this proof is to imagine we have managed to create our "halting tester" (see last section) which can solve the halting problem for all computer programs (we will later show that this results in a contradiction, so this perfect halting tester could never actually exist). The halting tester program is called HaltTest and it takes two inputs:

  1. A program, P.
  2. An input, I, for the program P.

The output of HaltTest is "Loop" if the program P goes into an infinite loop when it is given I as input. Alternatively, HaltTest outputs "Halt" if the program P halts:

For the next step, it is important to realise that a computer program can be expressed as a sequence of bytes: binary data. So a computer program can be treated as input data, and we can input the same program, P, to both inputs of HaltTest:

The next step is to construct a simple algorithm called StrangeProgram that takes the output of HaltTest and does the following:

  1. If HaltTest outputs "Loop" then StrangeProgram halts.
  2. If HaltTest outputs "Halt" then StrangeProgram goes into an infinite loop.

That is, StrangeProgram does the reverse of HaltTest's output. Here is the code for StrangeProgram:

and here is the graphical representation of StrangeProgram:

The final stage is to feed the function StrangeProgram back into itself as input:

StrangeProgram(StrangeProgram)

and the graphical representation of that is shown here:

Now let's consider this rather peculiar arrangement. There are two possible situations depending on the output of HaltTest:

  1. If HaltTest says that StrangeProgram halts when fed itself as input, then StrangeProgram goes into an infinite loop.
  2. If HaltTest says that StrangeProgram goes into an infinite loop when fed itself as input, then StrangeProgram halts.

In either case, HaltTest gives the wrong result for StrangeProgram. Therefore, our "perfect" HaltTest program does not work for all cases. It is therefore not possible to create a "halting tester" algorithm which can test for all cases of halting programs.

Diophantine Equations

The halting problem (and non-computability in general) has serious implications for mathematics. The Diophantine equations, for example, are a group of equations in which the unknowns must be positive integers (natural numbers).

The most famous Diophantine equation is Fermat's Last Theorem which states that there are no positive integers x, y, and z which satisfy the equation:

xn + yn = zn   for n > 2

To solve a Diophantine equation on a computer would involve progressively searching through all the integers until a set of integers is found which satisfies the equation. However, if you fail to find a set of suitable integers on your progressive search, there is no way of knowing if there is not still a set of suitable larger integers out there waiting to be found. So you would be unable to say for certain that the equation cannot be solved. Do you see the similarity with the halting problem, waiting to see if a computer program halts? Even if your program has not yet halted, that is not to say it might not halt in the distant future. So if you try to use a computer to solve a Diophantine equation you will be unable to say that it cannot be solved for the same reason that you cannot say for definite that a program will never halt. A solution might be found in the future, just like a computer program might halt in the future.

So just like in the halting problem example, we might be tempted to build the equivalent of a "halting tester" program which could analyse a Diophantine equation and say whether it has any solutions. This would involve writing a program to loop through all possible integers, substituting them into the Diophantine equation. We wouldn't actually run that program - we would just pass it to be analysed by our halting tester to determine if the program halts and outputs a solution. If it halts we would know that the Diophantine equation had a solution. However, this approach would be doomed to failure because of the halting problem: the halting tester would never be able to tell if the program halted or not (see here).

Are there uncomputable functions in physical reality?

We now move on to consider the million-dollar question: are there any uncomputable functions in physical reality? This is such an important question because if it could be shown that there were uncomputable functions in the way the universe works it would kill stone dead the idea that the universe behaves like a computer.

If we believe in Max Tegmark's idea that the universe is a purely mathematical construct (see the section "Max Tegmark's Mathematical Universe" on the Mathematical Universe page) then we would expect to find uncomputable functions in the universe as there are certainly uncomputable functions in mathematics, and Tegmark's idea is that reality is mathematics. So if uncomputable functions do not appear in physical reality then there must be some constraints imposed somehow, limiting the subset of mathematics which has relevance to our universe. Those constraints would be responsible for "filtering-out" the uncomputable functions so they would not appear in physical reality.

But if uncomputable functions are to be somehow filtered-out then how might this be achieved? I think it is useful at this point to examine the proof of the halting problem (given in the section above). In that proof, we initially proposed the idea that we could build a "halting tester" program capable of answering any question purely by running through its mechanised process. So the functioning of that halting tester was unhindered by the presence of any uncomputable functions which it was incapable of solving. So we can think of the smooth functioning of that halting tester as the smooth functioning of a "universe computer", if that universe contains no troublesome uncomputable functions. So let's start our analysis by thinking of our universe as that "halting tester" in the earlier discussion about the halting problem.

What we discovered in that halting problem proof was that we were able to construct a peculiar function called StrangeProgram which basically broke our halting tester. StrangeProgram showed that our HaltTest program which tested for halting programs did not work in all cases. So what was it about StrangeProgram that proved so destructive to the smooth operation of our halting tester? And could a form of StrangeProgram exist in physical reality, breaking our "computer universe" model by proving that uncomputable functions existed in our universe?

StrangeProgram worked firstly by taking the output of the HaltTest function and inverting it (see the discussion in the section above for more details). The final step of the proof was to create a form of feedback loop so that StrangeProgram fed back into itself in a recursive manner:

StrangeProgram(StrangeProgram)

The result of this feedback loop was that whatever came out of HaltTest got inverted and fed back into HaltTest, leading to a form of unstable oscillator: if the output of HaltTest said "Halt" then the input of HaltTest was switched to make the output say "Loop", and if the output of HaltTest said "Loop" then the input was switched to make the output say "Halt".

The Halting Problem proof

If this situation was in physical reality it would lead to a logical inconsistency: a paradox. The output of HaltTest could not be both "Loop" and "Halt". In physical reality, an object cannot be two things. For example, an object cannot be both present and absent at the same time. So if the halting problem is to have relevance in physical reality (as opposed to a purely mathematical conceptual model) we should consider if such a paradox could possibly occur in physical reality.

The Grandfather Paradox

It seems to me that it was the inclusion of the inverting function (StrangeProgram) together with the recursive feedback loop which causes all the problems. I wondered if there could possibly be a similar situation in physical reality, and I think the grandfather paradox is equivalent. In the grandfather paradox a man travels back in time and kills his own grandfather before the latter met the traveller's grandmother. According to Wikipedia: "As a result, one of the traveller's parents (and by extension, the traveller himself) would never have been conceived. This would imply that he could not have travelled back in time after all, which in turn implies the grandfather would still be alive, and the traveller would have been conceived, allowing him to travel back in time and kill his grandfather. Thus each possibility seems to imply its own negation."

So just as in the halting problem proof, we get the same sort of feedback loop and negation that proves so troublesome. So we end up with the same sort of oscillatory paradox that we found in the halting problem proof. And the structure of the grandfather paradox is also very similar to the structure of the halting problem proof:

The Grandfather Paradox

Note that this "grandfather paradox" program is now running on the "universe computer" itself, not just any old PC as in the halting problem proof. So the input to the grandfather paradox structure is no longer a simple computer program, but rather it is the software of the universe itself: the state of the universe.

The grandfather paradox structure (shown in the diagram immediately above) functions in the same way as the halting problem proof. The HaltTest of the halting problem (which took a computer program as input) is replaced by a GrandfatherAliveTest (which takes the state of the universe as input and inspects to see if the grandfather is alive). The effect of the time travel backward in time is to effectively feed the whole "situation" - the state of the universe - back into itself in a recursive manner:

StrangeProgram(StrangeProgram)

Hence we finish with the same paradoxical situation as in the halting problem proof.

So the question of whether or not uncomputable functions could exist in physical reality would depend on whether we could get this form of recursive situation caused by backward time travel, or whether it would be prohibited (filtered-out) by some law such as Stephen Hawking's chronology protection conjecture.

Admittedly, the halting problem is just one form of uncomputable problem, but I think it represents an excellent case study to analyse the sort of "filtering" which would be required if there were to be no uncomputable functions in physical reality. I think it's especially interesting that this type of uncomputable problem would lead to logical inconsistencies in physical reality (the grandfather being both dead and alive at the same time). As we know there are no inconsistencies in physical reality this leads me to believe that there are no uncomputable functions in physical reality.

However, this does not prevent us from discussing and imagining all mathematical structures, even uncomputable ones. As Schmidhuber suggests here, we can talk about time travel and the grandfather paradox even if time travel is not possible in our universe: "Although we live in a computable universe, we occasionally chat about incomputable things, such as the halting probability of a universal Turing machine (which is closely related to Gödel's incompleteness theorem). And we sometimes discuss inconsistent worlds in which, say, time travel is possible. Talk about such worlds, however, does not violate the consistency of the processes underlying it."

The idea that there are no uncomputable functions in the universe is in line with Max Tegmark's proposal for a Mathematical Universe which includes a Computable Universe Hypothesis (CUH). The CUH proposes that physical reality can be entirely described by computable functions (in order to avoid all the paradoxes and inconsistencies which would otherwise wreck the Mathematical Universe): "According to the CUH, the mathematical structure that is our universe is computable and hence well-defined in the strong sense that all its relations can be computed. There are thus no physical aspects of our universe that are uncomputable/undecidable, eliminating the concern that Gödel's work makes it somehow incomplete or inconsistent" (for more on this, see the section And now ... the Ultiverse! on the Anthropic Principle page). Max Tegmark was forced to append the CUH to his Mathematical Universe model in order to retain the idea that the universe is created by mathematics, in order to avoid destructive paradoxes (see the section "Max Tegmark's Mathematical Universe" on the Mathematical Universe page).

"The integers were made by God; all else is the work of man."
- Leopold Kronecker

Mathematical Constructivism
(or ... "Why are there apparently no non-computable functions in the universe?")

So, as just discussed in the previous section, if it could be shown that there were uncomputable functions in physical reality then it would kill stone dead the idea that the universe behaves like a computer. However, fortunately, so far it would appear that every aspect of the universe's behaviour can be modelled on a computer. For example, we can plot the orbits of the planets around the Sun using a computer. So if there are no non-computable functions in the universe, why should this be the case? In order to provide a possible answer to this question, we will examine a radical approach to mathematics: constructivism.

Constructivism says that mathematics should only include statements which can be deduced by a finite sequence of step-by-step constructions, starting from the "natural" numbers (1, 2, 3, etc.). This is a major departure from conventional maths because many of the more exotic mathematical structures (such as infinity, and irrational numbers) would not be eligible as part of maths under the strict rules of constructivism. To quote Gregory Chaitin from his book MetaMaths (in an attack on the existence of irrational numbers which are generated from an infinite series): "Some mathematicians have what is called a 'constructive' attitude. This means that they only believe in mathematical objects that can be constructed, that, given enough time, in theory one could actually calculate. They think that there ought to be some way to calculate a real number, to calculate it digit by digit, otherwise in what sense can it be said to have some kind of mathematical existence?"

So why is constructivism relevant to our current discussion? Well, it's because computers construct their results in precisely the same step-by-step method as constructivism. And if the structure of the universe can really be thought of as the product of some form of computer program then mathematical constructivism would appear to be the perfect type of mathematics to model the universe.

Viewed this way, the absence of exotic mathematical structures - such as infinity - from mathematical constructivism now seems like less of a major omission: if there are no infinities in physical reality then it does not matter if there are no infinities in a mathematics based on constructivism. And if the structure of spacetime is discrete at very small scales (rather than continuous) as many physicists now believe then the integer natural numbers of constructivism are sufficient to describe our world, rather than requiring the infinite-precision irrational numbers (which are prohibited under constructivism). In fact, constructivism might now be appearing to be a perfect tool for describing the "real world".

As discussed at the end of the previous section, Max Tegmark had to append a Computable Universe Hypothesis (CUH) to his Mathematical Universe paper in order to avoid destructive paradoxes. Tegmark suggested the behaviour of the universe was restricted to computable functions, and went on to suggest that mathematical constructivism played a role in determining this behaviour: "According to the finitist school of mathematicians (which included Kronecker, Weyl and Goodstein), representing an extreme form of so-called intuitionism and constructivism, a mathematical object does not exist unless it can be constructed from natural numbers in a finite number of steps. This leads directly to a computable structure (a computable universe)."

To sum-up, it appears that there might be no non-computable functions in the universe: a mathematics based on constructivism might be the best tool to describe the universe. So I think it's important to state something which might appear obvious but I have never actually seen written-down anywhere: if the universe DOES behave like a computer, then there would be NO non-computable functions in the universe. Like I say, pretty obvious, though it's important to state it as it is the most obvious reason where there might be no non-computable functions in the universe.

Referring to the diagram above, perhaps mathematical constructivism suggests a universe which is "built-up" out of nothing rather than "carved" out of everything. This diagram and idea is considered in the section From Ultiverse ... To Nulltiverse! at the end of the Anthropic Principle page. Instead of a situation in which absolutely everything exists without need of a reason, we would now have a situation in which absolutely nothing would exist without a good reason for its existence. We would then have to consider ex nihilo (creation out of nothing) scenarios for the universe.

Arguments against the universe behaving like a computer

Several physicists have raised objections to this idea of the universe behaving like a computer. Their objections have generally presented examples of non-computable behaviour in the universe (so the universe could not possibly have computed those functions).

For example, if quantum behaviour is fundamentally, genuinely random (as opposed to just pseudo-random) then no computer could possibly produce those results (the output of a computer is always deterministic, not random). However, many physicists now believe that quantum behaviour is actually fundamentally deterministic after all in processes which are hidden from our analytic methods (we can only see the apparently random results). Hence, to quote Einstein, "God does not play dice". As Schmidhuber says in his paper A Computer Scientist's View of Life, the Universe, and Everything: "Is there true randomness in our universe, in addition to the simple physical laws? True randomness essentially means that there is no short algorithm computing 'the precise collapse of the wave function', and what is perceived as noise by today's physicists. Our fundamental inability to perceive our universe's state does not imply its true randomness, though. For instance, there may be a very short algorithm computing the positions of electrons lightyears apart in a way that seems like noise to us but actually is highly regular." So there might very well not be true (uncomputable) randomness in the universe - there might just be the appearance of randomness.

In his book New Theories of Everything, John Barrow suggests that if we have a law of physics which depends on some physical property being differentiated (e.g., the wave equation) then this could be non-computable if the curve contained a "kink" or "crease". This would be the case if spacetime was actually discrete (i.e., the universe being a digital computer) rather than smooth and continuous:

The absolute value function is continuous, but fails to be differentiable at x = 0 as there is a "kink" in the curve at x = 0 (i.e., the curve is not smooth)
(Diagram from the Wikipedia entry for Derivative).
Hence, when we consider the derivative of the curve (the "rate of change" of the curve) we find it is not continuous: it is disjoint at the point of the "kink" at x = 0. The derivative (the "rate of change" of the top curve) is -1 for negative values of x, and is +1 for positive values of x, but the derivative is not defined (i.e., non-computable) at x = 0.

John Barrow then goes on to argue that this implies that some aspects of the universe are non-computable. However, I feel it just shows how inadequate our formulae for the laws of nature would be if the universe really was discrete. The Newtonian calculus provided mathematical methods for dealing with the infinitely small, and modelled the physical world as a continuum. As a result, our equations based on calculus containing derivatives (such as the wave equation) have been developed on the basis that spacetime is smooth and continuous, not discrete. If spacetime is discrete then we would need to develop new, more accurate analytical formulae rather than these approximations which are only capable of describing a continuous spacetime (just like Newton's approximate theory of gravitation was replaced by Einstein's more accurate theory of general relativity). As the Wikipedia entry on Digital Physics notes: "Proponents of digital physics, however, reject the very notion of the continuum, and claim that the existing continuous theories are just approximations of a true discrete theory".

To sum-up, we certainly cannot use our current (possibly approximate) laws to infer that the universe is continuous and not discrete, as John Barrow suggests.

Comments

Comments are now closed on this page.

Interesting article. So the idea is that the current state of the universe is the output of all the previous operations, and the input for the next operation? what a cool idea. I wonder...if and when they prove this to be true and go about trying to hack the universe...I wonder what they will find? I bet the universe is running on Linux. - Bob, 9th November 2008
Hi Bob, yes, I'm still working on this article. It's definitely quite a fashionable approach at the moment. You think the universe would be open source? Maybe that would explain why we can understand it! - Andrew Thomas, 10th November 2008
The Earth is a computer, and the answer is 42. - Glen, 12th November 2008
Excellent article, a really good read. I don't know how many physicists believe that quantum processes are deterministic - Bell's theorem did a number on that. Also, I always thought that radioactive decay was one of the few examples of true randomness, but how do you test for randomness? Is there a RNG with an algorithm so complex and with such a large period that we could not tell it for otherwise? (Mersenne Twister?)

I think I just hurt my head.

And the answer is DEFINITELY 42. - Dave, 13th November 2008
Hi Dave and Glen, I'm glad you've found the answer already!

Dave, Bell's theorem is a test for quantum non-locality, not randomness - see the "Quantum Entanglement" page for more details. As far as testing for randomness, yes, you're right: we consider a sequence to be random if it cannot be compressed, cannot be produced by a simpler algorithm. If an algorithm cannot be compressed to something simpler, it is said to be "elegant". Gregory Chaitin has shown that we cannot prove an algorithm to be elegant if the program you are using to prove the elegance of the algorithm is simpler than the algorithm you are testing: "How can we be sure that we have the best theory? How can we tell whether a program is elegant? The answer, surprisingly enough, is that we can't!": http://arxiv.org/abs/math/0611740

So you're quite right: if the apparent quantum randomness is actually just produced by a really complex algorithm then it would be impossible to prove it was not random after all. (I hadn't heard of the Mersenne Twister - very interesting, thanks: http://en.wikipedia.org/wiki/Mersenne_Twister ).

However, if the answer really is 42 then that sounds like a very elegant solution. - Andrew Thomas, 13th November 2008
Very good article. A great read - I just had one question though. You stated:

"The output of HaltTest could not be both "Loop" and "Halt". In physical reality, an object cannot be two things. For example, an object cannot be both present and absent at the same time."

But isn't that pretty similar to the basis of quantum theory? Of course if the universe were a quantum computer... - Alec, 14th November 2008
Thanks Alec. Very interesting. As you suggest, if the universe really does behave like a computer then it behaves like a quantum computer. This is because the fundamentals of the universe are based on quantum mechanical foundations.

So the particles which compose the universe are in quantum superposition states (i.e., a mixture of both 0 and 1, or "in two places at the same time"). But, in quantum theory an object can only be "in two places at the same time" (i.e., a particle in a superposition state) UNTIL we try to detect the particle. And then we only find the particle in one precise position. We DON'T see superposition states in our physical reality. We don't see cats alive and dead at the same time. And when we observe a quantum qubit in quantum computing we only observe it to be 0 or 1 ("Eventually, however, observing the system would cause it to collapse into a single quantum state corresponding to a single answer" - http://www.qubithosting.com/qubit/ ). So even a quantum computer only gives a single output.

Things in our physical reality - when we observe them - are not in superposition states, they have definite values. So, yes, the output of HaltTest COULD be a mix of "Loop" and "Halt" if it was a particle in a quantum superposition state, but as soon as we observe it we find it has only one of those two values. The qubit is EITHER 1 or 0. The grandfather cannot be both alive and dead.

(I deliberately did not talk about quantum computers in the main article as they are basically just another form of computer: all the discussion of non-computability applies equally to quantum computers as it does to conventional computers. As Gordon McCabe said: "Although quantum computers might be able to perform certain calculations faster than computers based upon the notion of a Turing machine, the collection of uncomputable functions for a quantum computer is the same as the collection of uncomputable functions for a Turing machine". http://arxiv.org/abs/physics/0511116 ) - Andrew Thomas, 15th November 2008
Hi Andrew, I enjoyed your website very much. After reading this article one thing confuses me a little bit. You stated: "Are there any uncomputable functions in physical reality? This is such an important question because if it could be shown that there were uncomputable functions in the way the universe works it would kill stone dead the idea that the universe behaves like a computer."
I donīt think so. An uncomputable function will result in a closed loop, but will not loop endlessly because of the finiteness of the universe. And stating "TRUE=FALSE" will not harm any physical computer or universe. (Otherwise our world would have dissolved in the very moment I wrote this comment?) - Donnerstilzchen, 19th November 2008
Hi Donnerstilzchen, thanks, that's some really interesting points.

Firstly, yes, I suppose there would be no such thing as an "infinite loop" in a finite universe. But I think if we did have a similar inverting loop then we would have things flashing on and off! For example, the grandfather might be flashing alive, then dead, then alive, then dead!

As for your second statement, just writing "TRUE=FALSE" doesn't actually prove anything about mathematics. The famous example of this is the statement "This statement is false". If the statement is true, then the statement is false. But if the statement is false, then its true. So we appear to have an inconsistent paradox (so that's the kind of thing you were suggesting). But the resolution to this paradox was provided by Alfred Tarski who said you are actually making the statement in a "meta-language", i.e., a language ABOUT mathematics, you are not making the statement in mathematics itself. So that is allowed and there is no paradox.

From Wikipedia: "It is legitimate for sentences in "languages" higher on the semantic hierarchy to refer to sentences lower in the "language" hierarchy, but not the other way around. This prevents a system from becoming self-referential." http://en.wikipedia.org/wiki/Liar_paradox#Alfred_Tarski

Now, if you could *prove* that TRUE=FALSE using mathematics, then we really would be in trouble. - Andrew Thomas, 19th November 2008
Thank you Andrew for pointing me to Alfred Tarski. Thinking about this, I came to the conclusion that there can be no self reference problems on the physical layer of reality. All the fuzz is on the interpretation layer. Next time I see a traffic light flashing I can imagine that this is a mechanism in the process of evaluating a deep question with a self contradiction in it... - Donnerstilzchen, 23rd November 2008
He he, quite. Thanks for your comments. - Andrew, 24th November 2008
Yes, we are in a computer. People have called this computer 'God'.

At one time, people thought there were many of these 'computers' fighting each other in the sky.

Then the one true computer started downloading messages to selected agents who searched for the one true computer.

Then the one true computer downloaded himself into the very matrix he created to straiten things out but people killed him, (he had the cheat code for 'god mode' but didn't want to use it to prove that he could come back from death.


http://oftheonetruevine.blogspot.com/ - Noah Hornberger, 24th July 2009
i have been saying this for years. the earth can be considered like a magnetic hard drive, fill it up too much, or dont defrag and it will crash and fail. its all about magnetism. we are in the final days of filling the earths 'disk', and something has to give soon. get ready for the great defrag of the late great planet earth......... - nerf, 25th September 2009
Nerf, I like that analogy. Maybe ideally we'd prefer a defragging, but a reformatting is more likely what we'll end up with. - Andrew Thomas, 25th September 2009
You state that a Turing Machine can compute anything which can be computed on any other computer. Can you prove that? - Robert Puttnam, 12th October 2009
Hi Robert. Yes, Paul Davies explains a nice proof in his book "The Mind Of God". Here it is: "Turing demonstrated that it was possible to construct a *universal* Turing Machine which is capable of simulating all other Turing Machines. The reason why such a universal machine can exist is simple. Any machine can be specified by giving a systematic procedure for its construction: washing machines, sewing machines, adding machines, Turing Machines. The fact that a Turing Machine is itself a machine to carry out a procedure is the key point. Hence, a universal Turing Machine can be instructed to first read off the specification of any given Turing Machine, then reconstruct its internal logic, and finally execute its function. Clearly, then, the possibility exists of a general-purpose machine capable of performing all mathematical tasks. One no longer needs an adding machine to add, a multiplying machine to multiply, and so on. A single machine could do it all." - Andrew Thomas, 12th October 2009
Hi Andrew,

Truly a nice piece outlining the current arguments which essentially comes down to asking if mathematics being a discovery or an invention and there by extension if it capable of capturing all of logic or merely being a subset of a larger truth. In as Godel has already made it quite evident as the latter being true then I would submit the question of whether or not the universe is a computer cannot by itself serve as proof if it is a structure mandated by reason or not. I have long believed it was this realization that had Bertrand Russell abandon mathematics as his full time concern in favour of philosophy, since he felt only through it could he explore beyond the limitations of mathematics in relation to reason.

Best,

Phil
- Phil Warnell, 26th November 2009
Hi Phil, thanks for that. Yes, John Barrow has used the result of Godel and Gregory Chaitin to suggest that even if we think we have found a theory of everything to describe the universe, we could never be certain that it was the most elegant (i.e., simplest) description. Basicallly, if the only analytical tools you have at hand are the tools you can find WITHIN the universe then you're always going to have a problem describing the ENTIRE universe (as the complexity of the entire universe will be greater than that of your tools). Your tools will not be up to the job. - Andrew Thomas, 26th November 2009