Last revised: September 6, 2003, 2:15 AM
Somewhere in 1936-37, shortly after the appearance of the fundamental work of Turing [Tur36] several researchers, among them Alonzo Church, Alan Turing himself, and (according to some sources) Emil Post as well independently came to the conclusion that all mathematical functions conceivable by the human mind can be also computed on a computational device now known as Universal Turing Machine (UTM)1.
This famous proposition is usually referred to as "Church-Turing(-Post) thesis"; for brevity, we shall denote it below simply as the C-T thesis.
There are various equivalent formulations of the C-T thesis; the one to be used here is:
Definition (Church-Turing thesis): The class of all intuitively computable mathematical functions coincides with the class of all mathematical functions computable on a UTM.
This statement of metaphysical nature lies now at the very foundations of Theoretical Computer Science, known also as Theoretical Informatics, Theory of Algorithms, or Discrete Mathematics. Indeed, the C-T thesis is so widely accepted among mathematical/computer science circles that, in fact, its correctness has never been seriously questioned.2
Sometime around 1960 Edward Fredkin suggested another idea: that the Universe itself is some kind of computational device, namely, a highly parallel computational machine known as cellular automaton (CA).
Fredkin's conjecture remained unpublished until the appearance of Conway's "Game of Life" (GOL) in 1969, and subsequent popular publications by Martin Gardner's [Gar70, Gar71] devoted to the GOL and to cellular automata in general. It was Gardner who first announced the "Universe as a CA" idea in his February 1971 article in the Scientific American series, which later appeared in book form [Gar83].
However, the first publication specially devoted to Fredkin and his theory appeared only in 1988 in form of an interview given to Robert Wright [Wri88a], which was later enlarged and published in a book [Wri88b].
And only in 1990 Fredkin himself wrote a paper [Fre90] devoted to the subject that appears to be the first publication of the idea in a respected scientific journal.
As it often happens in science, Fredkin was not alone in this train of thought... The idea that the Universe might be a cellular automaton was independently proposed and published by Konrad Zuse in the late 1960's [Zus67, Zus69].
From the viewpoint of modern cellular automata theory the ideas of Zuse were somewhat naive. Still, while Fredkin was the first to pursue the idea to its full potential, the contribution of Zuse is equally important (at least, from a historical point of view). Therefore, below we shall credit both men as originators of this truly remarkable idea.
The conjecture made by Zuse and Fredkin is now considered to be pivotal for two relatively new scientific fields: Digital Mechanics (DM) and Digital Physics (DP).
In the present brief article we shall not focus on what is different between these two branches, but rather on what is common to both.
In both DM and DP we consider the Zuse-Fredkin proposition ("The Universe is a CA") to be correct and we operate with it just like classical Computer Science operates with the Church-Turing thesis.
We call this proposition the "Zuse-Fredkin thesis"; for brevity, below we shall denote it simply as the Z-F thesis.
Definition (Zuse-Fredkin thesis): The Universe is a cellular automaton.
Despite undergoing more that forty years of quiet development and having a significant theory behind it, the Z-F thesis remains widely unknown and publicly unacknowledged. In the present work we speculate about the mutual "almost-equivalence" of the C-T and the Z-F theses advancing this as a strong argument in support of the Z-F thesis.
While many arguments in support of the Zuse-Fredkin thesis may be provided (for example, see: [Wri88a, Fre90]), the following, probably, is the shortest we are able to think of.
As we shall show now, if one feels confident about the C-T thesis, there is no reason to mistrust the Z-F thesis, and vice versa.
First, let us consider the opposite, namely that from the validity of the Zuse-Fredkin thesis classical Church-Turing thesis follows immediately.
The argument is straightforward:
If the Universe is a universal cellular automaton (UCA)3, anything that is going on within that UCA, obviously, is some sort of a computational process, and then we ourselves (together with our "mathematical thoughts") are nothing more than algorithms taking place in some specific region of space/time of the automaton.
(If the Universe is a CA, but our thoughts or "intuitively computable mathematical functions" are not(?) algorithms, then please tell us what they are!)
On the other hand, every UCA can emulate any other abstract computational machine4, including a UTM. Hence the C-T thesis follows.
Now, let us begin with the Church-Turing thesis and see why it appears to be a direct suggestion in support of the Zuse-Fredkin thesis.
First of all, please note that the C-T thesis is actually an "immature" form of Z-F thesis; both statements are more or less equivalent (from some certain point of view).
The C-T thesis states that every intuitively computable mathematical function has its isomorphic representation (in the form of an algorithm) on a (somewhat primitive) serial computational device, namely, a UTM.
Zuse-Fredkin thesis says, actually, almost the same thing, i.e. that the Universe itself is a computational device, namely, a highly parallel machine that we call CA.
One can say also that Z-F thesis is a direct "hint" (or even a "physical-like corollary") given by the C-T thesis. Why?
The following is the reasoning proposed:
All of physics, as we know it, is nothing more than an attempt to "compress" Reality into formulae in order to build "mathematical models" (or "theories") that explain phenomena taking place within our Universe.
But: on the other hand, it turns out that any "formula" or "theory" can be represented (according to the C-T thesis) on a UTM.
Since the only way we know to "study" (or "comprehend") Reality is by using mathematical models/theories, then from here to the ingenious Z-F statement that the Universe itself is some kind of computational device, namely, a cellular automaton, there is only one step!
Hence the suggested "near-equivalence" of the two theses.
In modern theoretical physics there exists the notion of a "Theory of everything" (TOE). This is a scientific term denoting an all-embracing and consistent theory about all processes taking part into the Universe we live in.
If we had to summarize the content of the present article very briefly, we could say the following:
In the mid thirties Church and Turing came to the idea that every theory, conceivable by the human mind, can be represented on a universal computer. (Turing, in particular, advanced the UTM as a theoretical computational model. However, the UTM, which is a sequential computational device, is not in any way the best model for doing computation; it is merely one of many, to be exact — historically the first abstract mathematical model — that has been proved to be computationally universal)
In the sixties Fredkin and Zuse came to another idea: that a Theory of everything, existing in the Universe, could be built on a universal computer. (Hence, the whole Universe we live in — as paradoxical as it may seem at first — is nothing but some kind of computer)
Fredkin and Zuse, actually, went much further: they advanced the hypothesis that the solution of the problem what kind of computer the Universe is should be sought in a relatively narrow class of abstract mathematical models for parallel computation known as "cellular automata".
The classical Church-Turing thesis is usually considered to be a successful attempt for mathematical formalization of human thinking and the notion of "abstract mathematical theory". In this sense, we can say that the C-T thesis is related to our "internal world", i.e. to the way we human beings perceive all things that surround us through our mind. Later — to a great extent surprisingly — it turned out that this metaphysical statement has another, much more powerful corollary relating to what the "external world" is, i.e. the Universe as a whole.
It is anticipated that, regardless of the argument presented above, many will tend to refuse to recognize the obvious (for us) strong connection between the two theses. And since the C-T thesis is widely accepted, while the Z-F thesis is not, in the field of Digital Physics we use both statements: the first for its well-established, almost universal acceptance, and the second, the Z-F thesis, for its close affinity to the first and its special CA formulation.
This is mainly to avoid any lengthy and mostly tautological metaphysical discussions whether the two statements are exactly equivalent, to what extent they are equivalent (with regard to "parallelism versus serialism" issue), and things of this sort.
The present work appears to be the leading one in a series of articles devoted to the Digital Physics [Pet02]. Therefore, here we will not consider the obvious question why the Universe is exactly a CA, but not some other computational model; this question, however, will be studied in detail in the next articles of this Series [Pet02a2, Pet02a3].
* This article is a part of planned "Series of Brief Articles about Digital Physics (DP)" — see ref. [Pet02].
1 "Universal computing machine" is the term used by Turing for UTM in [Tur36].
2 In the modern times, things have become slightly complicated with the proposition of so-called "quantum computation" (QC); the hope here is to use some phenomena known from quantum mechanics (QM) in order to demonstrate novel ways of doing computation. However, even QC proponents do not question actually the correctness of the C-T thesis; they merely insist that some kind of "speedup" should be gained if we use certain QM effects during the computational process.
3 In its original form, the Zuse-Fredkin thesis merely states that the Universe is a CA, not certainly a universal CA. However, the latter is often considered to be "tacitly implied" in the definition of Z-F thesis — much like we are accustomed to think of the smaller, but more powerful class of UTMs when we talk about TMs.
4 While the very fact that any given universal computational machine can emulate any other (universal) computational machine is merely a tautology that follows directly from the definition of universality as a notion, the explicit construction of the emulation sometimes might be very complicated. For an example of how "Game of Life" (that appears to be a two-dimensional universal CA) can emulate a UTM check out [Ren00].
[Fre90] Fredkin, Edward, "Digital Mechanics: An Informational Process Based on Reversible Universal CA", Physica D 45 (1990) . Online version: http://digitalphilosophy.org/dm_paper.htm
[Gar70] Gardner, Martin, "The Fantastic Combinations of John Conway's New Solitaire Game of 'Life' ", Scientific American 223 (October 1970) . Online version: http://hensel.lifepatterns.net/october1970.html
[Gar71] Gardner, Martin, "Mathematical Games: On Cellular Automata, Self-Reproduction, the Garden of Eden, and the Game 'Life' ", Scientific American (February 1971) .
[Gar83] Gardner, Martin, Wheels, Life and Other Mathematical Amusements, W.H.Freeman and Company (1983). Translated into Russian as: "Krestiki-noliki" ("Tic-Tac-Toe"), Moscow, Mir (1988). See the last three chapters of this book.
[Pet02] Petrov, Plamen, Series of Brief Articles about Digital Physics (DP), in preparation. For the latest update, check out: https://digitalphysics.org/Publications/Petrov/DPSeries/
[Pet02a2] Petrov, Plamen, "Church-Turing Thesis as an Immature Form of Zuse-Fredkin Thesis (More Arguments in Favour of the 'Universe as a Cellular Automaton' Idea)". This article is a part of [Pet02].
Online version: https://digitalphysics.org/Publications/Petrov/Pet02a2/Pet02a2.htm
[Pet02a3] Petrov, Plamen, "Zuse-Fredkin Thesis is the Ultimate Form of Church-Turing Thesis", in preparation. This article is a part of [Pet02].
[Ren00] Rendell, Paul, A Turing Machine in Conway's Game of Life, extendable to a Universal Turing Machine, online document (02-Apr-2000). In: Andrew Adamatzky (ed.), "Collision-Based Computing", Springer Verlag (2002). See: "Turing Universaility of the Game of Life".
Online version: http://rendell.server.org.uk/gol/tm.htm
[Tur36] Turing, Alan, "On Computable Numbers, With an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Series 2, Volume 42 (1936-37) ; Corrections, Ibid., vol. 43 (1937) . Reprinted in M. David (ed.), "The Undecidable", Hewlett, NY: Raven Press (1965).
Online version: http://www.abelard.org/turpap2/tp2-ie.asp
[Wri88a] Wright, Robert, "Did the Universe Just Happen?", Atlantic Monthly (April 1988) 29-44. Translated into Bulgarian as: "Kompjutar li e Vselenata?" ("Is the Universe a Computer?"), Spectar 66 (1989) 42-51.
Online version (in English): https://digitalphysics.org/Publications/Wri88a/html/
Online version (in Bulgarian): https://digitalphysics.org/Publications/Wri88a-Bul/html/
[Wri88b] Wright, Robert, Three Scientists and Their Gods: Looking for Meaning in an Age of Information, Times Books (1988). See: "Part One: Edward Fredkin".
[Zus67] Zuse, Konrad, "Rechnender Raum", Elektronische Datenverarbeitung 8 (1967) . Available online at:
[Zus69] Zuse, Konrad, "Rechnender Raum", Schriften zur Datenverarbeitung, Band 1, Friedrich Vieweg & Sohn, Braunschweig (1969). English translation: "Calculating Space", MIT Technical Translation AZT-70-164-GEMIT, MIT (Proj. MAC), Cambridge, Mass. 02139, Feb. 1970. Available online at: