About this topic
Summary The theory of computation is a mathematical theory about the properties of abstract computational objects, such as algorithms and Turing machines. They are abstract in the sense that they ignore or leave out considerations about by features of physical implementations, such as finite memory.  In contrast, computations are done by physical systems: concrete machines made of silicon and metal, or brains made of biological materials, can run algorithms or implement Turing machines. This area is concerned with questions about how the abstract objects that are in the purview of the theory of computation relate to physical systems.
Key works The relationship between abstract computation and physical systems such as brains is a central issue in philosophy of mind, particularly given the rise of computational functionalism as a foundation for the study of the mind.  Here the work of Chalmers 1996 provides a good starting point for bridging the theory of computation with theories of physical systems by means of animplementation relation. 
Introductions A good introduction is Piccinini 2010
  Show all references
Related categories
Siblings:
35 found
Search inside:
(import / add options)   Sort by:
  1. W. Aitken & J. A. Barrett (2010). A Note on the Physical Possibility of Transfinite Computation. British Journal for the Philosophy of Science 61 (4):867-874.
    In this note, we consider constraints on the physical possibility of transfinite Turing machines that arise from how one models the continuous structure of space and time in one's best physical theories. We conclude by suggesting a version of Church's thesis appropriate as an upper bound for physical computation given how space and time are modeled on our current physical theories.
    Remove from this list | Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  2. Francesco Berto & Jacopo Tagliabue (2014). The World is Either Digital or Analogue. Synthese 191 (3):481-497.
    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 (...)
    Remove from this list | Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  3. Francesco Berto & Jacopo Tagliabue (2012). Cellular Automata. Stanford Encyclopedia of Philosophy.
    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 (...)
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  4. Andrew Boucher (1997). Parallel Machines. Minds and Machines 7 (4):543-551.
    Because it is time-dependent, parallel computation is fundamentally different from sequential computation. Parallel programs are non-deterministic and are not effective procedures. Given the brain operates in parallel, this casts doubt on AI's attempt to make sequential computers intelligent.
    Remove from this list | Direct download (18 more)  
     
    My bibliography  
     
    Export citation  
  5. Paul Bohan Broderick (2004). On Communication and Computation. Minds and Machines 14 (1):1-19.
    Comparing technical notions of communication and computation leads to a surprising result, these notions are often not conceptually distinguishable. This paper will show how the two notions may fail to be clearly distinguished from each other. The most famous models of computation and communication, Turing Machines and (Shannon-style) information sources, are considered. The most significant difference lies in the types of state-transitions allowed in each sort of model. This difference does not correspond to the difference that would be expected after (...)
    Remove from this list | Direct download (16 more)  
     
    My bibliography  
     
    Export citation  
  6. Carol E. Cleland (2002). On Effective Procedures. Minds and Machines 12 (2):159-179.
    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 (...)
    Remove from this list | Direct download (17 more)  
     
    My bibliography  
     
    Export citation  
  7. Cristian Cocos (2002). Computational Processes: A Reply to Chalmers and Copeland. SATS 3 (2):25-49.
    Remove from this list | Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  8. B. Jack Copeland (2002). Accelerating Turing Machines. Minds and Machines 12 (2):281-300.
    Accelerating Turing machines are Turing machines of a sort able to perform tasks that are commonly regarded as impossible for Turing machines. For example, they can determine whether or not the decimal representation of contains n consecutive 7s, for any n; solve the Turing-machine halting problem; and decide the predicate calculus. Are accelerating Turing machines, then, logically impossible devices? I argue that they are not. There are implications concerning the nature of effective procedures and the theoretical limits of computability. Contrary (...)
    Remove from this list | Direct download (17 more)  
     
    My bibliography  
     
    Export citation  
  9. B. Jack Copeland (2002). Hypercomputation. Minds and Machines 12 (4):461-502.
    A survey of the field of hypercomputation, including discussion of a variety of objections.
    Remove from this list | Direct download (16 more)  
     
    My bibliography  
     
    Export citation  
  10. B. Jack Copeland (1996). What is Computation? Synthese 108 (3):335-59.
    To compute is to execute an algorithm. More precisely, to say that a device or organ computes is to say that there exists a modelling relationship of a certain kind between it and a formal specification of an algorithm and supporting architecture. The key issue is to delimit the phrase of a certain kind. I call this the problem of distinguishing between standard and nonstandard models of computation. The successful drawing of this distinction guards Turing's 1936 analysis of computation against (...)
    Remove from this list | Direct download (8 more)  
     
    My bibliography  
     
    Export citation  
  11. B. Jack Copeland & Oron Shagrir (2007). Physical Computation: How General Are Gandy's Principles for Mechanisms? [REVIEW] Minds and Machines 17 (2):217-231.
    What are the limits of physical computation? In his ‘Church’s Thesis and Principles for Mechanisms’, Turing’s student Robin Gandy proved that any machine satisfying four idealised physical ‘principles’ is equivalent to some Turing machine. Gandy’s four principles in effect define a class of computing machines (‘Gandy machines’). Our question is: What is the relationship of this class to the class of all (ideal) physical computing machines? Gandy himself suggests that the relationship is identity. We do not share this view. We (...)
    Remove from this list | Direct download (15 more)  
     
    My bibliography  
     
    Export citation  
  12. Jack Copeland, Even Turing Machines Can Compute Uncomputable Functions.
    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.
    Remove from this list |
     
    My bibliography  
     
    Export citation  
  13. Jack Copeland (1997). The Broad Conception of Computation. American Behavioral Scientist 40 (6):690-716.
    A myth has arisen concerning Turing's paper of 1936, namely that Turing set forth a fundamental principle concerning the limits of what can be computed by machine - a myth that has passed into cognitive science and the philosophy of mind, to wide and pernicious effect. This supposed principle, sometimes incorrectly termed the 'Church-Turing thesis', is the claim that the class of functions that can be computed by machines is identical to the class of functions that can be computed by (...)
    Remove from this list | Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  14. Ronald P. Endicott (1996). Searle, Syntax, and Observer-Relativity. Canadian Journal of Philosophy 26 (1):101-22.
    I critically examine some provocative arguments that John Searle presents in his book The Rediscovery of Mind to support the claim that the syntactic states of a classical computational system are "observer relative" or "mind dependent" or otherwise less than fully and objectively real. I begin by explaining how this claim differs from Searle's earlier and more well-known claim that the physical states of a machine, including the syntactic states, are insufficient to determine its semantics. In contrast, his more recent (...)
    Remove from this list | Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  15. Nir Fresco, Concrete Digital Computation: Competing Accounts and its Role in Cognitive Science.
    There are currently considerable confusion and disarray about just how we should view computationalism, connectionism and dynamicism as explanatory frameworks in cognitive science. A key source of this ongoing conflict among the central paradigms in cognitive science is an equivocation on the notion of computation simpliciter. ‘Computation’ is construed differently by computationalism, connectionism, dynamicism and computational neuroscience. I claim that these central paradigms, properly understood, can contribute to an integrated cognitive science. Yet, before this claim can be defended, a better (...)
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  16. Nir Fresco & Marty J. Wolf (2014). The Instructional Information Processing Account of Digital Computation. Synthese 191 (7):1469-1492.
    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 (...)
    Remove from this list | Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  17. Amit Hagar, To Balance a Pencil on its Tip: On the Passive Approach to Quantum Error Correction.
    Quantum computers are hypothetical quantum information processing (QIP) devices that allow one to store, manipulate, and extract information while harnessing quantum physics to solve various computational problems and do so putatively more efficiently than any known classical counterpart. Despite many ‘proofs of concept’ (Aharonov and Ben–Or 1996; Knill and Laflamme 1996; Knill et al. 1996; Knill et al. 1998) the key obstacle in realizing these powerful machines remains their scalability and susceptibility to noise: almost three decades after their conceptions, experimentalists (...)
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  18. Roman Stanisław Ingarden (2002). Open Systems and Consciousness: A Philosophical Discussion. Open Systems and Information Dynamics 9:125-151.
  19. David Kirsh (1992). Architectures of Intelligent Systems. Exploring Brain Functions.
    Theories of intelligence can be of use to neuroscientists if they: 1. Provide illuminating suggestions about the functional architecture of neural systems; 2. Suggest specific models of processing that neural circuits might implement. The objective of our session was to stand back and consider the prospects for this interdisciplinary exchange.
    Remove from this list |
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  20. Ignazio Licata & Ammar Sakaji (eds.) (2008). Physics of Emergence and Organization. World Scientific.
    This book is a state-of-the-art review on the Physics of Emergence. Foreword v Gregory J. Chaitin Preface vii Ignazio Licata Emergence and Computation at the Edge of Classical and Quantum Systems 1 Ignazio Licata Gauge Generalized Principle for Complex Systems 27 Germano Resconi Undoing Quantum Measurement: Novel Twists to the Physical Account of Time 61 Avshalom C. Elitzur and Shahar Dolev Process Physics: Quantum Theories as Models of Complexity 77 Kirsty Kitto A Cross-disciplinary Framework for the Description of Contextually Mediated (...)
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  21. Jacques Mallah, The Many Computations Interpretation (MCI) of Quantum Mechanics.
    Computationalism provides a framework for understanding how a mathematically describable physical world could give rise to conscious observations without the need for dualism. A criterion is proposed for the implementation of computations by physical systems, which has been a problem for computationalism. Together with an independence criterion for implementations this would allow, in principle, prediction of probabilities for various observations based on counting implementations. Applied to quantum mechanics, this results in a Many Computations Interpretation (MCI), which is an explicit form (...)
    Remove from this list | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  22. Jacques Mallah (forthcoming). Structure and Dynamics in Implementation of Computations. In Yasemin J. Erden (ed.), Proceedings of the 7th AISB Symposium on Computing and Philosophy:. AISB.
    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.
    Remove from this list | Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  23. Nenad Miscevic (1996). Computationalism and the Kripke-Wittgenstein Paradox. Proceedings of the Aristotelian Society 96:215-29.
  24. Marcin Miłkowski (2009). Is Evolution Algorithmic? Minds and Machines 19 (4):465-475.
    In Darwin’s Dangerous Idea, Daniel Dennett claims that evolution is algorithmic. On Dennett’s analysis, evolutionary processes are trivially algorithmic because he assumes that all natural processes are algorithmic. I will argue that there are more robust ways to understand algorithmic processes that make the claim that evolution is algorithmic empirical and not conceptual. While laws of nature can be seen as compression algorithms of information about the world, it does not follow logically that they are implemented as algorithms by physical (...)
    Remove from this list | Direct download (18 more)  
     
    My bibliography  
     
    Export citation  
  25. Marcin Miłkowski (2007). Is Computationalism Trivial? In Gordana Dodig Crnkovic & Susan Stuart (eds.), Computation, Information, Cognition: The Nexus and the Liminal. Cambridge Scholars Press.
    In this paper, I want to deal with the triviality threat to computationalism. On one hand, the controversial and vague claim that cognition involves computation is still denied. On the other, contemporary physicists and philosophers alike claim that all physical processes are indeed computational or algorithmic. This claim would justify the computationalism claim by making it utterly trivial. I will show that even if these two claims were true, computationalism would not have to be trivial.
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  26. Ivan Moura (2006). A Model of Agent Consciousness and its Implementation. Neurocomputing 69 (16-18):1984-1995.
  27. Matthew W. Parker (2003). Three Concepts of Decidability for General Subsets of Uncountable Spaces. Theoretical Computer Science 351 (1):2-13.
    There is no uniquely standard concept of an effectively decidable set of real numbers or real n-tuples. Here we consider three notions: decidability up to measure zero [M.W. Parker, Undecidability in Rn: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382], which we abbreviate d.m.z.; recursive approximability [or r.a.; K.-I. Ko, Complexity Theory of Real Functions, Birkhäuser, Boston, 1991]; and decidability ignoring boundaries [d.i.b.; W.C. Myrvold, The decision problem for entanglement, in: R.S. (...)
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  28. Gualtiero Piccinini (2008). Computation Without Representation. Philosophical Studies 137 (2):205-241.
    The received view is that computational states are individuated at least in part by their semantic properties. I offer an alternative, according to which computational states are individuated by their functional properties. Functional properties are specified by a mechanistic explanation without appealing to any semantic properties. The primary purpose of this paper is to formulate the alternative view of computational individuation, point out that it supports a robust notion of computational explanation, and defend it on the grounds of how computational (...)
    Remove from this list | Direct download (11 more)  
     
    My bibliography  
     
    Export citation  
  29. Gualtiero Piccinini (2008). Some Neural Networks Compute, Others Don't. Neural Networks 21 (2-3):311-321.
    I address whether neural networks perform computations in the sense of computability theory and computer science. I explicate and defend
    the following theses. (1) Many neural networks compute—they perform computations. (2) Some neural networks compute in a classical way.
    Ordinary digital computers, which are very large networks of logic gates, belong in this class of neural networks. (3) Other neural networks
    compute in a non-classical way. (4) Yet other neural networks do not perform computations. Brains may well fall into this last class.
    Remove from this list |
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  30. Paul Schweizer (2002). Consciousness and Computation. Minds and Machines 12 (1):143-144.
    Remove from this list | Direct download (14 more)  
     
    My bibliography  
     
    Export citation  
  31. Aaron Sloman, What Are Virtual Machines? Are They Real?
  32. Edward P. Stabler (1987). Kripke on Functionalism and Automata. Synthese 70 (January):1-22.
    Saul Kripke has proposed an argument to show that there is a serious problem with many computational accounts of physical systems and with functionalist theories in the philosophy of mind. The problem with computational accounts is roughly that they provide no noncircular way to maintain that any particular function with an infinite domain is realized by any physical system, and functionalism has the similar problem because of the character of the functional systems that are supposed to be realized by organisms. (...)
    Remove from this list | Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  33. Eric Steinhart (2003). Supermachines and Superminds. Minds and Machines 13 (1):155-186.
    If the computational theory of mind is right, then minds are realized by machines. There is an ordered complexity hierarchy of machines. Some finite machines realize finitely complex minds; some Turing machines realize potentially infinitely complex minds. There are many logically possible machines whose powers exceed the Church–Turing limit (e.g. accelerating Turing machines). Some of these supermachines realize superminds. Superminds perform cognitive supertasks. Their thoughts are formed in infinitary languages. They perceive and manipulate the infinite detail of fractal objects. They (...)
    Remove from this list | Direct download (12 more)  
     
    My bibliography  
     
    Export citation  
  34. Peter Suber (1988). What is Software? Journal of Speculative Philosophy 2 (2):89-119.
    In defining the concept of software, I try at first to distinguish software from data, noise, and abstract patterns of information with no material embodiment. But serious objections prevent any of these distinctions from remaining stable. The strong thesis that software is pattern per se, or syntactical form, is initially refined to overcome obvious difficulties; but further arguments show that the refinements are trivial and that the strong thesis is defensible.
    Remove from this list | Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  35. Hector Zenil, A Computable Universe: Understanding and Exploring Nature as Computation.
    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 (...)
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation