Switch to: References

Citations of:

Proving church's thesis

Philosophia Mathematica 8 (3):244--58 (2000)

Add citations

You must login to add citations.
  1. 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  
  • In Defense of the Unprovability of the Church-Turing Thesis.Selmer Bringsjord - unknown
    One of us has previously argued that the Church-Turing Thesis (CTT), contra Elliot Mendelson, is not provable, and is — light of the mind’s capacity for effortless hypercomputation — moreover false (e.g., [13]). But a new, more serious challenge has appeared on the scene: an attempt by Smith [28] to prove CTT. His case is a clever “squeezing argument” that makes crucial use of Kolmogorov-Uspenskii (KU) machines. The plan for the present paper is as follows. After covering some necessary preliminaries (...)
    Direct download  
    Translate
     
     
    Export citation  
     
    Bookmark   2 citations  
  • A Note on the Relation Between Formal and Informal Proof.Jörgen Sjögren - 2010 - Acta Analytica 25 (4):447-458.
    Using Carnap’s concept explication, we propose a theory of concept formation in mathematics. This theory is then applied to the problem of how to understand the relation between the concepts formal proof and informal, mathematical proof.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • Turing-, Human- and Physical Computability: An Unasked Question. [REVIEW]Eli Dresner - 2008 - Minds and Machines 18 (3):349-355.
    In recent years it has been convincingly argued that the Church-Turing thesis concerns the bounds of human computability: The thesis was presented and justified as formally delineating the class of functions that can be computed by a human carrying out an algorithm. Thus the Thesis needs to be distinguished from the so-called Physical Church-Turing thesis, according to which all physically computable functions are Turing computable. The latter is often claimed to be false, or, if true, contingently so. On all accounts, (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Should Computability Be Epistemic? A Logical and Physical Point of View.Florent Franchette - 2016 - Philosophies 1 (1):15--27.
    Although the formalizations of computability provided in the 1930s have proven to be equivalent, two different accounts of computability may be distinguished regarding computability as an epistemic concept. While computability, according to the epistemic account, should be based on epistemic constraints related to the capacities of human computers, the non-epistemic account considers computability as based on manipulations of symbols that require no human capacities other than the capacity of manipulating symbols according to a set of rules. In this paper, I (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • The Equivalence of Definitions of Algorithmic Randomness†.Christopher Porter - forthcoming - Philosophia Mathematica:nkaa039.
    ABSTRACT In this paper, I evaluate the claim that the equivalence of multiple intensionally distinct definitions of random sequence provides evidence for the claim that these definitions capture the intuitive conception of randomness, concluding that the former claim is false. I then develop an alternative account of the significance of randomness-theoretic equivalence results, arguing that they are instances of a phenomenon I refer to as schematic equivalence. On my account, this alternative approach has the virtue of providing the plurality of (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • 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  
  • Human-Effective Computability†.Marianna Antonutti Marfori & Leon Horsten - 2018 - Philosophia Mathematica 27 (1):61-87.
    We analyse Kreisel’s notion of human-effective computability. Like Kreisel, we relate this notion to a concept of informal provability, but we disagree with Kreisel about the precise way in which this is best done. The resulting two different ways of analysing human-effective computability give rise to two different variants of Church’s thesis. These are both investigated by relating them to transfinite progressions of formal theories in the sense of Feferman.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Non-Standard Numbers: A Semantic Obstacle for Modelling Arithmetical Reasoning.Anderson De Araújo & Walter Carnielli - 2012 - Logic Journal of the IGPL 20 (2):477-485.
    The existence of non-standard numbers in first-order arithmetics is a semantic obstacle for modelling our arithmetical skills. This article argues that so far there is no adequate approach to overcome such a semantic obstacle, because we can also find out, and deal with, non-standard elements in Turing machines.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations