A Computable Universe

The following sections are included:

• Contents

• Foreword

• Preface

• Acknowledgements

The following sections are included:

• Understanding Computation & Exploring Nature as Computation
  • What is computation? How does nature compute?

• The Algorithmic Approach
  • Information and structure in living organisms

• Determinism from Quantum Mechanics?

• From String Theory to Bit String Theory
  • An algorithmic approach to the problem of fine tuning
  • Black holes as perfect data compressors

• References

Alan Turing continues to dazzle, enlighten and bemuse. His work is difficult to situate, straddling as it does theory, practice and philosophical speculation. The nature and extent of his influence continues to elude us, and the haunting originality of his work resists convenient typecasting. He was capable of blinding clarity as well as of near-mystical obscurity that has an ability to tantalise, madden, and stretch our horizons at the same time. His formal description of a universal computing engine predates the practical implementation of the general-purpose electronic stored-program digital computer, but his influence on its realisation is difficult to nail down This is partly due to the continuing legacy of war-time secrecy but also the general paucity of documentary records.

To help locate Turing’s ideas in the larger trajectories of computer history I propose here to revisit the back-story of computing to identify the core ideas embodied in the realisation of the modern computer. Most of these emerged explicitly in the 19th century, a surprising assertion given the accepted modernity of the field. I hope to show that making this assertion is not a presumptuous grab by history to appropriate the triumphs of the late 20th and early 21st centuries, but rather a place-holder for an intriguing set of connections between computing pre-history and the electronic era.

The following sections are included:

• Introduction

• Why Turing Rules

• Two Theses, Two Sides
  • Post’s thesis I: Generating sequences and limits of the computable
  • Post’s thesis II: Solvability and the realm of the computable
  • “When the bubble of symbolic logic finally burst…”

• Some Afterthoughts

• References

What is it for a physical machine to be an implementation of an abstract one? In this paper we shall provide an answer to this question that has its origins in the computer science concept of formal specification.

We describe axiomatizations of several aspects of effectiveness: effectiveness of transitions; effectiveness relative to oracles; and absolute effectiveness, as posited by the Church-Turing Thesis.

Church’s and Turing’s theses assert dogmatically that an informal notion of effective calculability is adequately captured by a particular mathematical concept of computability. I present analyses of calculability that are embedded in a rich historical and philosophical context, lead to precise concepts, and dispense with theses…

There are growing uncertainties surrounding the classical model of computation established by Gödel, Church, Kleene, Turing and others in the 1930s onwards. The mismatch between the Turing machine conception, and the experiences of those more practically engaged in computing, has parallels with the wider one between science and those working creatively or intuitively out in the ‘real’ world. The scientific outlook is more flexible and basic than some understand or want to admit. The science is subject to limitations which threaten careers. We look at embodiment and disembodiment of computation as the key to the mismatch, and find Turing had the right idea all along – amongst a productive confusion of ideas about computation in the real and the abstract worlds.

Intuitionistic mathematics perceives subtle variations in meaning where classical mathematics asserts equivalence, and permits geometrically and computationally motivated axioms that classical mathematics prohibits. It is therefore well-suited as a logical foundation on which questions about computability in the real world are studied.

The realizability interpretation explains the computational content of intuitionistic mathematics, and relates it to classical models of computation, as well as to more speculative ones that push the laws of physics to their limits. Through the realizability interpretation Brouwerian continuity principles and Markovian computability axioms become statements about the computational nature of the physical world.

Concurrency is of crucial importance to the science and engineering of computation in part because of the rise of the Internet and many-core architectures. However, concurrency extends computation beyond the conceptual framework of Church, Gandy [1980], Gödel, Herbrand, Kleene [1987], Post, Rosser, Sieg [2008], Turing, etc. because there are effective computations that cannot be performed by Turing Machines…

In this paper we present in a tutorial fashion the framework of reaction systems — a formal approach to investigating processes instigated by the living cell. The main idea behind this approach is that this functioning is determined by interactions between biochemical reactions, and these interactions are based on two mechanisms, facilitation and inhibition.

In this paper we look at links between biology and computer science, at how Turing machines may change our look of bacteria, at how colonies of bacteria could be classified and how hyperbolic cellular automata could be used to better understand the behaviour of colonies of bacteria.

The computing disciplines face difficult challenges by extending CMOS technology to and beyond the end of dimensional scaling. One solution path is to use an innovative combination of novel devices, compute paradigms, and architectures to create new information processing technology. It is reasonable to expect that future devices will increasingly exhibit extreme physical variation, and thus have a partially or entirely unknown structure with limited functional control. In this chapter we argue and illustrate that unorganized compute machines—as originally also proposed by Alan M. Turing in a little known report—are a promising solution to address some of the challenges. Such unconventional machines can even have significant benefits over their conventional counterparts, however, we need to use different communication and compute paradigms.

Amorphous computing presents a novel computational paradigm. From a computational viewpoint, amorphous computing systems differ from the classical ones almost in every aspect. They consist of a set of tiny, independent, anonymous and self-powered processors or robots that can communicate wirelessly to a limited distance. The processors are simplified down to the absolute necessaries in order to enable their massive production. The amorphous systems appear in many variants. Their processors can be randomly placed in a closed area or volume and form an ad-hoc network; in some applications they can move, either actively, or passively (e.g., in a bloodstream). Depending on their environment, they can communicate either via radio or via signal molecules. Assuming exponential progress in all sciences resulting in our ability to produce amorphous computing systems with myriads of processors, an unmatched application potential is expected profoundly to change all areas of science and life.

In this paper, we will review the developing features of computations based on rings. Particularly, we will analyse what kinds of interaction occur between gliders travelling on a ‘cyclotron’ cellular automaton derived from a catalog of collisions. We will demonstrate that collisions between gliders emulate the basic types of interaction that occur between localizations in non-linear media: fusion, elastic collision, and soliton-like collision. Computational outcomes of a swarm of gliders circling on a one-dimensional torus are analysed via implementation of some simple computing models. Gliders in one-dimensional cellular automata are compact groups of non-quiescent patterns translating along an automaton lattice. They are cellular-automaton analogous to localizations or quasi-local collective excitations travelling in a spatially extended non-linear medium. So, they can be represented as binary strings or symbols travelling along a one-dimensional ring, interacting with each other and changing their states, or symbolic values, as a result of interactions. We present a number of complex one-dimensional cellular automata with such features.

The following sections are included:

• Turing as a Biologist

• Introduction to this Paper

• History of Metabiology

• Modeling Evolution
  • Software organisms
  • The hill-climbing algorithm
  • Fitness
  • What is a mutation?
  • Mutation distance
  • Hidden use of oracles

• Model A (Naming Integers) Exhaustive Search
  • The Busy Beaver function
  • Proof of Theorem 1 (exhaustive search)

• Model A (Naming Integers) Intelligent Design
  • Another Busy Beaver function
  • Improving lower bounds on Ω
  • Proof of Theorem 2 (intelligent design)

• Model A (Naming Integers) Cumulative Evolution at Random

• Model B (Naming Functions)

• Remarks on Model C (Naming Ordinals)

• Conclusion

• Appendix. AIT in a Nutshell

• References

This is an outline of the origins and development of the way computability theory and algorithmic complexity theory were incorporated into economic and finance theories. We try to place, in the context of the development of computable economics, some of the classics of the subject as well as those that have, from time to time, been credited with having contributed to the advancement of the field. Speculative thoughts on where the frontiers of computable economics are, and how to move towards them, conclude the paper. In a precise sense — both historically and analytically — it would not be an exaggeration to claim that both the origins of computable economics and its frontiers are defined by two classics, both by Banach and Mazur: that one page masterpiece by Banach and Mazur (⁶), built on the foundations of Turing’s own classic, and the unpublished Mazur conjecture of 1928, and its unpublished proof by Banach (³⁹, ch. 6 &⁶⁹, ch. 1, §.6). For the undisputed original classic of computable economics is Rabin’s effectivization of the Gale-Stewart game (⁴³;¹⁷); the frontiers, as I see them, are defined by recursive analysis and constructive mathematics, underpinning computability over the computable and constructive reals and providing computable foundations for the economist’s Marshallian penchant for curve-sketching (¹⁰;²⁰; and, in general, the contents of Theoretical Computer Science, Vol. 219, Issue 1-2). The former work has its roots in the Banach-Mazur game (cf.³⁹, especially p. 30), at least in one reading of it; the latter in (⁶), as well as other, earlier, contributions, not least by Brouwer.

We sketch the developments that led to the construction of the da Costa and Doria expression for the halting function in languages more powerful than arithmetic, and use it to describe a plausible real hypercomputer.

In this paper, we employ the method of computational philosophy, the use of computational techniques to aid in the discovery of philosophical insights that might not be easily discovered otherwise, to show that it is not unreasonable to suggest 1) that there are genuine teleological causes in nature, 2) that such causes can be computed from Newtonian (“push”) causation, provided that other architectural and environmental conditions are met, and 3) that it is possible to do so without recourse to semantics by taking an information-theoretic approach to measuring information flow in a system.

The following sections are included:

• Introduction

• Understanding DTP
  • Informational characteristics

• Philosophical Speculations

Is there a short and fast program that can compute the precise history of our universe, including all seemingly random but possibly actually deterministic and pseudo-random quantum fluctuations? There is no physical evidence against this possibility. So let us start searching! We already know a short program that computes all constructively computable universes in parallel, each in the asymptotically fastest way. Assuming ours is computed by this optimal method, we can predict that it is among the fastest compatible with our existence. This yields testable predictions.

Nearly all theories developed for our world are computational. The fundamental theories in physics can be used to emulate on a computer ever more aspects of our universe. This and the ubiquity of computers and virtual realities has increased the acceptance of the computational paradigm. A computable theory of everything seems to have come within reach. Given the historic progression of theories from ego- to geo- to helio-centric models to universe and multiverse theories, the next natural step was to postulate a multiverse composed of all computable universes. Unfortunately, rather than being a theory of everything, the result is more a theory of nothing, which actually plagues all too-large universe models in which observers occupy random or remote locations. The problem can be solved by incorporating the subjective observer process into the theory. While the computational paradigm exposes a fundamental problem of large-universe theories, it also provides its solution.

This essay uses insights from studying the computational universe to explore questions about possibility and impossibility in the physical universe and in physical theories. It explores the ultimate limits of technology and of human experience, and their relation to the features and consequences of ultimate theories of physics.

The following sections are included:

• Computation and Physics

• Cellular Automata

• Processes and Observers

• References

The following sections are included:

• Introduction
  • Computational universe conjecture
  • Causal set program
  • The plan
  • And the quantum mechanical view?

• Causets from Probabilistic Procedures
  • Causets from random sprinklings
  • Causets from transitive percolation dynamics

• Causets from Sequential Deterministic Computations
  • A preliminary inspection of RW-causets
  • Forgetting non recent write operations: from fat to thin RW-causets
  • The case of elementary Turing machines

• Causets from Touring Ants
  • Touring ants on circular binary tapes
  • Touring ants on planar trivalent networks

• Emergent Properties of Touring Ant Causets
  • Deterministic chaos in trinet mobile automata
  • Dimensional analysis
  • Particles?

• More on Dimensional Analysis

• Conclusions

• Acknowledgements

• References

When can a model of a physical system be regarded as computable? We provide the definition of a computable physical model to answer this question. The connection between our definition and Kreisel’s notion of a mechanistic theory is discussed, and several examples of computable physical models are given, including models which feature discrete motion, a model which features non-discrete continuous motion, and probabilistic models such as radioactive decay. We show how computable physical models on effective topological spaces can be formulated using the theory of type-two effectivity (TTE). Various common operations on computable physical models are described, such as the operation of coarse-graining and the formation of statistical ensembles. The definition of a computable physical model also allows for a precise formalization of the computable universe hypothesis—the claim that all the laws of physics are computable.

