One recursively enumerable real α dominates another one β if there are nondecreasing recursive sequences of rational numbers (a[n] : n ∈ ω) approximating α and (b[n] : n ∈ ω) approximating β and a positive constant C such that for all n, C(α − a[n]) ≥ (β − b[n]). See [R. M. Solovay, Draft of a Paper (or Series of Papers) on Chaitin’s Work, manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1974, p. 215] and [G. J. (...) Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. We show that every recursively enumerable random real dominates all other recursively enumerable reals. We conclude that the recursively enumerable random reals are exactly the Ω-numbers [G. J. Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. Second, we show that the sets in a universal Martin-Lof test for randomness have random measure, and every recursively enumerable random number is the sum of the measures represented in a universal Martin-Lof test. (shrink)

A Computable Universe is a collection of papers discussing computation in nature and the nature of computation, a compilation of the views of the pioneers in the contemporary area of intellectual inquiry focused on computational and informational theories of the world. This volume is the definitive source of informational/computational views of the world, and of cutting-edge models of the universe, both digital and quantum, discussed from a philosophical perspective as well as in the greatest technical detail. (...) The book discusses the foundations of computation in relation to nature. It focuses on two main questions: What is computation? How does nature compute? The contributors are world-renowned experts who have helped shape a cutting-edge computational understanding of the universe. They discuss computation in the world from a variety of perspectives, ranging from foundational concepts to pragmatic models to ontological conceptions and their philosophical implications. The volume provides a state-of-the-art collection of technical papers and non-technical essays representing a field that takes information and computation to be key to understanding and explaining the basic structure underpinning physical reality. It also includes a new edition of Konrad Zuse's "Calculating Space", and a panel discussion transcription on the topic, featuring worldwide experts (including a Nobel prize) in quantum mechanics, physics, cognition, computation and algorithmic complexity.A Computable Universe is a collection of papers discussing computation in nature and the nature of computation, a compilation of the views of the pioneers in the contemporary area of intellectual inquiry focused on computational and informational theories of the world. This volume is the definitive source of informational/computational views of the world, and of cutting-edge models of the universe, both digital and quantum, discussed from a philosophical perspective as well as in the greatest technical detail. The book discusses the foundations of computation in relation to nature. It focuses on two main questions: What is computation? How does nature compute? The contributors are world-renowned experts who have helped shape a cutting-edge computational understanding of the universe. They discuss computation in the world from a variety of perspectives, ranging from foundational concepts to pragmatic models to ontological conceptions and their philosophical implications. The volume provides a state-of-the-art collection of technical papers and non-technical essays representing a field that takes information and computation to be key to understanding and explaining the basic structure underpinning physical reality. It also includes a new edition of Konrad Zuse's "Calculating Space", and a panel discussion transcription on the topic, featuring worldwide experts (including a Nobel prize) in quantum mechanics, physics, cognition, computation and algorithmic complexity. (shrink)

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)

The very idea of a noncomputable universe creates considerable anxiety among not a few cosmologists and mathematical theorists. This brief paper offers some suggestions as to why noncomputability constitutes a threat to a certain philosophical mentality.

We present a simple example that disproves the universality principle. Unlike previous counter-examples to computational universality, it does not rely on extraneous phenomena, such as the availability of input variables that are time varying, computational complexity that changes with time or order of execution, physical variables that interact with each other, uncertain deadlines, or mathematical conditions among the variables that must be obeyed throughout the computation. In the most basic case of the new example, all that is used (...) is a single pre-existing global variable whose value is modified by the computation itself. In addition, our example offers a new dimension for separating the computable from the uncomputable, while illustrating the power of parallelism in computation. (shrink)

The purpose of this paper is to provide an account of the epistemology and metaphysics of universe creation on a computer. The paper begins with F.J.Tipler's argument that our experience is indistinguishable from the experience of someone embedded in a perfect computer simulation of our own universe, hence we cannot know whether or not we are part of such a computer program ourselves. Tipler's argument is treated as a special case of epistemological scepticism, in a similar vein to (...) `brain-in-a-vat' arguments. It is argued that the hypothesis that our universe is a program running on a digital computer in another universe generates empirical predictions, and is therefore a falsifiable hypothesis. The computer program hypothesis is also treated as a hypothesis about what exists beyond the physical world, and is compared with Kant's metaphysics of noumena. It is proposed that a theory about what exists beyond the physical world should be formulated with the precise concepts of mathematics, and should generate physical predictions. It is argued that if our universe is a program running on a digital computer, then our universe must have compact spatial topology, and the possibilities of observationally testing this prediction are considered. The possibility of testing the computer program hypothesis with the value of the density parameter Omega_0 is also analysed. The informational requirements for a computer to represent a universeexactly and completely are considered. Consequent doubt is thrown upon Tipler's claim that if a hierarchy of computer universes exists, we would not be able to know which `level of implementation' our universe exists at. It is then argued that a digital computer simulation of a universe cannot exist as a universe. However, the paper concludes with the acknowledgement that an analog computer simulation can be objectively related to the thing it represents, hence an analog computer simulation of a universe could, in principle, exist as a universe. (shrink)

Computational complexity theory is a branch of computer science dedicated to classifying computational problems in terms of their difficulty. While computability theory tells us what we can compute in principle, complexity theory informs us regarding our practical limits. In this chapter I argue that the science of \emph{quantum computing} illuminates complexity theory by emphasising that its fundamental concepts are not model-independent, but that this does not, as some suggest, force us to radically revise the foundations of the theory. (...) For model-independence never has been essential to those foundations. The fundamental aim of complexity theory is to describe what is achievable in practice under various models of computation for our various practical purposes. Reflecting on quantum computing illuminates complexity theory by reminding us of this, too often under-emphasised, fact. (shrink)

The scope of Platonism is extended by introducing the concept of a “Platonic computer” which is incorporated in metacomputics. The theoretical framework of metacomputics postulates that a Platonic computer exists in the realm of Forms and is made by, of, with, and from metaconsciousness. Metaconsciousness is defined as the “power to conceive, to perceive, and to be self-aware” and is the formless, con-tentless infinite potentiality. Metacomputics models how metaconsciousness generates the perceived actualities including abstract entities and physical and nonphysical realities. (...) It is postulated that this is achieved via digital computation using the Platonic computer. The introduction of a Platonic computer into the realm of Forms thus bridges the “inverse explanatory gap” and therefore solves the “inverse hard problem of consciousness” in the philosophy of mind. (shrink)

Fluid neural networks can be used as a theoretical framework for a wide range of complex systems as social insects. In this article we show that collective logical gates can be built in such a way that complex computation can be possible by means of the interplay between local interactions and the collective creation of a global field. This is exemplified by a NOR gate. Some general implications for ant societies are outlined. ©.

Computer simulation and philosophy of science Content Type Journal Article Pages 1-4 DOI 10.1007/s11016-011-9567-8 Authors Wendy S. Parker, Department of Philosophy, Ellis Hall 202, Ohio University, Athens, OH 45701, USA Journal Metascience Online ISSN 1467-9981 Print ISSN 0815-0796.

From the very beginning of ancient Greek philosophy up to the present day a puzzling correlation is found between rationality and reality. In this study this relation is examined with emphasis on the philosophical tradition of Aristotle and Aquinas. A comparison is made with the virtual reality created by computers and actual reality of our universe. The view expressed in the scientific neopositivism of Jordan and Mach is found to be an adequate approach to avoid contradictions in the interpretation (...) of modern physics. A challenging hypothesis is made by updating the Laplacian Demon by a powerful creative intellect in line with Judeo-Christian tradition. With this hypothesis a new light is shed on several fundamental issues in modern science. (shrink)

We prove a number of results motivated by global questions of uniformity in computabi- lity theory, and universality of countable Borel equivalence relations. Our main technical tool is a game for constructing functions on free products of countable groups. We begin by investigating the notion of uniform universality, first proposed by Montalbán, Reimann and Slaman. This notion is a strengthened form of a countable Borel equivalence relation being universal, which we conjecture is equivalent to the usual notion. With this additional (...) uniformity hypothesis, we can answer many questions concerning how countable groups, probability measures, the subset relation, and increasing unions interact with universality. For many natural classes of countable Borel equivalence relations, we can also classify exactly which are uniformly universal. We also show the existence of refinements of Martin’s ultrafilter on Turing invariant Borel sets to the invariant Borel sets of equivalence relations that are much finer than Turing equivalence. For example, we construct such an ultrafilter for the orbit equivalence relation of the shift action of the free group on countably many generators. These ultrafilters imply a number of structural properties for these equivalence relations. (shrink)

The nature of quantum computation is discussed. It is argued that, in terms of the amount of information manipulated in a given time, quantum and classical computation are equally efficient. Quantum superposition does not permit quantum computers to ''perform many computations simultaneously'' except in a highly qualified and to some extent misleading sense. Quantum computation is therefore not well described by interpretations of quantum mechanics which invoke the concept of vast numbers of parallel universes. Rather, entanglement makes available types of (...) computation processes which, while not exponentially larger than classical ones, are unavailable to classical systems. The essence of quantum computation is that it uses entanglement to generate and manipulate a physical representation of the correlations between logical entities, without the need to completely represent the logical entities themselves. (shrink)

The scope of Platonism is extended by introducing the concept of a “Platonic computer” which is incorporated in metacomputics. The theoretical framework of metacomputics postulates that a Platonic computer exists in the realm of Forms and is made by, of, with, and from metaconsciousness. Metaconsciousness is defined as the “power to conceive, to perceive, and to be self-aware” and is the formless, con-tentless infinite potentiality. Metacomputics models how metaconsciousness generates the perceived actualities including abstract entities and physical and nonphysical realities. (...) It is postulated that this is achieved via digital computation using the Platonic computer. The introduction of a Platonic computer into the realm of Forms thus bridges the “inverse explanatory gap” and therefore solves the “inverse hard problem of consciousness” in the philosophy of mind. (shrink)

In the age of digitization, the world seems to be reducible to a digital computer. However, mathematically, modern quantum field theories do not only depend on discrete, but also continuous concepts. Ancient debates in natural philosophy on atomism versus the continuum are deeply involved in modern research on digital and computational physics. This example underlines that modern physics, in the tradition of Newton’s Principia Mathematica Philosophiae Naturalis, is a further development of natural philosophy with the rigorous methods of mathematics, (...) measuring, and computing. We consider fundamental concepts of natural philosophy with mathematical and computational methods and ask for their ontological and epistemic status. The following article refers to the author’s book, “The Digital and the Real World. Computational Foundations of Mathematics, Science, Technology, and Philosophy.”. (shrink)

This paper examines the use of tablet personal computers and how they interfere with Nigerian undergraduates reading culture and love for educational books. The study adopts a descriptive research design. The University of Ilorin undergraduates constitute the population for this study while 200 level students of three faculties across the university constitute the target population. Stratified sampling technique was used to sample the needed respondents. A researchers’ designed questionnaire was use for data collection. The collected data was analysed using descriptive (...) statistics. The findings revealed that access to tablet computer influence the undergraduate reading culture. Also, 55.7% of 200 level undergraduates read more electronic materials on their tablet computer than printed texts. Based on the findings of this study, it is recommended that students should be encouraged to visit the library and read textbooks since there is certain fundamental knowledge that might not be accessible on the net. (shrink)

Vera & Simon (1993a) have argued that the theories and methods known as situated action or situativity theory are compatible with the assumptions and methodology of the physical symbol systems hypothesis and do not require a new approach to the study of cognition. When the central criterion of computational universality is added to the loose definition of a symbol system which Vera and Simon provide, it becomes apparent that there are important incompatibilities between the two approaches such that situativity (...) theory cannot be subsumed within the symbol systems approach. Symbol systems and situativity theoretic approaches are, and should be seen to be, competing approaches to the study of cognition. (shrink)

The simulation hypothesis has recently excited renewed interest, especially in the physics and philosophy communities. However, the hypothesis specifically concerns {computers} that simulate physical universes, which means that to properly investigate it we need to couple computer science theory with physics. Here I do this by exploiting the physical Church-Turing thesis. This allows me to introduce a preliminary investigation of some of the computer science theoretic aspects of the simulation hypothesis. In particular, building on Kleene's second recursion theorem, I prove (...) that it is mathematically possible for us to be in a simulation that is being run on a computer \textit{by us}. In such a case, there would be two identical instances of us; the question of which of those is ``really us'' is meaningless. I also show how Rice's theorem provides some interesting impossibility results concerning simulation and self-simulation; briefly describe the philosophical implications of fully homomorphic encryption for (self-)simulation; briefly investigate the graphical structure of universes simulating universes simulating universes, among other issues. I end by describing some of the possible avenues for future research that this preliminary investigation reveals. (shrink)

Shi and Aharonov have shown that the Toffoli gate and the Hadamard gate give rise to an approximately universal set of quantum computational gates. We study the basic algebraic properties of this system by introducing the notion of Shi-Aharonov quantum computational structure. We show that the quotient of this structure is isomorphic to a structure based on a particular set of complex numbers (the closed disc with center \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$(\frac{1}{2},\frac{1}{2})$\end{document} and (...) radius \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{1}{2}$\end{document} ). (shrink)

In this philosophical paper, we explore computational and biological analogies to address the fine-tuning problem in cosmology. We first clarify what it means for physical constants or initial conditions to be fine-tuned. We review important distinctions such as the dimensionless and dimensional physical constants, and the classification of constants proposed by Lévy-Leblond. Then we explore how two great analogies, computational and biological, can give new insights into our problem. This paper includes a preliminary study to examine the two (...) analogies. Importantly, analogies are both useful and fundamental cognitive tools, but can also be misused or misinterpreted. The idea that our universe might be modelled as a computational entity is analysed, and we discuss the distinction between physical laws and initial conditions using algorithmic information theory. Smolin introduced the theory of "cosmological natural selection" with a biological analogy in mind. We examine an extension of. (shrink)

Book Review: "David Alan Grier. When Computers Were Human." Isis, 99 (4), December 2008, pp. 870-871.

Putnam (Representations and reality. MIT Press, Cambridge, 1988) and Searle (The rediscovery of the mind. MIT Press, Cambridge, 1992) famously argue that almost every physical system implements every finite computation. This universal implementation claim, if correct, puts at the risk of triviality certain functional and computational views of the mind. Several authors have offered theories of implementation that allegedly avoid the pitfalls of universal implementation. My aim in this paper is to suggest that these theories are still consistent with (...) a weaker result, which is the nomological possibility of systems that simultaneously implement different complex automata. Elsewhere I (Shagrir in J Cogn Sci, 2012) argue that this simultaneous implementation result challenges a computational sufficiency thesis (articulated by Chalmers in J Cogn Sci, 2012). My focus here is on theories of implementation. After presenting the basic simultaneous implementation construction, I argue that these theories do not avoid the simultaneous implementation result. The conclusion is that the idea that the implementation of the right kind of automaton suffices for a possession of a mind is dubious. (shrink)

This is a review of CONDITIONALS: FROM PHILOSOPHY TO COMPUTER SCIENCE, edited by Crocco G., del Cerro L. Fariñas, and Herzig A., Studies in logic and computation, no. 5, Clarendon Press, Oxford University Press, Oxford and New York 1995.