Computation and Physical Systems

Computing, today more than ever before, is a multi-faceted discipline which collates several methodologies, areas of interest, and approaches: mathematics, engineering, programming, and applications. Given its enormous impact on everyday life, it is essential that its debated origins are understood, and that its different foundations are explained. On the Foundations of Computing offers a comprehensive and critical overview of the birth and evolution of computing, and it presents some of the most important technical results and philosophical problems of the discipline, (...) combining both historical and systematic analyses. -/- The debates this text surveys are among the latest and most urgent ones: the crisis of foundations in mathematics and the birth of the decision problem, the nature of algorithms, the debates on computational artefacts and malfunctioning, and the analysis of computational experiments. By covering these topics, On the Foundations of Computing provides a much-needed resource to contextualize these foundational issues. -/- For practitioners, researchers, and students alike, a historical and philosophical approach such as what this volume offers becomes essential to understand the past of the discipline and to figure out the challenges of its future. (shrink)

Digital computers carry out algorithms coded in high level programs. These abstract entities determine what happens at the physical level: they control whether electrons flow through specific transistors at specific times or not, entailing downward causation in both the logical and implementation hierarchies. This paper explores how this is possible in the light of the alleged causal completeness of physics at the bottom level, and highlights the mechanism that enables strong emergence (the manifest causal effectiveness of application programs) to occur. (...) Although synchronic emergence of higher levels from lower levels is manifestly true, diachronic emergence is generically not the case; indeed we give specific examples where it cannot occur because of the causal effectiveness of higher level variables. (shrink)

I analyze a tension at the core of the mechanistic view of computation generated by its joint commitment to the medium independence of computational vehicles and to computational systems possessing teleological functions to compute. While computation is individuated in medium-independent terms, teleology is sensitive to the constitutive physical properties of vehicles. This tension spells trouble for the mechanistic view, suggesting that there can be no teleological functions to compute. I argue that, once considerations about the relevant function-bestowing factors for computational (...) systems are brought to bear, the tension dissolves: physical systems can have the teleological function to compute. (shrink)

Que peut bien être l’informatique pour nous envahir à ce point? Se fondant sur des travaux récents de philosophie de l’informatique, ce livre revient sur la notion de Machine de Turing et sur la Thèse de Church : l’ordinateur peut-il tout simuler? . Eclairant les notions de computation et d’abstraction à la lumière de celles de simulation et d’ontologie, il montre en quoi l’informatique n’est ni simplement une branche des mathématiques, ni une technologie de l’information, mais une technologie des croisements (...) des voies de la référence. (shrink)

In the 1980s, a number of philosophers argued that perception is analog. In the ensuing years, these arguments were forcefully criticized, leaving the thesis in doubt. This paper draws on Weber’s Law, a well-entrenched finding from psychophysics, to advance a new argument that perception is analog. This new argument is an adaptation of an argument that cognitive scientists have leveraged in support of the contention that primitive numerical representations are analog. But the argument here is extended to the representation of (...) non-numerical magnitudes, such as luminance and distance, and shown to apply to perception and not just cognition. The relevant sense of ‘analog’ is also clarified, and two powerful objections are addressed. Finally, the question whether perception’s analog vehicles are located in conscious experience is explored and related to a well-known controversy within psychophysics. (shrink)

In recent history of sociopolitical organization we have observed first the transition to nation states followed by the creation of supranational political organizations. One determining characteristic of these contemporary sociopolitical structures is their sovereignty over increasingly large populations. In this paper we are presenting a theoretical framework through which we can generalize the organization of large numbers of individuals within a system. We are reinterpreting Foucault as to outline a political anatomy of computer architecture, thus establishing the notion of politics (...) in a purely technical system. Through this political framing of a technological artifact we are able to describe organization as a technology with applications to technical and social systems alike. Based on the recognition of shared organizing principles across different systems we adopt Heidegger’s notion of the Gestell as to challenge the immutability of contemporary organization. We concretize Heidegger’s primal truth through Derrida’s notion of a democracy to come and reformulate it within our framework as organizations to come. Integrating the outlined concepts, we are proposing the framework of Large-Scale Systems Composed of Homogeneous Individuals (LSSCHI) allowing for new perspectives on the relationship between individuals, structure, activity and power within large-scale systems. (shrink)

The development of synthetic biology calls for accurate understanding of the critical functions that allow construction and operation of a living cell. Besides coding for ubiquitous structures, minimal genomes encode a wealth of functions that dissipate energy in an unanticipated way. Analysis of these functions shows that they are meant to manage information under conditions when discrimination of substrates in a noisy background is preferred over a simple recognition process. We show here that many of these functions, including transporters and (...) the ribosome construction machinery, behave as would behave a material implementation of the informationmanaging agent theorized by Maxwell almost 150 years ago and commonly known as Maxwell’s demon (MxD). A core gene set encoding these functions belongs to the minimal genome required to allow the construction of an autonomous cell. These MxDs allow the cell to perform computations in an energy-efficient way that is vastly better than our contemporary computers. (shrink)

Defining Ecosophy (ecological wisdom) like a contemporary philosophy of survival, security and a sustainable Human Development, terrestrial nature and society, the author of this article approaches the correlation between it and the digital version of security in the context of new technologies. Human survival is in connection with the protection, optimal functioning of the natural environment and the development of human society. Human evolution, physical and psychological (the issues of Anthropoecology, a medical-biological science, deals with them), depends on the natural (...) and social environment, on the development of new techniques and technologies. New technologies (nano-, bio-, info-, socio-technologies) can ensure the security and the increasing development of the human being, but they can threaten it too. The author does not deny behaviours, the possibility that human intellect could be non-biological. Moreover, the author believes if it comes to it, that we will not be able to speak about the human species. New technologies like the traditional and less new, are intended to help in solving various problems related to health, society interactions with nature, human society and diverse cultures, societies and states. The philosophy of security and the digital one, like the components of Ecosophy, along with philosophical aspects of Anthropoecology, General Ecology and Social Ecology, needs like any other science or philosophy to elaborate systems of concepts, principles and laws. (shrink)

Over the past 50 years, philosophers and psychologists have perennially argued for the existence of analog mental representations of one type or another. This study critically reviews a number of these arguments as they pertain to three different types of mental representation: perceptual representations, imagery representations, and numerosity representations. Along the way, careful consideration is given to the meaning of “analog” presupposed by these arguments for analog mental representation, and to open avenues for future research.

Computational neuroscientists not only employ computer models and simulations in studying brain functions. They also view the modeled nervous system itself as computing. What does it mean to say that the brain computes? And what is the utility of the ‘brain-as-computer’ assumption in studying brain functions? In previous work, I have argued that a structural conception of computation is not adequate to address these questions. Here I outline an alternative conception of computation, which I call the analog-model. The term ‘analog-model’ (...) does not mean continuous, non-discrete or non-digital. It means that the functional performance of the system simulates mathematical relations in some other system, between what is being represented. The brain-as-computer view is invoked to demonstrate that the internal cellular activity is appropriate for the pertinent information-processing task.Keywords: Computation; Computational neuroscience; Analog computers; Representation; Simulation. (shrink)

It is sometimes suggested that the history of computation in cognitive science is one in which the formal apparatus of Turing-equivalent computation, or effective computability, was exported from mathematical logic to ever wider areas of cognitive science and its environs. This paper, however, indicates some respects in which this suggestion is inaccurate. Computability theory has not been focused exclusively on Turing-equivalent computation. Many essential features of Turing-equivalent computation are not captured in definitions of computation as symbol manipulation. Turing-equivalent computation did (...) not play the role in McCulloch and Pitts’s early cybernetic work that is sometimes attributed to it. Finally, various segments of the neuroscientific community invoke a notion of computation that differs from the Turing-equivalent notion.Keywords: Circular causality; Computation; Cortical maps; Neural networks; Symbol manipulation; Turing-equivalent computation. (shrink)

This paper revisits one of the first models of analog computation, the General Purpose Analog Computer. In particular, we restrict our attention to the improved model presented in [11] and we show that it can be further refined. With this we prove the following: the previous model can be simplified; it admits extensions having close connections with the class of smooth continuous time dynamical systems. As a consequence, we conclude that some of these extensions achieve Turing universality. Finally, it is (...) shown that if we introduce a new notion of computability for the GPAC, based on ideas from computable analysis, then one can compute transcendentally transcendental functions such as the Gamma function or Riemann's Zeta function. (shrink)

I have read many recent discussions of the limits of computation and the universe as computer, hoping to find some comments on the amazing work of polymath physicist and decision theorist David Wolpert but have not found a single citation and so I present this very brief summary. Wolpert proved some stunning impossibility or incompleteness theorems (1992 to 2008-see arxiv.org) on the limits to inference (computation) that are so general they are independent of the device doing the computation, and even (...) independent of the laws of physics, so they apply across computers, physics, and human behavior. They make use of Cantor's diagonalization, the liar paradox and worldlines to provide what may be the ultimate theorem in Turing Machine Theory, and seemingly provide insights into impossibility,incompleteness, the limits of computation,and the universe as computer, in all possible universes and all beings or mechanisms, generating, among other things,a non-quantum mechanical uncertainty principle and a proof of monotheism. (shrink)

The dialogue develops arguments for and against a broad new world system - info-computationalist naturalism - that is supposed to overcome the traditional mechanistic view. It would make the older mechanistic view into a special case of the new general info-computationalist framework (rather like Euclidian geometry remains valid inside a broader notion of geometry). We primarily discuss what the info-computational paradigm would mean, especially its pancomputationalist component. This includes the requirements for a the new generalized notion of computing that would (...) include sub-symbolic information processing. We investigate whether pancomputationalism can provide the basic causal structure to the world and whether the overall research program of info-computationalist naturalism appears productive, especially when it comes to new approaches to the living world, including computationalism in the philosophy of mind. (shrink)

There is much discussion about whether the human mind is a computer, whether the human brain could be emulated on a computer, and whether at all physical entities are computers (pancomputationalism). These discussions, and others, require criteria for what is digital. I propose that a state is digital if and only if it is a token of a type that serves a particular function - typically a representational function for the system. This proposal is made on a syntactic level, assuming (...) three levels of description (physical, syntactic, semantic). It suggests that being digital is a matter of discovery or rather a matter of how we wish to describe the world, if a functional description can be assumed. Given the criterion provided and the necessary empirical research, we should be in a position to decide on a given system (e.g. the human brain) whether it is a digital system and can thus be reproduced in a different digital system (since digital systems allow multiple realization). (shrink)

The theory that all processes in the universe are computational is attractive in its promise to provide an understandable theory of everything. I want to suggest here that this pancomputationalism is not sufficiently clear on which problem it is trying to solve, and how. I propose two interpretations of pancomputationalism as a theory: I) the world is a computer and II) the world can be described as a computer. The first implies a thesis of supervenience of the physical over computation (...) and is thus reduced ad absurdum. The second is underdetermined by the world, and thus equally unsuccessful as theory. Finally, I suggest that pancomputationalism as metaphor can be useful. – At the Paderborn workshop in 2008, this paper was presented as a commentary to the relevant paper by Gordana Dodig-Crnkovic " Info-Computationalism and Philosophical Aspects of Research in Information Sciences". (shrink)

Review of: "Computation, Information, Cognition: The Nexus and the Liminal", Ed. Susan Stuart & Gordana Dodig Crnkovic, Newcastle: Cambridge Scholars Publishing, September 2007, xxiv+340pp, ISBN: 9781847180902, Hardback: £39.99, $79.99 ---- Are you a computer? Is your cat a computer? A single biological cell in your stomach, perhaps? And your desk? You do not think so? Well, the authors of this book suggest that you think again. They propose a computational turn, a turn towards computational explanation and towards the explanation of (...) computation itself. The explanation of computation is the core of the present volume, but the computational turn to regard a wide variety of systems as computational is a potentially very wide-ranging project. (shrink)

Cognition is commonly taken to be computational manipulation of representations. These representations are assumed to be digital, but it is not usually specified what that means and what relevance it has for the theory. I propose a specification for being a digital state in a digital system, especially a digital computational system. The specification shows that identification of digital states requires functional directedness, either for someone or for the system of which it is a part. In the case or digital (...) representations, to be a token of a representational type, where the function of the type is to represent. [An earlier version of this paper was discussed in the web-conference "Interdisciplines" https://web.archive.org/web/20100221125700/http://www.interdisciplines.org/adaptation/papers/7 ]. (shrink)

This paper revisits one of the first models of analog computation, the General Purpose Analog Computer . In particular, we restrict our attention to the improved model presented in [11] and we show that it can be further refined. With this we prove the following: the previous model can be simplified; it admits extensions having close connections with the class of smooth continuous time dynamical systems. As a consequence, we conclude that some of these extensions achieve Turing universality. Finally, it (...) is shown that if we introduce a new notion of computability for the GPAC, based on ideas from computable analysis, then one can compute transcendentally transcendental functions such as the Gamma function or Riemann's Zeta function. (shrink)

The question ‘What is computation?’ might seem a trivial one to many, but this is far from being in consensus in philosophy of mind, cognitive science and even in physics. The lack of consensus leads to some interesting, yet contentious, claims, such as that cognition or even the universe is computational. Some have argued, though, that computation is a subjective phenomenon: whether or not a physical system is computational, and if so, which computation it performs, is entirely a matter of (...) an observer choosing to view it as such. According to one view, which we dub bold anti-realist pancomputationalism, every physical object computes every computer program. According to another, more modest view, some computational systems can be ascribed multiple computational descriptions. We argue that the first view is misguided, and that the second view need not entail observer-relativity of computation. At least to a large extent, computation is an objective phenomenon. Construed as a form of information processing, we argue that information-processing considerations determine what type of computation takes place in physical systems. (shrink)

The analog vs. digital distinction is frequently used in computer science, computer technology and elsewhere. However, its precise nature is more elusive than might be expected. This dissertation defines a set of problems hidden within the conventions of ordinary and technical language, and suggests solutions to them. ;Chapter 1 examines ordinary language uses of the analog-digital distinction. Chapter 2 considers its use in technical contexts. There are two main ways of making the distinction that appear in both of the opening (...) chapters. The most common is to take it to be equivalent to that between the continuous and the discrete. These two terms are typically used to differentiate either a physical medium, such as the continuous grooves of a vinyl record or the discrete bubbles in a compact disc, or some form of notation by means of which a phenomenon is represented. Systems of discrete characters, such as alphabets, provide means of digital representation, whereas diagrams and figures operate as means of analog representation. It has frequently been argued that an analog representation relies on some form of natural resemblance to what is being represented. As the word suggests, analogy, i.e., a similarity of structure, is the prime candidate to explain this kind of resemblance. In contrast, digital representation requires a conventional means of correlation, which in turn requires a translation manual, to establish the relationship between the notation and what is represented. ;Chapter 3 shows that the various distinctions considered in the previous chapters have consequences for arguments in the philosophy of mind. ;Chapter 4 presents a literature survey. Chapter 5 extends the picture developed in the opening chapters beyond the philosophy of mind. ;The importance of this dissertation lies in its response to a question basic to both philosophy of mind and philosophy of language: how do representations work? Traditional theories of representation have tended to be functional in their descriptions of representations. By contrast, recent developments in cognitive science have offered structural descriptions. Clearly, these two modes parallel the analog-digital distinction. This dissertation, in clarifying the distinction, provides important clues for bridging these two contemporary philosophical movements. (shrink)

The ‘received view’ of the analog–digital distinction holds that analog representations are continuous while digital representations are discrete. In this paper I first provide support for the received view by showing how it (1) emerges from the theory of computation, and (2) explains engineering practices. Second, I critically assess several recently offered alternatives, arguing that to the degree they are justified they demonstrate not that the received view is incorrect, but rather that distinct senses of the terms have become entrenched (...) specific fields, perhaps most notably in the cognitive psychology of mental imagery. (shrink)

Without a proper restriction on mappings, virtually any system could be seen as implementing any computation. That would not allow characterization of systems in terms of implemented computations and is not compatible with a computationalist philosophy of mind. Information-based criteria for independence of substates within structured states are proposed as a solution. Objections to the use of requirements for transitions in counterfactual states are addressed, in part using the partial-brain argument as a general counterargument to neural replacement arguments.

We address an argument by Floridi (Synthese 168(1):151–178, 2009; 2011a), to the effect that digital and analogue are not features of reality, only of modes of presentation of reality. One can therefore have an informational ontology, like Floridi’s Informational Structural Realism, without commitment to a supposedly digital or analogue world. After introducing the topic in Sect. 1, in Sect. 2 we explain what the proposition expressed by the title of our paper means. In Sect. 3, we describe Floridi’s argument. In (...) the following three sections, we raise three difficulties for it, (i) an objection from intuitions: Floridi’s view is not supported by the intuitions embedded in the scientific views he exploits (Sect. 4); (ii) an objection from mereology: the view is incompatible with the world’s having parts (Sect. 5); (iii) an objection from counting: the view entails that the question of how many things there are doesn’t make sense (Sect. 6). In Sect. 7, we outline two possible ways out for Floridi’s position. Such ways out involve tampering with the logical properties of identity, and this may be bothersome enough. Thus, Floridi’s modus ponens will be our (and most ontologists’) modus tollens. (shrink)

Chaotic dynamics can be related to analog computation. A possibility of electronically implementing the chaos -driven contracting system in the target article is explored with an analog electronic circuit with inevitable noise from the viewpoint of analog computation with chaotic neurons.

What is nontrivial digital computation? It is the processing of discrete data through discrete state transitions in accordance with finite instructional information. The motivation for our account is that many previous attempts to answer this question are inadequate, and also that this account accords with the common intuition that digital computation is a type of information processing. We use the notion of reachability in a graph to defend this characterization in memory-based systems and underscore the importance of instructional information for (...) digital computation. We argue that our account evaluates positively against adequacy criteria for accounts of computation. (shrink)

Ceruzzi pens a history of computing from the development of the first electronic digital computer to the Web and dot-com crash.

We distinguish scanning switches, which only enumerate states, from function switches which transform input states into output states. For the latter we introduce a logical network symbolism. Our history of early computer switching begins with the suggestions of Ramon Lull and Gottfried Leibniz, surveys the evolution of mechanical scanning switches and the first mechanical function switches, and then describes the first electromechanical function switches. The main themes of the present paper are that William S. Jevons built the first substantial function (...) switch (his logical piano), and that his work led to the design by Allan Marquand of the first substantial electromechanical function switch, as well as to Charles S. Peirce's idea for an electrical general-purpose programmable computer. These events all occurred fifty years before the first general-purpose programmable computers were constructed (in the 1940's), but they had no influence. (shrink)

