Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

If the Universe Is a Program


Oct02: Programming Paradigms

Michael is editor-at-large for DDJ. He can be contacted at [email protected].


This month's column will not, I'm sorry to say, answer any of these questions. It will, however, suggest what may be the most likely place to look for the answers. (That's the best I can do under the pressure of monthly deadlines.) I won't keep you in suspense: The most likely place to look for the answers to these questions, I believe, is in the writings of Edward Fredkin, who 1) unlike almost every physicist on the planet truly believes that the universe is a computer program, 2) has devoted 40 years of his life to examining that hypothesis and the questions that it provokes, and 3) is a very bright guy. This month I'll point you to Fredkin's writings on what he calls "Digital Mechanics."

My short list of questions didn't include one that would occur to many a Dr. Dobb's Journal reader: If the universe is a program, in what programming language is it written? The unmatched success of quantum physics in making predictions that agree with the most mundane and the most extreme observations down to the last measurable decimal point would argue that the programming language of the universe would have to be a quantum one. (Ed Fredkin would probably disagree with that.) Quite recently it would have been impossible to point to an example of a real quantum programming language, but that is no longer the case. This month I'll point you to QCL, a bona fide quantum programming language, which will undoubtedly become much more useful when there is a bona fide quantum computer on which to run it, and I'll point out a recent development that makes that possibility more plausible.

Fredkin's Folly?

For the past two months I have devoted a significant part of this column to a (more superficial than I'd like) exploration of the ideas in Stephen Wolfram's massive and challenging A New Kind of Science. Several readers wrote to take issue either with Wolfram's ideas or with my presentation of them. One idea that generated some heat was that of computational universality. Realizing that the problem was probably in my inadequate understanding of the point that Wolfram was trying to make about universality, I went to one of his sources—Ed Fredkin. The more I read of Fredkin's work, the more I became convinced that all the really interesting ideas in A New Kind of Science are really Fredkin's.

Ed Fredkin has been maintaining since 1960 and earlier that space, time, and all other quantities of physics are discrete; that the fundamental processes of physics are similar to the processes that go on inside a digital computer; and that the entire story of the universe, past and present, can be captured in a few integers, at least one of them probably rather large. He is fully aware that this view, at least on the surface, is incompatible with both quantum physics and relativity theory. He knows enough physics both to appreciate the apparent incompatibility and to attempt to resolve it. Fredkin is, however, not a physicist but a computer scientist. If he weren't, it is less likely that the idea of the universe as a computer would have struck him so forcefully, nor would he have been equipped to explore it so fanatically. This does not diminish the importance of the ideas.

Fredkin reports that revered MIT physicist Phillip Morrison once said of him, "Ed Fredkin is a computer person, therefore he believes that the universe is actually a computer. If Fredkin was a cheese merchant he might be telling you that the universe is made up out of cheese." That's just asinine, and the precise specification of "computer person" as opposed to "computer scientist" and "cheese merchant" as opposed to some more scholarly kind of cheesy profession sounds suspiciously like a dig at Fredkin for having started a successful computer company. But while the universe couldn't be made of cheese, it could be a computer; that's not the really radical part. Fredkin's radicalism comes in claiming that it's a digital computer. (I said "computer program" earlier and "computer" here. The precise assertion, I guess, is that the universe is a computation, an idea that takes into itself both the computer and the program.)

Fredkin has always had trouble getting respect for his ideas. Legendary iconoclast and physicist Richard Feynman brainstormed with him repeatedly and was happy to borrow some of Fredkin's ideas (although Wolfram's wholesale appropriation of Fredkin's ideas dwarfs Feynman's carelessness over credit), but Feynman always distanced himself from Fredkin's reputation as a crank, wanting everyone to know that he didn't take these crazy ideas seriously. When I mentioned in this space that Fredkin had headed MIT's Project MAC, a former MIT professor wrote to tell me in no uncertain terms that Fredkin had never run the project.

Well, he did, from 1971 to 1974. An innocent mistake on the ex-MIT professor's part, I'm sure, but there may have been a bit of anti-Fredkin bias showing in the vehemence of his assertion. Fredkin raises people's hackles. I've read his essay on the soul and the draft of his book on digital mechanics and he seems fairly modest for a non-physicist trying to turn physics on its head. At least compared to Stephen Wolfram. It must be his unwillingness to wear a tie.

