Sean watches a panel discussion on whether the universe is a computer, looks up the definition of a computer, and decides that instead the universe is a calculation. If thinking about the universe as a computer is designed to make computer scientists feel important, thinking about the universe as a calculation seems designed to make theoretical physicists feel important 🙂 But what I find interesting is that Sean points to a question asked by Tony Leggett: “What kind of process does not count as a computation?”
Now first of all, let me preface this by saying that the word “computation” has a much more specific meaning for me that it probably does for most physicists. That is I consider “computer” to be equivalent to a device which computes in a fashion easily mapped to that of a Turing machine. Thus for me “computer” has a much specific meaning that what I think Sean or most of the commenters on his post think of as a computer.
So, given this definition of a computer, I think a computer scientist would probably immediately respond to Leggett’s question with a discussion of computable functions. There are certainly universes I can imagine which perform evolutions which are not computable functions. For example there might be a universe where data describing a Turing machine and an input to this Turing machine evolves in time to data describing whether this Turing machine halts (this is not a computable function.) Of course this evolution law is for a physics that will probably look very different from our universe, where all we seem to be able to build are Turing machine-like devices. Nonetheless, such laws of physics can certainly be written down.
But I also think there is another answer to Leggett which is often overlooked. This is the opposite end of the stick. In the previous paragraph I described a universe where the evolution of the universe is more powerful than a Turing machine. So…certainly another answer to this question is that we can imagine universes where the power of the physical evolution is not enough to perform universal computation. Indeed we can also easily write down physics for just such universes, as for example, in cellular automata which are not universal.
Further, and I think more interestingly, is the possibility that our universe is not a computer because its evolution is not predictable or controllable enough. In other words, it might be possible that our universe does not allow for computation (classical or quantum) because the evolution is subject to too much noise or inability of systems to control each other. Indeed I would argue that most of our universe is exactly in that situation. The Diet Coke on my desk is not a computing device, as far as I can tell, because I do not have enough control over it. Could I turn it into a computing device? Perhaps. Okay, who am I kidding. I just drank all of the Diet Coke, so now I’d have to make a computing device from the plastic. Possible? Possibly. But right now I don’t think I have much of a right to call it a computer.
Now you might say: but I have a computer on my desk, so certainly I have experimental evidence that our universe allows for computation. But I would argue that your computer only proves that computers can exist for a timespan of a few decades. And indeed, your hard drive isn’t really that good of a storage device, and a few centuries from now, the software on such a drive, if you just let it sit there, will probably no longer function. Very few are the physical processes which allow digital computation. On the other hand, we do have some theoretical reasons combined with experimental evidence to believe that our universe does allow for computation. This comes from our understanding of the laws of physics combined with results in fault-tolerant computation. But if pushed I would probably say that we haven’t put this full theory together, i.e. deriving fault-tolerant quantum computation from the first principles of our physical laws (of which we don’t really have a fundamental theory at all, so right now this exercise is fundamentally flawed.)
So, at this point you might be thinking: but aren’t you confounding what the universe can do (i.e. whether we can build a computer) with what the universe is? If I say, for example, that our universe does not allow for universal robust computation, why can’t you just say “but the laws of physics can be thought of as doing a computation.” But this is exactly the point: if I tell you that the universe is a computer, then if computation is not possible in our universe, then this computation that the universe is doing is not experimentally accessible. And if its not experimentally accessible, it ain’t science, and so can be used at best as metaphysics (which is not to say that such a metaphysics might not allow you to think differently and solve problems from this perspective. But that is another story.)
So I think the question “Is the universe a computer?” really does have some content beyond just thinking about uncomputable laws of evolution. The question asks whether the evolution of our universe is, at a fundamental level, one which is predictable and controllable enough to warrant the moniker of computer. And this is a wonderful question, because, I think we have some ideas about the answer to this question, but as we learn more about physics, we will learn more about the ultimate answer to this question.
O brave new quantum world!
Is it really certainly true that we can write down laws of physics that would (essentially) solve the halting problem? What would they look like? Perhaps I am unsure what counts as a “law of physics.”
On the other end of the stick, I suspect one could convincingly argue that our universe is unable to do a calculation that would take longer that the Poincare recurrence time for a universe with a 10^120-dimensional Hilbert space. But does that really mean it’s “not a computer”?
My “law of physics” is a very very very wide definition! Suppose you have a one dimensional cellular automata world where each cell is either 0 or 1. Define the update rule as follows. Let l denote the state of the cells to the left and r the state of the cells to the right. Then update a cell to 0 in the next time step if suitably interpreted a Turing machine described by l halts on input r. Update the cell to 1 in the next time step if suitable interpreted a Turing machine describe by l does not halt on input r. You will probably also have to pad these rules for l’s and r’s which don’t define valid Turing machines or valid inputs.
Of course this is an absolutely crazy law of physics! And getting this to mesh with what we currently now about the world seems incredibly difficult. Interestingly, you can trade the extreme nonlocality of this model, for a model where the regions are real numbers, so the model becomes local and continuous, but at the expense of replacing space with precision.
To the second comment I guess I would say that there are two ways to interpret “the universe is a computer.” One is that the entire universe is a computer. The other is that everywhere we look we see parts of the universe which appear to be a computer. I was thinking about the second problem, I guess. Thats what I get for having not taken a cosmology course since 1998.
“Just to orient myself, suppose we have a universe consisting only of quarks and gluons interacting according to the rules of QCD. This is, in this hypothetical example, the complete description of the universe. Is that universe a computer?”
I love it. This is a particle physicists version of starting with a simple universe 🙂 ! I don’t know if I can give a sensible answer to that. John Preskill?
I think you’ve definitely expanded my view of possible laws of physics. Usually I think of some differential (or difference) equation, or something equally explicit. Now I want to consider a cellular automaton rule that says “the cell turns from 1 to 0 if 1 is the loneliest number.” The possibilities boggle.
I think there are lots of physical theories which have universes which aren’t computers by their lack of universality. For example, a theory which has one dimensional fermions interacting quadratically isn’t computationally universal, so that the universe described by that theory I wouldn’t consider a computer. If you allow me classical physical theories, then E&M without matter isnt’ computationally universal.
As for cases where noise or imprecise control is the reason the universe isn’t a computer, I don’t know of a simple theory which gives rise to such a universe. There are certainly ways to get this. One way might be to build a model with a severe detector inefficiency problem which effectively gives you a very noisy evolution.
That universe would stay in 0 because 1 is the loneliest number, no?
I think we are perfectly allowed to say, given what we know now, the universe does allow computation. But I think any such statement would need to be subject to refinement as a better understanding of physics is uncovered.
For example, if we had discovered eletromagnetism with no matter first, we would have concluded that computation was not possible (and the existence of a computer would have been called the “computing paradox”?) But then discovering interactions between matter and electric fields would have changed our mind.
Besides the “thinking about uncomputable laws of evolution”, which ties in with the Church-Turing thesis, one can also think about laws of evolution that beat the time/space complexity limits set by (quantum) computers, which makes a link with the strong Church-Turing thesis after Deutsch.
While I am not holding my breath for laws of physics doing uncomputable things, I do not consider it impossible that we will discover physical phenomena that beat the power of BQP, the same way that quantum mechanics beat BPP. (Oh yeah, we did not prove that one, but it’s gotta be right.)
Just to orient myself, suppose we have a universe consisting only of quarks and gluons interacting according to the rules of QCD. This is, in this hypothetical example, the complete description of the universe. Is that universe a computer?
I’m just trying to be concrete, feel free to replace QCD by any theory we know to actually describe a physical system. Is the universe described by that theory a computer? is it not a computer? can we know the difference by performing any finite number of experiments?
Excellent Dave, thanks. I really like your definition emphasizing universality, especially since it is not meaningless, always a good thing :-)…but I am still confused about another thing: is this necessarily a statement about the “ultimate” theory of the universe, in other words do we need to know absolutely everything about the fundamental laws before we decide if our universe is a computer, or can we know the answer using some suitably accurate approximation?
Thanks Dave.
Hi Dave,
When you say a model (such as free fermions) doesn’t support universal computation, what is your definition of how I am allowed to encode input into the system, and decode output from the system? Even on the computer I’m using to type this, I have to encode problems in a certain way (say, as C code) to get an answer, but if I allow too much freedom to encode problems, then that’s no good there either.
Isn’t this the same question as arose in the recent claim of a certain Wolfram CA being universal or not?
Matt
Suppose we assert: “The less capable a system is of calculation, the easier it is to simulate.” What I’m uncertain of is whether this assertion is best understood as a physical law, a definition, a theorem, or an engineering principle. Best guess: all four. 🙂
Hi Dave & Co.,
This has been said before by men and women much smarter than I, but it bears repeating…
Discussion of the Universe as a Computer is predictable by historical standards and, perhaps, unlikely to yield much in the way of insight. Society has a tendency to liken the Universe to the most complex technology of the age. Hence Deists believed in the “Watchmaker” God as precisely engineered timepieces were among the most complex technological achievements at the time.
This is not to say that such discourse is without merit, but it is to suggest that it’s not a terribly concept.
last line should read
…it’s not a terribly new concept.
otherwise the post is even sillier.
Michael J. Biercuk said:
“Hence Deists believed in the “Watchmaker” G-d as precisely engineered timepieces were among the most complex technological achievements at the time. This is not to say that such discourse is without merit, but it is to suggest that it’s not a terribly [new] concept.”
As I recall, the phrase “clockwork universe” was coined by Isaac Newton. To me, that’s strong circumstantial evidence that “such discourse” is far from without merit!