It is common in cognitive science to equate computation (and in particular digital computation) with information processing. Yet, it is hard to find a comprehensive explicit account of concrete digital computation in information processing terms. An information processing account seems like a natural candidate to explain digital computation. But when ‘information’ comes under scrutiny, this account becomes a less obvious candidate. Four interpretations of information are examined here as the basis for an information processing account of digital computation, namely Shannon (...) information, algorithmic information, factual information and instructional information. I argue that any plausible account of concrete computation has to be capable of explaining at least the three key algorithmic notions of input, output and procedures. Whist algorithmic information fares better than Shannon information, the most plausible candidate for an information processing account is instructional information. (shrink)

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)

This paper investigates the view that digital hypercomputing is a good reason for rejection or re-interpretation of the Church-Turing thesis. After suggestion that such re-interpretation is historically problematic and often involves attack on a straw man (the ‘maximality thesis’), it discusses proposals for digital hypercomputing with Zeno-machines , i.e. computing machines that compute an infinite number of computing steps in finite time, thus performing supertasks. It argues that effective computing with Zeno-machines falls into a dilemma: either they are specified such (...) that they do not have output states, or they are specified such that they do have output states, but involve contradiction. Repairs though non-effective methods or special rules for semi-decidable problems are sought, but not found. The paper concludes that hypercomputing supertasks are impossible in the actual world and thus no reason for rejection of the Church-Turing thesis in its traditional interpretation. (shrink)