Digital Mechanics

I don't know if Fredkin is right, but I don't think that he is a crank. Anyone who summariliy dismisses Fredkin's views will also have to dismiss Stephen Wolfram's, because they are in fundamental respects the same. (Many scientists are dismissing Wolfram's views expressed in A New Kind of Science, but not everyone.) You can decide for yourself what you think of Fredkin's ideas by reading his writings at http://www.digitalphilosophy.org/. I'll go over some of his points here and see if I can find hints to what might be Fredkin's answers to the questions I raised at the beginning of this column.

Fredkin believes that there is an actual program underlying all physics. He thinks that the real scientific challenge is not just to find the simplifying constraint rules that have traditionally made up the bulk of science, but to determine the actual programs underlying the processes of nature. To determine how this instant generates the next. We've actually done it in biology, he points out with amazement. We know the mechanism of genetics. We know, or are learning, how the parents generate the specific characteristics of the child, and in biology there is no hesitation in referring to the "program" or to the "language" underlying the process. But we haven't begun to do the same thing in physics. Like Wolfram, Fredkin believes that computation lies at the bottom of everything, and that simple (but universal) cellular automata are the cleanest and most useful model for the computational substrate of physics.

About computational universality: My use of that phrase and the term "universal computer" in past columns caused some confusion among readers. As Wolfram and Fredkin use the term it doesn't require infinite memory. Fredkin defines "universal computer" or "universal machine" to include universal cellular automata and other kinds of general purpose computers "that have large but finite memories [including] any commercial computer. A universal machine [is one that] can exactly mimic the behavior of any other finite computer, provided its memory is just a very little bit larger than the target machine."

Fredkin follows out the consequences of his beliefs and unflinchingly meets the formidable problems that they present. And they are formidable: His vision only makes sense if nature is discrete and deterministic and has an absolute spatial and temporal frame of reference. Doesn't this put him in conflict with the known data of quantum and relativistic physics? Didn't the Michelson-Morley experiment demolish the possibility of an absolute frame of reference? Isn't quantum uncertainty solidly established? Fredkin's answer is that his views are not in conflict with the data of quantum and relativistic physics; only with the accepted interpretations of those data. He doesn't challenge the data, he just says that four generations of physicists have interpreted the data wrong.

If Fredkin is right about "finite nature," his fundamental assumption that everything is discrete and finite, then his Digital Mechanics could be not just an approximate model for physics, but an exact model. The model. He has set quite a program for himself. He has to explain, within his Digital Mechanics or DM perspective: All the basic conservation laws, all the data of relativity and quantum mechanics, the uncertainty principle, wave-like interference in particles, how to measure absolute time and establish a fixed time/space reference system, the Big Bang, inertia, spin, charge, energy, Bell's inequality—to pick a few challenges more or less at random. But he has been wrestling with these challenges for decades and thinks that he has made some progress. Or rather that he and his students and his few interested colleagues, including Stephen Wolfram, have made some progress. For all the hubris of his assault on establishment physics, Fredkin does usually say "we," a word that Wolfram apparently never learned.

The challenge is great, but the appeal of Fredkin's approach to physics is great. I understand what he means by his desire to eliminate the "magic" in present-day physics. Why are there the particular particles and constants that we observe? To this and many other questions, modern physics repeats Newton's infamous "I make no hypotheses." Fredkin sides with Descartes: we should be able to understand everything. And he's working on it.

The Questions

So how about those questions with which I started this column? What does Fredkin say about them?

Assuming that the universe is a computation, is it efficient? Totally. According to Fredkin, the universe is computing itself as fast as it can; there is no way to do it any faster. Wolfram talks about this, too: computational irreducibility. If either Fredkin or Wolfram has proved that the universe as computation must be computationally irreducible, I missed it, but they do both claim it. So there's your answer. Does it terminate?

Fredkin says, "When thinking about theoretical models of computation, it's best to leave out the idea of a halt instruction. There is a quaint and antique concept, which is a part of the literature on Turing Machines from half a century ago, that all computers halt when they get to the answer. Since a computer is a finite machine, eventually it gets back into some prior state. From that point on it is in a cycle."

So it doesn't halt, but is that the same as saying it doesn't terminate? Fredkin apparently believes that the universal computation had a beginning and that it is reversible. I'm not sure that that doesn't entail that it has an end. So: Halt quashed, but end entailed? I dunno.

Is It Buggy?

A bug implies a purpose. On one hand, Fredkin does impute purpose to the universal computation; in fact, he seems to go beyond that and impute purpose to all computations. But it's an intrinsic purpose he has in mind: The computation's purpose is whatever it's computing. Implying no bugs, I'd say. On the other hand, he does talk about the programmer... okay, if the universe is a program, who wrote it?

Fredkin offers one answer, although I'm not sure how serious he is about it: Our universe is a reversible universal cellular automaton (RUCA) created by a thing/in a place that he calls Other. Other is outside our space and time and operates under different laws; it might have no need for conservation laws, for example. But that doesn't mean that we can't figure out some things about this Other. Why is Other running the program that is our universe? To get the result of the computation, presumably. Fredkin himself is outside physics here, but at least he admits it. Although I've seen references to his views that associate them with Intelligent Design believers, Fredkin is not one of them. I'll leave it to you to assess Fredkin's theology. He may just be having fun.

Speaking of fun, the rest of this month's column will follow the quantum computing thread that I've been gathering or unwinding or spinning or whatever the appropriate metaphor is. When I finally wrap it up, I'm going to have a ball of quantum yarn the size of Stephen Wolfram's ego.

Quantum Uncertainty

The (actually very good) British science weekly New Scientist baldly contradicted itself over the course of about three weeks this summer. The cover of the 29 June issue shouted "God Doesn't Play Dice," which Albert Einstein would have been glad to read. Einstein was never comfortable with the fundamental uncertainty built into the quantum view of the universe. "God doesn't play dice with the universe" was his pithy anthropomorphic encapsulation of his discomfort with quantum uncertainty. But in the 20 July issue of New Scientist, a shorter article asserted that "God really does play dice with the universe," and that, at least according to one group of researchers, the last plausible alternative to quantum uncertainty, the guide-wave theory espoused by de Broglie and Bohm, had been experimentally refuted. Or maybe not. One cited physicist pointed out that the guide-wave theory was constructed to make all the same predictions as quantum theory, meaning that it would be impossible to refute one in favor of the other on experimental grounds. Both articles (pro-dice and anti-dice) acknowledged dissenting views, leaving the whole matter decidedly... uncertain.

QCL

A big chunk of the uncertainty about the feasibility of building useful quantum computers has recently been removed. Scientists at the University of Wisconsin have come up with a scalable quantum dot device; that is, a semiconductor-based device that can trap and hold individual electrons and line them up, and the device can be scaled up to a size adequate for building an actual quantum computer. Trapping the electrons and lining them up creates a quantum bit, or qubit, and the inability to assemble more than a half-dozen or so qubits at a time has been the chief holdup in build a working quantum computer. (Earlier this year it was hailed as a major breakthrough when enough qubits were assembled to factor 15 into 3 and 5, a task that I could do with paper and pencil in under a minute.) The fact that a qubit can exist in a superposition of states leads to the appealing virtue of quantum parallelism—by which quantum computers ought to be able to crack uncrackable codes and otherwise shake things up.

So this is an interesting development. But quantum computers need quantum computer languages....

Enter Bernhard Omer. He has written a high-level, architecture-independent programming language for quantum computers. I probably don't need to tell you that this highly exotic quantum programming language tastes like chicken—er, has a C-like syntax.

It's called QCL, short for "Quantum Computation Language," and it is designed to work with any qubit-based quantum computer architecture, Omer says, by which he does not mean any existing quantum computer architecture: that would be too easy. QCL is built around the concept of quantum registers, which are sequences of qubits. All operations on the machine state take quantum registers as arguments.

The QCL package (http://tph.tuwien.ac.at/%7Eoemer/qcl.html) comes with two working examples of well-known quantum algorithms—Schor's fast quantum factorization algorithm and Grover's database search algorithm, both described in detail with QCL source code.

Errata

I suppose a 42-orders-of-magnitude error is too much uncertainty to let pass unacknowledged. As Joseph North points out, in my June column I wrote "kTlog2, which is about 2x1021 joules" and should have written "2x10-21 joules" instead. Mea culpa. This month's greatest error may be discussing discrete physics and cellular automata and leaving out Konrade Zuse, who, as near as I can tell, thought of everything first. Maybe I can rectify that in the coming months.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.