In physics and cosmology, digital physics is a collection of theoretical perspectives based on the premise that the universe is, at heart, describable by information, and is therefore computable. Therefore, the universe can be conceived as either the output of a computer program or as a vast, digital computation device (or, at least, mathematically isomorphic to such a device).

Digital physics is grounded in one or more of the following hypotheses; listed in order of increasing strength. The universe, or reality:

• is essentially informational (although not every informational ontology needs to be digital);
• is essentially computable;
• can be described digitally;
• is in essence digital;
• is itself a computer;
• is the output of a simulated reality exercise.

History[link]

Every computer must be compatible with the principles of information theory, statistical thermodynamics, and quantum mechanics. A fundamental link among these fields was proposed by Edwin Jaynes in two seminal 1957 papers.^[1] Moreover, Jaynes elaborated an interpretation of probability theory as generalized Aristotelian logic, a view very convenient for linking fundamental physics with digital computers, because these are designed to implement the operations of classical logic and, equivalently, of Boolean algebra.^[2]

The hypothesis that the universe is a digital computer was pioneered by Konrad Zuse in his book Rechnender Raum (translated into English as Calculating Space). The term digital physics was first employed by Edward Fredkin, who later came to prefer the term digital philosophy.^[3] Others who have modeled the universe as a giant computer include Stephen Wolfram,^[4] Juergen Schmidhuber,^[5] and Nobel laureate Gerard 't Hooft.^[6] These authors hold that the apparently probabilistic nature of quantum physics is not necessarily incompatible with the notion of computability. Quantum versions of digital physics have recently been proposed by Seth Lloyd,^[7] David Deutsch, and Paola Zizzi.^[8]

Related ideas include Carl Friedrich von Weizsäcker's binary theory of ur-alternatives, pancomputationalism, computational universe theory, John Archibald Wheeler's "It from bit", and Max Tegmark's ultimate ensemble.

Digital physics[link]

Overview[link]

Digital physics suggests that there exists, at least in principle, a program for a universal computer which computes the evolution of the universe. The computer could be, for example, a huge cellular automaton (Zuse 1967^[9]), or a universal Turing machine, as suggested by Schmidhuber (1997), who pointed out that there exists a very short program that can compute all possible computable universes in an asymptotically optimal way.

Some try to identify single physical particles with simple bits. For example, if one particle, such as an electron, is switching from one quantum state to another, it may be the same as if a bit is changed from one value (0, say) to the other (1). A single bit suffices to describe a single quantum switch of a given particle. As the universe appears to be composed of elementary particles whose behavior can be completely described by the quantum switches they undergo, that implies that the universe as a whole can be described by bits. Every state is information, and every change of state is a change in information (requiring the manipulation of one or more bits). Setting aside dark matter and dark energy, which are poorly understood at present, the known universe consists of about 10⁸⁰ protons and the same number of electrons. Hence, the universe could be simulated by a computer capable of storing and manipulating about 10⁹⁰ bits. If such a simulation is indeed the case, then hypercomputation would be impossible.

Loop quantum gravity could lend support to digital physics, in that it assumes space-time is quantized. Paola Zizzi has formulated a realization of this concept in what has come to be called "computational loop quantum gravity", or CLQG.^[10][11] Other theories that combine aspects of digital physics with loop quantum gravity are those of Marzuoli and Rasetti^[12][13] and Girelli and Livine.^[14]

Weizsäcker's ur-alternatives[link]

Physicist Carl Friedrich von Weizsäcker's theory of ur-alternatives (archetypal objects), first publicized in his book The Unity of Nature (1980),^[15] further developed through the 1990s,^[16][17] is a kind of digital physics as it axiomatically constructs quantum physics from the distinction between empirically observable, binary alternatives. Weizsäcker used his theory to derive the 3-dimensionality of space and to estimate the entropy of a proton falling into a black hole.

Pancomputationalism or the computational universe theory[link]

Pancomputationalism (also known as pan-computationalism, naturalist computationalism) is a view that the universe is a huge computational machine, or rather a network of computational processes which, following fundamental physical laws, computes (dynamically develops) its own next state from the current one.^[18]

A computational universe is proposed by Jürgen Schmidhuber in a paper based on Konrad Zuse's assumption (1967) that the history of the universe is computable. He pointed out that the simplest explanation of the universe would be a very simple Turing machine programmed to systematically execute all possible programs computing all possible histories for all types of computable physical laws. He also pointed out that there is an optimally efficient way of computing all computable universes based on Leonid Levin's universal search algorithm (1973). In 2000 he expanded this work by combining Ray Solomonoff's theory of inductive inference with the assumption that quickly computable universes are more likely than others. This work on digital physics also led to limit-computable generalizations of algorithmic information or Kolmogorov complexity and the concept of Super Omegas, which are limit-computable numbers that are even more random (in a certain sense) than Gregory Chaitin's number of wisdom Omega.

Wheeler's "it from bit"[link]

Following Jaynes and Weizsäcker, the physicist John Archibald Wheeler wrote the following:

[...] it is not unreasonable to imagine that information sits at the core of physics, just as it sits at the core of a computer. (John Archibald Wheeler 1998: 340)

It from bit. Otherwise put, every 'it'—every particle, every field of force, even the space-time continuum itself—derives its function, its meaning, its very existence entirely—even if in some contexts indirectly—from the apparatus-elicited answers to yes-or-no questions, binary choices, bits. 'It from bit' symbolizes the idea that every item of the physical world has at bottom—a very deep bottom, in most instances—an immaterial source and explanation; that which we call reality arises in the last analysis from the posing of yes–no questions and the registering of equipment-evoked responses; in short, that all things physical are information-theoretic in origin and that this is a participatory universe. (John Archibald Wheeler 1990: 5)

David Chalmers of the Australian National University summarised Wheeler's views as follows:

Wheeler (1990) has suggested that information is fundamental to the physics of the universe. According to this 'it from bit' doctrine, the laws of physics can be cast in terms of information, postulating different states that give rise to different effects without actually saying what those states are. It is only their position in an information space that counts. If so, then information is a natural candidate to also play a role in a fundamental theory of consciousness. We are led to a conception of the world on which information is truly fundamental, and on which it has two basic aspects, corresponding to the physical and the phenomenal features of the world.^[19]

Chris Langan also builds upon Wheeler's views in his epistemological metatheory:

The Future of Reality Theory According to John Wheeler: In 1979, the celebrated physicist John Wheeler, having coined the phrase “black hole”, put it to good philosophical use in the title of an exploratory paper, Beyond the Black Hole, in which he describes the universe as a self-excited circuit. The paper includes an illustration in which one side of an uppercase U, ostensibly standing for Universe, is endowed with a large and rather intelligent-looking eye intently regarding the other side, which it ostensibly acquires through observation as sensory information. By dint of placement, the eye stands for the sensory or cognitive aspect of reality, perhaps even a human spectator within the universe, while the eye’s perceptual target represents the informational aspect of reality. By virtue of these complementary aspects, it seems that the universe can in some sense, but not necessarily that of common usage, be described as “conscious” and “introspective”…perhaps even “infocognitive”.^[20]

The first formal presentation of the idea that information might be the fundamental quantity at the core of physics seems to be due to Frederick W. Kantor (a physicist from Columbia University). Kantor's book Information Mechanics (Wiley-Interscience, 1977) developed this idea in detail, but without mathematical rigor.

The toughest nut to crack in Wheeler's research program of a digital dissolution of physical being in a unified physics, Wheeler himself says, is time. In a 1986 eulogy to the mathematician, Hermann Weyl, he proclaimed: "Time, among all concepts in the world of physics, puts up the greatest resistance to being dethroned from ideal continuum to the world of the discrete, of information, of bits. ... Of all obstacles to a thoroughly penetrating account of existence, none looms up more dismayingly than 'time.' Explain time? Not without explaining existence. Explain existence? Not without explaining time. To uncover the deep and hidden connection between time and existence ... is a task for the future."^[21] The Australian phenomenologist, Michael Eldred, comments:

The antinomy of the continuum, time, in connection with the question of being ... is said by Wheeler to be a cause for dismay which challenges future quantum physics, fired as it is by a will to power over moving reality, to "achieve four victories" (ibid.)... And so we return to the challenge to "[u]nderstand the quantum as based on an utterly simple and—when we see it—completely obvious idea" (ibid.) from which the continuum of time could be derived. Only thus could the will to mathematically calculable power over the dynamics, i.e. the movement in time, of beings as a whole be satisfied.^[22][23]

Digital vs. informational physics[link]

Not every informational approach to physics (or ontology) is necessarily digital. According to Luciano Floridi,^[24] "informational structural realism" is a variant of structural realism that supports an ontological commitment to a world consisting of the totality of informational objects dynamically interacting with each other. Such informational objects are to be understood as constraining affordances.

Digital ontology and pancomputationalism are also independent positions. In particular, John Wheeler advocated the former but was silent about the latter; see the quote in the preceding section.

On the other hand, pancomputationalists like Lloyd (2006), who models the universe as a quantum computer, can still maintain an analogue or hybrid ontology; and informational ontologists like Sayre and Floridi embrace neither a digital ontology nor a pancomputationalist position.^[25]

Computational foundations[link]

Turing machines[link]

Theoretical computer science is founded on the Turing machine, an imaginary computing machine first described by Alan Turing in 1936. While mechanically simple, the Church-Turing thesis implies that a Turing machine can solve any "reasonable" problem. (In theoretical computer science, a problem is considered "solvable" if it can be solved in principle, namely in finite time, which is not necessarily a finite time that is of any value to humans.) A Turing machine therefore sets the practical "upper bound" on computational power, apart from the possibilities afforded by hypothetical hypercomputers.

Wolfram's principle of computational equivalence powerfully motivates the digital approach. This principle, if correct, means that everything can be computed by one essentially simple machine, the realization of a cellular automaton. This is one way of fulfilling a traditional goal of physics: finding simple laws and mechanisms for all of nature.

Digital physics is falsifiable in that a less powerful class of computers cannot simulate a more powerful class. Therefore, if our universe is a gigantic simulation, that simulation is being run on a computer at least as powerful as a Turing machine. If humans succeed in building a hypercomputer, then a Turing machine cannot have the power required to simulate the universe.

The Church–Turing (Deutsch) thesis[link]

The classic Church–Turing thesis claims that any computer as powerful as a Turing machine can, in principle, calculate anything that a human can calculate, given enough time. A stronger version, not attributable to Church or Turing,^[26] claims that a universal Turing machine can compute anything any other Turing machine can compute - that it is a generalizable Turing machine. But the limits of practical computation are set by physics, not by theoretical computer science:

"Turing did not show that his machines can solve any problem that can be solved 'by instructions, explicitly stated rules, or procedures', nor did he prove that the universal Turing machine 'can compute any function that any computer, with any architecture, can compute'. He proved that his universal machine can compute any function that any Turing machine can compute; and he put forward, and advanced philosophical arguments in support of, the thesis here called Turing's thesis. But a thesis concerning the extent of effective methods—which is to say, concerning the extent of procedures of a certain sort that a human being unaided by machinery is capable of carrying out—carries no implication concerning the extent of the procedures that machines are capable of carrying out, even machines acting in accordance with 'explicitly stated rules.' For among a machine's repertoire of atomic operations there may be those that no human being unaided by machinery can perform." ^[27]

On the other hand, if two further conjectures are made, along the lines that:

• hypercomputation always involves actual infinities;
• there are no actual infinities in physics,

the resulting compound principle does bring practical computation within Turing's limits.

As David Deutsch puts it:

"I can now state the physical version of the Church-Turing principle: 'Every finitely realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means.' This formulation is both better defined and more physical than Turing's own way of expressing it."^[28] (Emphasis added)

This compound conjecture is sometimes called the "strong Church-Turing thesis" or the Church–Turing–Deutsch principle.

Criticism[link]

The critics of digital physics—including physicists^{[citation needed]} who work in quantum mechanics—object to it on several grounds.

Physical symmetries are continuous[link]

One objection is that extant models of digital physics are incompatible^{[citation needed]} with the existence of several continuous characters of physical symmetries, e.g., rotational symmetry, translational symmetry, Lorentz symmetry, and electroweak symmetry, all central to current physical theory.

Proponents of digital physics claim that such continuous symmetries are only convenient (and very good) approximations of a discrete reality. For example, the reasoning leading to systems of natural units and the conclusion that the Planck length is a minimum meaningful unit of distance suggests that at some level space itself is quantized.^[29]

Locality[link]

Some argue^{[citation needed]} that extant models of digital physics violate various postulates of quantum physics. For example, if these models are not grounded in Hilbert spaces and probabilities, they belong to the class of theories with local hidden variables that some deem ruled out experimentally using Bell's theorem. This criticism has two possible answers. First, any notion of locality in the digital model does not necessarily have to correspond to locality formulated in the usual way in the emergent spacetime. A concrete example of this case was recently given by Lee Smolin.^[30] Another possibility is a well-known loophole in Bell's theorem known as superdeterminism (sometimes referred to as predeterminism).^[31] In a completely deterministic model, the experimenter's decision to measure certain components of the spins is predetermined. Thus, the assumption that the experimenter could have decided to measure different components of the spins than he actually did is, strictly speaking, not true.

Physical theory requires the continuum[link]

It has been argued^{[weasel words]} that digital physics, grounded in the theory of finite state machines and hence discrete mathematics, cannot do justice to a physical theory whose mathematics requires the real numbers, which is the case for all physical theories having any credibility.

But computers can manipulate and solve formulas describing real numbers using symbolic computation, thus avoiding the need to approximate real numbers by using an infinite number of digits.

Before symbolic computation, a number—in particular a real number, one with an infinite number of digits—was said to be computable if a Turing machine will continue to spit out digits endlessly. In other words, there is no "last digit". But this sits uncomfortably with any proposal that the universe is the output of a virtual-reality exercise carried out in real time (or any plausible kind of time). Known physical laws (including quantum mechanics and its continuous spectra) are very much infused with real numbers and the mathematics of the continuum.

"So ordinary computational descriptions do not have a cardinality of states and state space trajectories that is sufficient for them to map onto ordinary mathematical descriptions of natural systems. Thus, from the point of view of strict mathematical description, the thesis that everything is a computing system in this second sense cannot be supported".^[32]

For his part, David Deutsch generally takes a "multiverse" view to the question of continuous vs. discrete. In short, he thinks that “within each universe all observable quantities are discrete, but the multiverse as a whole is a continuum. When the equations of quantum theory describe a continuous but not-directly-observable transition between two values of a discrete quantity, what they are telling us is that the transition does not take place entirely within one universe. So perhaps the price of continuous motion is not an infinity of consecutive actions, but an infinity of concurrent actions taking place across the multiverse.” January, 2001 The Discrete and the Continuous, an abridged version of which appeared in The Times Higher Education Supplement.

See also[link]

References[link]

Further reading[link]

• Paul Davies, 1992. The Mind of God: The Scientific Basis for a Rational World. New York: Simon & Schuster.
• David Deutsch, 1997. The Fabric of Reality. New York: Allan Lane.
• Michael Eldred, 2009, The Digital Cast of Being: Metaphysics, Mathematics, Cartesianism, Cybernetics, Capitalism, Communication ontos, Frankfurt 2009, 137 pp. ISBN 978-3-86838-045-3
• Edward Fredkin, 1990. "Digital Mechanics," Physica D: 254-70.
• Seth Lloyd, Ultimate physical limits to computation, Nature, volume 406, pages 1047–1054
• Carl Friedrich von Weizsäcker, 1980. The Unity of Nature. New York: Farrar Straus & Giroux.
• John Archibald Wheeler, 1990. "Information, physics, quantum: The search for links" in W. Zurek (ed.) Complexity, Entropy, and the Physics of Information. Addison-Wesley.
• John Archibald Wheeler and Kenneth Ford, 1998. Geons, black holes and quantum foam: A life in physics. W. W. Norton. ISBN 0-393-04642-7.
• Robert Wright, 1989. Three Scientists and Their Gods: Looking for Meaning in an Age of Information. HarperCollins. ISBN 0-06-097257-2. This book discusses Edward Fredkin's work.
• Konrad Zuse, 1970. Calculating Space. The English translation of his Rechnender Raum.

External links[link]

• Luciano Floridi, "Against Digital Ontology", Synthese, 2009, 168.1, (2009), 151-178.
• Edward Fredkin:
  • Digital Philosophy site - Temporarily doesn't work.
  • Introduction to Digital Philosophy - Temporarily doesn't work.
• Gontigno, Paulo, "Hypercomputation and the Physical Church-Turing thesis"
• Petrov, Plamen, and Joel Dobrzelewski, 1998. Digital Physics
• Juergen Schmidhuber:
  • Home page, 1996-2007
  • Computer Universes and Algorithmic Theory of Everything
  • "Zuse's Thesis: The Universe is a Computer"
• Konrad Zuse, PDF scan of Zuse's paper.

• Digital physics. Mountain Math Software.
• The Oxford Advanced Seminar on Informatic Structures
• Wired: God is the Machine
• Gualtiero Piccinini. Computation in Physical Systems Discusses the metaphysical foundations of digital physics in section 3.4.

This article's lead section may not adequately summarize its contents. Please consider expanding the lead to provide an accessible overview of the article's key points. (September 2011)

Gregory John Chaitin^{[pronunciation?]} (born 1947) is an Argentine-American mathematician and computer scientist.

Mathematics and computer science[link]

Beginning in 2009 Chaitin has worked on metabiology, a field parallel to biology dealing with the evolution of artificial software (computer programs) instead of natural software (DNA).

Beginning in the late 1960s, Chaitin made contributions to algorithmic information theory and metamathematics, in particular a new incompleteness theorem in reaction to Gödel's incompleteness theorem. He attended the Bronx High School of Science and City College of New York, where he (still in his teens) developed the theories that led to his independent discovery of Kolmogorov complexity.^[2][3]

Chaitin has defined Chaitin's constant Ω, a real number whose digits are equidistributed and which is sometimes informally described as an expression of the probability that a random program will halt. Ω has the mathematical property that it is definable but not computable.

Chaitin's early work on algorithmic information theory paralleled the earlier work of Kolmogorov.

Chaitin is also the originator of using graph coloring to do register allocation in compiling, a process known as Chaitin's algorithm.

Other scholarly contributions[link]

Chaitin also writes about philosophy, especially metaphysics and philosophy of mathematics (particularly about epistemological matters in mathematics). In metaphysics, Chaitin claims that algorithmic information theory is the key to solving problems in the field of biology (obtaining a formal definition of ‘life’, its origin and evolution) and neuroscience (the problem of consciousness and the study of the mind).

Indeed, in recent writings, he defends a position known as digital philosophy. In the epistemology of mathematics, he claims that his findings in mathematical logic and algorithmic information theory show there are “mathematical facts that are true for no reason, they're true by accident. They are random mathematical facts”. Chaitin proposes that mathematicians must abandon any hope of proving those mathematical facts and adopt a quasi-empirical methodology.

Honors[link]

In 1995 he was given the degree of doctor of science honoris causa by the University of Maine. In 2002 he was given the title of honorary professor by the University of Buenos Aires in Argentina, where his parents were born and where Chaitin spent part of his youth. In 2007 he was given a Leibniz Medal by Wolfram Research. In 2009 he was given the degree of doctor of philosophy honoris causa by the National University of Córdoba. He was formerly a researcher at IBM's Thomas J. Watson Research Center and is now a professor at the Federal University of Rio de Janeiro.

Criticism[link]

Some philosophers and logicians^[who?] strongly disagree with the philosophical conclusions that Chaitin has drawn from his theorems.^[4] The logician Torkel Franzén ^[5] criticizes Chaitin’s interpretation of Gödel's incompleteness theorem and the alleged explanation for it that Chaitin’s work represents.

See also[link]

• Digital philosophy
• Halting problem

Bibliography[link]

• Information, Randomness & Incompleteness (World Scientific 1987) [1]
• Algorithmic Information Theory (Cambridge University Press 1987) online,^{[dead link]}
• Information-Theoretic Incompleteness (World Scientific 1992) online,^{[dead link]}
• The Limits of Mathematics (Springer-Verlag 1998),
• The Unknowable (Springer-Verlag 1999),
• Exploring Randomness (Springer-Verlag 2001),
• Conversations with a Mathematician (Springer-Verlag 2002),
• From Philosophy to Program Size (Tallinn Cybernetics Institute 2003),
• Meta Math!: The Quest for Omega (Pantheon Books 2005) (reprinted in UK as Metamaths: The Quest for Omega, Atlantic Books 2006),
• Teoria algoritmica della complessità (G. Giappichelli Editore 2006),
• Thinking about Gödel & Turing (World Scientific 2007),
• Mathematics, Complexity and Philosophy (Editorial Midas 2011),
• Gödel's Way (CRC Press 2012),
• Proving Darwin: Making Biology Mathematical (Pantheon Books 2012).

Notes[link]

1. ^ Gregory Chaitin (2007), Algorithmic information theory: "Chaitin Research Timeline"
2. ^ Li and Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, Springer 1997, page 92: G.J.Chaitin had finished the Bronx High School of Science , and was an 18-year-old undergraduate student at City College of the City University of New York, when he submitted two papers [...] In his [second] paper, Chaitin puts forward the notion of Kolmogorov complexity [...]"
3. ^ Chaitin, GJ, On the Length of Programs for Computing Finite Binary Sequences, Journal of the ACM (JACM), 13:4, October 1966, 547-569.
4. ^ Panu Raatikainen "Exploring Randomness and The Unknowable" Notices of the American Mathematical Society Book Review October 2001
5. ^ Torkel Franzén Gödel's Theorem: An Incomplete Guide to its Use and Abuse. Wellesley, Massachusetts: A K Peters, Ltd., 2005. x + 172 pp. ISBN 1-56881-238-8.

References[link]

• Ugo Pagallo, Introduzione alla filosofia digitale. Da Leibniz a Chaitin, (G. Giappichelli Editore, 2005) ISBN 88-348-5635-X
• Cristian S. Calude (ed.), Randomness and Complexity. From Leibniz to Chaitin, (World Scientific, 2007) ISBN 978-981-277-082-0

External links[link]

• G J Chaitin Home Page
• List of publications of G J Chaitin
• Video of lecture on metabiology: "Life as evolving software"
• Works by or about Gregory Chaitin in libraries (WorldCat catalog)
• New Scientist article (March, 2001) on Chaitin, Omegas and Super-Omegas
• A short version of Chaitin's proof