The belief that the physical Universe is a knowable system governed by rules which determine its future uniquely and completely has dominated the Western civilisation in the last two and a half millennia. The goal of this paper is to provide new arguments in favour of the hypothesis that the Universe is lawless, a hypothesis proposed and discussed in our papers.

Although various limits on the predicability of physical phenomena as well as on physical knowables are commonly established and accepted, we challenge their ultimate validity. More precisely, we claim that fundamental limits arise only from our limited imagination and fantasy. To illustrate this thesis we give evidence that the well-known Turing incomputability barrier can be trespassed via quantum indeterminacy. From this algorithmic viewpoint, the “fine tuning” of physical phenomena amounts to a “(re)programming” of the universe.

So it seems we’re asking ourselves today “What is Computation?” and either “Does Nature Compute?” or “How Does Nature Compute?” And there’s an amazing fact that motivates both of these questions and indeed motivates every other foundational question about computation as well. It is this: if you take any physical variable whatsoever, for example “who is going to be the next president of the United States”, to take a topical example or, another one is “the mean temperature of the Earth’s atmosphere as a function of time” and ask how that variable depends on other variables, then the answer will always invariably be a computable function—or, if there’s quantum indeterminacy involved then the probability distribution function will be a computable function. This is because the laws of physics refer only to computable functions—either directly or via computable differential equations…

This article reviews the history of digital computation, and investigates just how far the concept of computation can be taken. In particular, I address the question of whether the universe itself is in fact a giant computer, and if so, just what kind of computer it is. I will show that the universe can be regarded as a giant quantum computer. The quantum computational model of the universe explains a variety of observed phenomena not encompassed by the ordinary laws of physics. In particular, the model shows that the the quantum computational universe automatically gives rise to a mix of randomness and order, and to both simple and complex systems.

Quantum information processing promises to beat limitations of “classical” information processing. We can have theoretically unbeatable quantum cryptography, which has by now very many technical implementations. We might have quantum computers, which in principle perform some tasks exponentially faster (in terms of operations needed) than classical ones, i.e. ones which are realizations of Turing machines…

What kind of computer is the universe? Here we present three results. The first is a consequence of the Kochen-Specker theorem: If the predictions of quantum mechanics are correct, then the universe cannot be a non-contextual computer. We then show that, if we assume that the density of memory is bounded, then the universe cannot be a classical contextual computer. The third result singles out the universe among all possible contextual computers by exploiting a curious connection with graph theory: In the universe, the maximal contextuality of a set of propositions is given by the Lovász number of the graph representing their mutual exclusiveness.

By a diagonalisation argument, Bell states are not distinguishable from inside. This result is closely related to the theorems of Gödel, Church, and Turing in spite of important dissimilarities.

We suggest that the ordinary human thought can have both the classical and the quantum computational modes. Due to massive parallelism, the quantum computational mode is exponentially faster than its classical counterpart, thus it can account for some extremely rapid mental processes, which humans are generally not aware of. The quantum mode is described by a formal Quantum Object-Language (QOL). The associated (quantum) deductive calculus has full access to the hidden quantum information and can reproduce, step-by step, the whole quantum computational process. The classical computational mode derives from the quantum mode through decoherence, and concerns conscious mental processes. The conscious mind, although it benefits of the very rapid data outputting of the preceding quantum mode, can grasp only a bit of the hidden quantum information. There is also a non-algorithmic mode concerning the meta-thought, which accounts for intention, intuition, and control, and stands at the roots of the unconscious mind The non-algorithmic mode is logically described by a formal Quantum Meta-Language (QML), which “talks about” the QOL. Both the quantum mode and the non-algorithmic mode are physically described by Quantum Physics. However, while the propositions of the former are described by qubits states of Quantum Information, the assertions of the latter are interpreted as quantum fields of a Quantum Field Theory of the brain.

The following sections are included:

• Question from T. Bolognesi to Ed Fredkin:

• Answer by Ed Fredkin:

