Switch to: References

Add citations

You must login to add citations.
  1. Against Structuralist Theories of Computational Implementation.Michael Rescorla - 2013 - British Journal for the Philosophy of Science 64 (4):681-707.
    Under what conditions does a physical system implement or realize a computation? Structuralism about computational implementation, espoused by Chalmers and others, holds that a physical system realizes a computation just in case the system instantiates a pattern of causal organization isomorphic to the computation’s formal structure. I argue against structuralism through counter-examples drawn from computer science. On my opposing view, computational implementation sometimes requires instantiating semantic properties that outstrip any relevant pattern of causal organization. In developing my argument, I defend (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  • Counterpossibles in Science: The Case of Relative Computability.Matthias Jenny - 2018 - Noûs 52 (3):530-560.
    I develop a theory of counterfactuals about relative computability, i.e. counterfactuals such as 'If the validity problem were algorithmically decidable, then the halting problem would also be algorithmically decidable,' which is true, and 'If the validity problem were algorithmically decidable, then arithmetical truth would also be algorithmically decidable,' which is false. These counterfactuals are counterpossibles, i.e. they have metaphysically impossible antecedents. They thus pose a challenge to the orthodoxy about counterfactuals, which would treat them as uniformly true. What’s more, I (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   24 citations  
  • On the Invariance of Gödel’s Second Theorem with Regard to Numberings.Balthasar Grabmayr - forthcoming - Review of Symbolic Logic:1-34.
    The prevalent interpretation of Gödel’s Second Theorem states that a sufficiently adequate and consistent theory does not prove its consistency. It is however not entirely clear how to justify this informal reading, as the formulation of the underlying mathematical theorem depends on several arbitrary formalisation choices. In this paper I examine the theorem’s dependency regarding Gödel numberings. I introduce deviant numberings, yielding provability predicates satisfying Löb’s conditions, which result in provable consistency sentences. According to the main result of this paper (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • Computers Are Syntax All the Way Down: Reply to Bozşahin.William J. Rapaport - 2019 - Minds and Machines 29 (2):227-237.
    A response to a recent critique by Cem Bozşahin of the theory of syntactic semantics as it applies to Helen Keller, and some applications of the theory to the philosophy of computer science.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • The Dependence of Computability on Numerical Notations.Ethan Brauer - 2020 - Synthese 198 (11):10485-10511.
    Which function is computed by a Turing machine will depend on how the symbols it manipulates are interpreted. Further, by invoking bizarre systems of notation it is easy to define Turing machines that compute textbook examples of uncomputable functions, such as the solution to the decision problem for first-order logic. Thus, the distinction between computable and uncomputable functions depends on the system of notation used. This raises the question: which systems of notation are the relevant ones for determining whether a (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • Implicit and Explicit Examples of the Phenomenon of Deviant Encodings.Paula Quinon - 2020 - Studies in Logic, Grammar and Rhetoric 63 (1):53-67.
    The core of the problem discussed in this paper is the following: the Church-Turing Thesis states that Turing Machines formally explicate the intuitive concept of computability. The description of Turing Machines requires description of the notation used for the input and for the output. Providing a general definition of notations acceptable in the process of computations causes problems. This is because a notation, or an encoding suitable for a computation, has to be computable. Yet, using the concept of computation, in (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Syntax, Semantics, and Computer Programs.William J. Rapaport - 2020 - Philosophy and Technology 33 (2):309-321.
    Turner argues that computer programs must have purposes, that implementation is not a kind of semantics, and that computers might need to understand what they do. I respectfully disagree: Computer programs need not have purposes, implementation is a kind of semantic interpretation, and neither human computers nor computing machines need to understand what they do.
    Direct download (4 more)  
    Translate
     
     
    Export citation  
     
    Bookmark   2 citations  
  • A Natural Axiomatization of Computability and Proof of Church’s Thesis.Nachum Dershowitz & Yuri Gurevich - 2008 - Bulletin of Symbolic Logic 14 (3):299-350.
    Church's Thesis asserts that the only numeric functions that can be calculated by effective means are the recursive ones, which are the same, extensionally, as the Turing-computable numeric functions. The Abstract State Machine Theorem states that every classical algorithm is behaviorally equivalent to an abstract state machine. This theorem presupposes three natural postulates about algorithmic computation. Here, we show that augmenting those postulates with an additional requirement regarding basic operations gives a natural axiomatization of computability and a proof of Church's (...)
    Direct download (12 more)  
     
    Export citation  
     
    Bookmark   17 citations  
  • The Physical Church–Turing Thesis: Modest or Bold?Gualtiero Piccinini - 2011 - British Journal for the Philosophy of Science 62 (4):733-769.
    This article defends a modest version of the Physical Church-Turing thesis (CT). Following an established recent trend, I distinguish between what I call Mathematical CT—the thesis supported by the original arguments for CT—and Physical CT. I then distinguish between bold formulations of Physical CT, according to which any physical process—anything doable by a physical system—is computable by a Turing machine, and modest formulations, according to which any function that is computable by a physical system is computable by a Turing machine. (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   20 citations  
  • The Philosophy of Computer Science.Raymond Turner - 2013 - Stanford Encyclopedia of Philosophy.
  • Computing with Numbers and Other Non-Syntactic Things: De Re Knowledge of Abstract Objects.Stewart Shapiro - 2017 - Philosophia Mathematica 25 (2):268-281.
    ABSTRACT Michael Rescorla has argued that it makes sense to compute directly with numbers, and he faulted Turing for not giving an analysis of number-theoretic computability. However, in line with a later paper of his, it only makes sense to compute directly with syntactic entities, such as strings on a given alphabet. Computing with numbers goes via notation. This raises broader issues involving de re propositional attitudes towards numbers and other non-syntactic abstract entities.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  • The Representational Foundations of Computation.Michael Rescorla - 2015 - Philosophia Mathematica 23 (3):338-366.
    Turing computation over a non-linguistic domain presupposes a notation for the domain. Accordingly, computability theory studies notations for various non-linguistic domains. It illuminates how different ways of representing a domain support different finite mechanical procedures over that domain. Formal definitions and theorems yield a principled classification of notations based upon their computational properties. To understand computability theory, we must recognize that representation is a key target of mathematical inquiry. We must also recognize that computability theory is an intensional enterprise: it (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   13 citations  
  • Deviant Encodings and Turing’s Analysis of Computability.B. Jack Copeland & Diane Proudfoot - 2010 - Studies in History and Philosophy of Science Part A 41 (3):247-252.
    Turing’s analysis of computability has recently been challenged; it is claimed that it is circular to analyse the intuitive concept of numerical computability in terms of the Turing machine. This claim threatens the view, canonical in mathematics and cognitive science, that the concept of a systematic procedure or algorithm is to be explicated by reference to the capacities of Turing machines. We defend Turing’s analysis against the challenge of ‘deviant encodings’.Keywords: Systematic procedure; Turing machine; Church–Turing thesis; Deviant encoding; Acceptable encoding; (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   8 citations