We review the pros and cons of analog and digital computation. We propose that computation that is most efficient in its use of resources is neither analog computation nor digital computation but, rather, a mixture of the two forms. For maximum efficiency, the information and information-processing resources of the hybrid form must be distributed over many wires, with an optimal signal-to-noise ratio per wire. Our results suggest that it is likely that the brain computes in a hybrid fashion and that (...) an underappreciated and important reason for the efficiency of the human brain, which consumes only 12 W, is the hybrid and distributed nature of its architecture. (shrink)

. . . Unlike Dewey, he has provided detailed incisive argumentation, and has shown just where the dogmas and dualisms break down." -- Richard Rorty, The Yale Review.

Representation is central to contemporary theorizing about the mind/brain. But the nature of representation--both in the mind/brain and more generally--is a source of ongoing controversy. One way of categorizing representational types is to distinguish between the analog and the digital: the received view is that analog representations vary smoothly, while digital representations vary in a step-wise manner. I argue that this characterization is inadequate to account for the ways in which representation is used in cognitive science; in its place, I (...) suggest an alternative taxonomy. I will defend and extend David Lewis's account of analog and digital representation, distinguishing analog from continuous representation, as well as digital from discrete representation. I will argue that the distinctions available in this four-fold account accord with representational features of theoretical interest in cognitive science more usefully than the received analog/digital dichotomy. (shrink)

It is fairly well-known that certain hard computational problems (that is, 'difficult' problems for a digital processor to solve) can in fact be solved much more easily with an analog machine. This raises questions about the true nature of the distinction between analog and digital computation (if such a distinction exists). I try to analyze the source of the observed difference in terms of (1) expanding parallelism and (2) more generally, infinite-state Turing machines. The issue of discreteness vs continuity will (...) also be touched upon, although it is not so important for analyzing these particular problems. (shrink)

Since the mid-twentieth century, the concept of the Turing machine has dominated thought about effective procedures. This paper presents an alternative to Turing's analysis; it unifies, refines, and extends my earlier work on this topic. I show that Turing machines cannot live up to their billing as paragons of effective procedure; at best, they may be said to provide us with mere procedure schemas. I argue that the concept of an effective procedure crucially depends upon distinguishing procedures as definite courses (...) of action(- types) from the particular courses of action(-tokens) that actually instantiate them and the causal processes and/or interpretations that ultimately make them effective. On my analysis, effectiveness is not just a matter of logical form; `content' matters. The analysis I provide has the advantage of applying to ordinary, everyday procedures such as recipes and methods, as well as the more refined procedures of mathematics and computer science. It also has the virtue of making better sense of the physical possibilities for hypercomputation than the received view and its extensions, e.g. Turing's o-machines, accelerating machines. (shrink)

Accelerated Turing machines are Turing machines that perform tasks commonly regarded as impossible, such as computing the halting function. The existence of these notional machines has obvious implications concerning the theoretical limits of computability.

The following paper presents a characterization of three distinctions fundamental to computationalism, viz., the distinction between analog and digital machines, representation and nonrepresentation-using systems, and direct and indirect perceptual processes. Each distinction is shown to rest on nothing more than the methodological principles which justify the explanatory framework of the special sciences.