• Question from H. Zenil to M. Margenstern:

• Answer by M. Margenstern:

• Comment by M. Margenstern on C. Calude, W. Meyerstein and A. Salomaa’s chapter:

• Question from H. Zenil to T. Bolognesi:

• Answer by T. Bolognesi:

• Question from H. Zenil to T. Bolognesi:

• Answer by T. Bolognesi:

• Question from C. Teuscher to M. Hutter:

• Answer by M. Hutter:

• Question from C. Teuscher to F. Doria:

• Answer by F. Doria:

• Question from H. Zenil to C. Calude:

• Answer by C. Calude:

• Reply by H. Zenil:

• Reply by C. Calude:

• Reply by H. Zenil:

• Reply by C. Calude:

• Question from M. Hutter to C. Calude:

• Answer by C. Calude:

• Reply by M. Hutter:

• Final reply by C. Calude:

• Question from A. Cabello to C. Calude and K. Svozil:

• Answer from C. Calude and K. Svozil:

• C. Calude aside comment to A. Cabello:

• Question from C. Teuscher to C. Calude and K. Svozil:

• Answer by C. Calude and K. Svozil:

• Question from C. Teuscher to A. Cabello:

• Answer by A. Cabello:

• Question from H. Zenil to A. Cabello:

• Answer by A. Cabello:

• Question from H. Zenil to A. Cabello:

• Answer by A. Cabello:

• Question from H. Zenil to A. Cabello:

• Answer by A. Cabello:

• Reply by H. Zenil:

• Question from H. Zenil to C. Teuscher:

• Answer by C. Teuscher:

• Question from F. Doria to H. Zenil:

• Answer by H. Zenil:

• Question from H. Zenil to L. De Mol:

• Answer by L. De Mol:

• Question from H. Zenil to L. De Mol:

• Answer by L. De Mol:

• Question from H. Zenil to L. De Mol:

• Answer by L. De Mol:

• Question from H. Zenil to K. Sutner:

• Answer by K. Sutner:

• Question from Bolognesi to Hewitt:

• Answer by C. Hewitt:

• Question from H. Zenil to A. Bauer:

• Answer by A. Bauer:

• Question from H. Zenil to A. Bauer:

• Answer by A. Bauer:

• Question from A. Cabello to S. Wolfram:

• Answer by S. Wolfram:

• Question from C. Teuscher to S. Wolfram:

• Answer by S. Wolfram:

• Question from M. Szudzik to S. Wolfram:

• Answer by S. Wolfram:

• Question from L. De Mol to S. Wolfram:

• Answer by S. Wolfram:

The following sections are included:

• QUANTUM VS. CLASSICAL COMPUTATION

• THE IDEA OF COMPUTATION

• IS THE UNIVERSE A COMPUTER?

• IS THE UNIVERSE DISCRETE OR CONTINUOUS?

• IS THE UNIVERSE RANDOM?

• INFORMATION VS. MATTER

• UNMODERATED AUDIENCE QUESTIONS

The work which follows stands somewhat outside the presently accepted method of approach, and it was for this reason rather difficult to find a publisher ready to undertake publication of such a work. For this reason I am indebted to the Vieweg Press and especially to Dr. Schuff for undertaking publication. Dr. Schuff suggested that a summary be printed in the Journal “Elektronische Datenverarbeitung” (Electronic Data Processing), which appeared last year.

The tragic death of Dr. Schuff has deeply shaken his friends, and we will always remember him with affection.

There are many parallels between Zuse’s and Turing’s interests. In the mid 1930s, some researchers were engaged in what amounted to an inquiry into the nature of computation, and trying to figure out whether it would be possible to build a computing machine. In part this was a consequence of Hilbert’s programme, but it was no doubt also due to a certain chain of historical events. As pointed out by Raúl Rojas, people started to think about computers when it was time to build computers. There were of course Schönfinkel (SKI combinators), Church (λ calculus), Post (tag systems), Kleene (recursive functions), Turing (a-machines), among a few others…

The following sections are included:

• Index