Cellular automata (henceforth: CA) are discrete, abstract computational systems that have proved useful both as general models of complexity and as more specific representations of non-linear dynamics in a variety of scientific fields. Firstly, CA are (typically) spatially and temporally discrete: they are composed of a finite or denumerable set of homogeneous, simple units, the atoms or cells. At each time unit, the cells instantiate one of a finite set of states. They evolve in parallel at discrete time steps, following (...) state update functions or dynamical transition rules: the update of a cell state obtains by taking into account the states of cells in its local neighborhood (there are, therefore, no actions at a distance). Secondly, CA are abstract, as they can be specified in purely mathematical terms and implemented in physical structures. Thirdly, CA are computational systems: they can compute functions and solve algorithmic problems. Despite functioning in a different way from traditional, Turing machine-like devices, CA with suitable rules can emulate a universal Turing machine, and therefore compute, given Turing's Thesis, anything computable.... (shrink)

Reply in Book Symposium on James Ladyman, Don Ross: 'Everything must go: metaphysics naturalized', Oxford: Oxford University Press, 2007.

Computational modeling plays an increasingly important explanatory role in cases where we investigate systems or problems that exceed our native epistemic capacities. One clear case where technological enhancement is indispensable involves the study of complex systems.1 However, even in contexts where the number of parameters and interactions that define a problem is small, simple systems sometimes exhibit non-linear features which computational models can illustrate and track. In recent decades, computational models have been proposed as a way to assist us in (...) understanding emergent phenomena. (shrink)

We study some aspects of the emergence of _lógos_ from _xáos_ on a basal model of the universe using methods and techniques from algorithmic information and Ramsey theories. Thereby an intrinsic and unusual mixture of meaningful and spurious, emerging laws surfaces. The spurious, emergent laws abound, they can be found almost everywhere. In accord with the ancient Greek theogony one could say that _lógos_, the Gods and the laws of the universe, originate from “the void,„ or from _xáos_, a picture (...) which supports the unresolvable/irreducible lawless hypothesis. The analysis presented in this paper suggests that the “laws„ discovered in science correspond merely to syntactical correlations, are local and not universal. (shrink)

Does what guides a pastry chef stand on par, from the standpoint of contemporary computer science, with what guides a supercomputer? Did Betty Crocker, when telling us how to bake a cake, provide an effective procedure, in the sense of `effective' used in computer science? According to Cleland, the answer in both cases is ``Yes''. One consequence of Cleland's affirmative answer is supposed to be that hypercomputation is, to use her phrase, ``theoretically viable''. Unfortunately, though we applaud Cleland's ``gadfly philosophizing'' (...) (as, in fact, seminal), we believe that unless such a modus operandi is married to formal philosophy, nothing conclusive will be produced (as evidenced by the problems plaguing Cleland's work that we uncover). Herein, we attempt to pull off not the complete marriage for hypercomputation, but perhaps at least the beginning of a courtship that others can subsequently help along. (shrink)

Machines were introduced as calculating devices to simulate operations carried out by human computers following fixed algorithms. The mathematical study of (paper) machines is the topic of our essay. The first three sections provide necessary logical background, examine the analyses of effective calculability given in the thirties, and describe results that are central to recursion theory, reinforcing the conceptual analyses. In the final section we pursue our investigation in a quite different way and focus on principles that govern the operations (...) of physically realizable machines. (shrink)

This article tells the story of Ed Fredkin, a pilot, programmer, engineer, hardware designer and entrepreneur, whose work inside and outside academia has influenced major developments in computer science and in the foundations of theoretical physics for the past fifty years.

I articulate a novel modal argument for P=NP.

Gödel's Theorem is often used in arguments against machine intelligence, suggesting humans are not bound by the rules of any formal system. However, Gödelian arguments can be used to support AI, provided we extend our notion of computation to include devices incorporating random number generators. A complete description scheme can be given for integer functions, by which nonalgorithmic functions are shown to be partly random. Not being restricted to algorithms can be accounted for by the availability of an arbitrary random (...) function. Humans, then, might not be rule-bound, but Gödelian arguments also suggest how the relevant sort of nonalgorithmicity may be trivially made available to machines. (shrink)

This paper presents a new modified quantum mechanics, Critical Complexity Quantum Mechanics, which includes a new account of wavefunction collapse. This modified quantum mechanics is shown to arise naturally from a fully discrete physics, where all physical quantities are discrete rather than continuous. I compare this theory with the spontaneous collapse theories of Ghirardi, Rimini, Weber and Pearle and discuss some implications of these theories and CCQM for a realist view of the quantum realm.

A new variational method, the principle of least radix economy, is formulated. The mathematical and physical relevance of the radix economy, also called digit capacity, is established, showing how physical laws can be derived from this concept in a unified way. The principle reinterprets and generalizes the principle of least action yielding two classes of physical solutions: least action paths and quantum wavefunctions. A new physical foundation of the Hilbert space of quantum mechanics is then accomplished and it is used (...) to derive the Schrödinger and Dirac equations and the breaking of the commutativity of spacetime geometry. The formulation provides an explanation of how determinism and random statistical behavior coexist in spacetime and a framework is developed that allows dynamical processes to be formulated in terms of chains of digits. These methods lead to a new foundation for Lorentz transformations and special relativity. The Parker-Rhodes combinatorial hierarchy is encompassed within our approach and this leads to an estimate of the interaction strength of the electromagnetic and gravitational forces that agrees with the experimental values to an error of less than one thousandth. Finally, it is shown how the principle of least-radix economy naturally gives rise to Boltzmann’s principle of classical statistical thermodynamics. A new expression for a general nonequilibrium entropy is proposed satisfying the Second Law of Thermodynamics. (shrink)

Selmer Bringsjord & Joshua Taylor∗ Department of Cognitive Science Department of Computer Science The Rensselaer AI & Reasoning (RAIR) Lab Rensselaer Polytechnic Institute (RPI) Troy NY 12180 USA http://www.rpi.edu/∼brings {selmer,tayloj}@rpi.edu..

The central motivating idea behind the development of this work is the concept of prespace, a hypothetical structure that is postulated by some physicists to underlie the fabric of space or space-time. I consider how such a structure could relate to space and space-time, and the rest of reality as we know it, and the implications of the existence of this structure for quantum theory. Understanding how this structure could relate to space and to the rest of reality requires, I (...) believe, that we consider how space itself relates to reality, and how other so-called "spaces" used in physics relate to reality. In chapter 2, I compare space and space-time to other spaces used in physics, such as configuration space, phase space and Hilbert space. I support what is known as the "property view" of space, opposing both the traditional views of space and space-time, substantivalism and relationism. I argue that all these spaces are property spaces. After examining the relationships of these spaces to causality, I argue that configuration space has, due to its role in quantum mechanics, a special status in the microscopic world similar to the status of position space in the macroscopic world. In chapter 3, prespace itself is considered. One way of approaching this structure is through the comparison of the prespace structure with a computational system, in particular to a cellular automaton, in which space or space-time and all other physical quantities are broken down into discrete units. I suggest that one way open for a prespace metaphysics can be found if physics is made fully discrete in this way. I suggest as a heuristic principle that the physical laws of our world are such that the computational cost of implementing those laws on an arbitrary computational system is minimized, adapting a heuristic principle of this type proposed by Feynman. In chapter 4, some of the ideas of the previous chapters are applied in an examination of the physics and metaphysics of quantum theory. I first discuss the "measurement problem" of quantum mechanics: this problem and its proposed solution are the primary subjects of chapter 4. It turns out that considering how quantum theory could be made fully discrete leads naturally to a suggestion of how standard linear quantum mechanics could be modified to give rise to a solution to the measurement problem. The computational heuristic principle reinforces the same solution. I call the modified quantum mechanics Critical Complexity Quantum Mechanics (CCQM). I compare CCQM with some of the other proposed solutions to the measurement problem, in particular the spontaneous localization model of Ghirardi, Rimini and Weber. Finally, in chapters 5 and 6, I argue that the measure of complexity of quantum mechanical states I introduce in CCQM also provides a new definition of entropy for quantum mechanics, and suggests a solution to the problem of providing an objective foundation for statistical mechanics, thermodynamics, and the arrow of time. (shrink)

This paper links the conjecture that the physical world is a virtual reality to the findings of modern physics. What is usually the subject of science fiction is here proposed as a scientific theory open to empirical evaluation. We know from physics how the world behaves, and from computing how information behaves, so whether the physical world arises from ongoing information processing is a question science can evaluate. A prima facie case for the virtual reality conjecture is presented. If a (...) photon is a pixel on a multi-dimensional grid that gives rise to space, the speed of light could reflect its refresh rate. If mass, charge and energy all arise from processing, the many conservation laws of physics could reduce to a single law of dynamic information conservation. If the universe is a virtual reality, then its big bang creation could be simply when the system was booted up. Deriving core physics from information processing could reconcile relativity and quantum theory, with the former how processing creates the space-time operating system and the latter how it creates energy and matter applications. (shrink)