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:
46 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. John R. Anderson & Christian Lebiere (2003). The Newell Test for a Theory of Cognition. Behavioral and Brain Sciences 26 (5):587-601.
    Newell (1980; 1990) proposed that cognitive theories be developed in an effort to satisfy multiple criteria and to avoid theoretical myopia. He provided two overlapping lists of 13 criteria that the human cognitive architecture would have to satisfy in order to be functional. We have distilled these into 12 criteria: flexible behavior, real-time performance, adaptive behavior, vast knowledge base, dynamic behavior, knowledge integration, natural language, learning, development, evolution, and brain realization. There would be greater theoretical progress if we evaluated theories (...)
    Remove from this list | Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  3. Peter M. Asaro (2001). Hans Moravec, Robot. Mere Machine to Transcendent Mind, New York, NY: Oxford University Press, Inc., 1999, IX + 227 Pp., $25.00 (Cloth), ISBN 0-19-511630-. [REVIEW] Minds and Machines 11 (1):143-147.
  4. William Bechtel & Adele Abrahamsen (2010). Dynamic Mechanistic Explanation: Computational Modeling of Circadian Rhythms as an Exemplar for Cognitive Science. Studies in History and Philosophy of Science Part A 41 (3):321-333.
    Two widely accepted assumptions within cognitive science are that (1) the goal is to understand the mechanisms responsible for cognitive performances and (2) computational modeling is a major tool for understanding these mechanisms. The particular approaches to computational modeling adopted in cognitive science, moreover, have significantly affected the way in which cognitive mechanisms are understood. Unable to employ some of the more common methods for conducting research on mechanisms, cognitive scientists’ guiding ideas about mechanism have developed in conjunction with their (...)
    Remove from this list | Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  5. 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  
  6. 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  
  7. 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  
  8. 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  
  9. 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  
  10. Cristian Cocos (2002). Computational Processes: A Reply to Chalmers and Copeland. SATS: Northern European Journal of Philosophy 3 (2):25-49.
    Remove from this list | Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  11. 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  
  12. 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  
  13. 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  
  14. 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  
  15. 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  
  16. 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  
  17. Amnon Eden (2011). Some Philosophical Issues in Computer Science. Minds and Machines 21 (2):123-133.
    The essays included in the special issue dedicated to the philosophy of computer science examine new philosophical questions that arise from reflection upon conceptual issues in computer science and the insights such an enquiry provides into ongoing philosophical debates.
    Remove from this list | Direct download (16 more)  
     
    My bibliography  
     
    Export citation  
  18. Amnon H. Eden (2007). Three Paradigms of Computer Science. Minds and Machines 17 (2):135-167.
    We examine the philosophical disputes among computer scientists concerning methodological, ontological, and epistemological questions: Is computer science a branch of mathematics, an engineering discipline, or a natural science? Should knowledge about the behaviour of programs proceed deductively or empirically? Are computer programs on a par with mathematical objects, with mere data, or with mental processes? We conclude that distinct positions taken in regard to these questions emanate from distinct sets of received beliefs or paradigms within the discipline: – The rationalist (...)
    Remove from this list | Direct download (15 more)  
     
    My bibliography  
     
    Export citation  
  19. 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  
  20. 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  
  21. 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  
  22. Stefan Gruner (2013). Eric Winsberg: Science in the Age of Computer Simulation. [REVIEW] Minds and Machines 23 (2):251-254.
  23. 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  
  24. Roman Stanisław Ingarden (2002). Open Systems and Consciousness: A Philosophical Discussion. Open Systems and Information Dynamics 9:125-151.
  25. John Kadvany (2010). Indistinguishable From Magic: Computation is Cognitive Technology. [REVIEW] Minds and Machines 20 (1):119-143.
    Abstract This paper explains how mathematical computation can be constructed from weaker recursive patterns typical of natural languages. A thought experiment is used to describe the formalization of computational rules, or arithmetical axioms, using only orally-based natural language capabilities, and motivated by two accomplishments of ancient Indian mathematics and linguistics. One accomplishment is the expression of positional value using versified Sanskrit number words in addition to orthodox inscribed numerals. The second is Panini’s invention, around<br>the fifth century BCE, of a formal (...)
    Remove from this list | Direct download (10 more)  
     
    My bibliography  
     
    Export citation  
  26. 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  
  27. 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  
  28. 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  
  29. 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  
  30. Nenad Miscevic (1996). Computationalism and the Kripke-Wittgenstein Paradox. Proceedings of the Aristotelian Society 96:215-29.
  31. 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  
  32. 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  
  33. Christopher Mole (2013). Review of Probably Approximately Correct. [REVIEW] TLS: The Times Literary Supplement 5772:32.
    Remove from this list | Direct download  
     
    My bibliography  
     
    Export citation  
  34. Ivan Moura (2006). A Model of Agent Consciousness and its Implementation. Neurocomputing 69 (16-18):1984-1995.
  35. 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  
  36. 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  
  37. 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  
  38. Itamar Pitowsky, From Logic to Physics: How the Meaning of Computation Changed Over Time.
    The intuition guiding the de…nition of computation has shifted over time, a process that is re‡ected in the changing formulations of the Church-Turing thesis. The theory of computation began with logic and gradually moved to the capacity of …nite automata. Consequently, modern computer models rely on general physical principles, with quantum computers representing the extreme case. The paper discusses this development, and the challenges to the Church-Turing thesis in its physical form, in particular, Kieu’s quantum computer and relativistic hyper-computation. Finally, (...)
    Remove from this list |
    Translate to English
    | Direct download  
     
    My bibliography  
     
    Export citation  
  39. 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  
  40. Oron Shagrir (2002). Effective Computation by Humans and Machines. Minds and Machines 12 (2):221-240.
    There is an intensive discussion nowadays about the meaning of effective computability, with implications to the status and provability of the Church–Turing Thesis (CTT). I begin by reviewing what has become the dominant account of the way Turing and Church viewed, in 1936, effective computability. According to this account, to which I refer as the Gandy–Sieg account, Turing and Church aimed to characterize the functions that can be computed by a human computer. In addition, Turing provided a highly convincing argument (...)
    Remove from this list | Direct download (18 more)  
     
    My bibliography  
     
    Export citation  
  41. Aaron Sloman, What Are Virtual Machines? Are They Real?
  42. 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  
  43. 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  
  44. 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  
  45. 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  
  46. Hector Zenil, Fernando Soler-Toscano & Joost J. Joosten (2012). Empirical Encounters with Computational Irreducibility and Unpredictability. Minds and Machines 22 (3):149-165.
    The paper presents an exploration of conceptual issues that have arisen in the course of investigating speed-up and slowdown phenomena in small Turing machines, in particular results of a test that may spur experimental approaches to the notion of computational irreducibility. The test involves a systematic attempt to outrun the computation of a large number of small Turing machines (3 and 4 state, 2 symbol) by means of integer sequence prediction using a specialized function for that purpose. The experiment prompts (...)
    Remove from this list | Direct download (7 more)  
     
    My bibliography  
     
    Export citation