An effective method is a computational method that might, in principle, be executed by a human. In this paper, I argue that there are methods for computing that are not effective methods. The examples I consider are taken primarily from quantum computing, but these are only meant to be illustrative of a much wider class. Quantum inference and quantum parallelism involve steps that might be implemented in multiple physical systems, but cannot be implemented, or at least not at will, by (...) an idealised human. Recognising that not all computational methods are effective methods is important for at least two reasons. First, it is needed to correctly state the results of Turing and other founders of computation theory. Turing is sometimes said to have offered a replacement for the informal notion of an effective method with the formal notion of a Turing machine. I argue that such a view only holds under limited circumstances. Second, not distinguishing between computational methods and effective methods can lead to mistakes when quantifying over the class of all possible computational methods. Such quantification is common in philosophy of mind in the context of thought experiments that explore the limits of computational functionalism. I argue that these ‘homuncular’ thought experiments should not be treated as valid. (shrink)

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.

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 definitions (...) of randomness with conceptual unity and a rationale for certain investigations that are carried out in the field. (shrink)

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. (...) I argue that Bold Physical CT is not relevant to the epistemological concerns that motivate CT and hence not suitable as a physical analog of Mathematical CT. The correct physical analog of Mathematical CT is Modest Physical CT. I propose to explicate the notion of physical computability in terms of a usability constraint, according to which for a process to count as relevant to Physical CT, it must be usable by a finite observer to obtain the desired values of a function. Finally, I suggest that proposed counterexamples to Physical CT are still far from falsifying it because they have not been shown to satisfy the usability constraint. (shrink)

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 (...) shall evaluate, both from a logical and physical point of view, whether computability should be regarded as an epistemic concept, i.e., whether epistemic constraints should be added on computability for considering functions as computable. Specifically, I shall argue that the introduction of epistemic constraints have deep implications for the set of computable functions, for the logical and physical Church-Turing thesis—cornerstones of logical and physical computability respectively—might turn out to be false according to which epistemic constraints are accepted. (shrink)

An investigation of the concept of “surveyability” as traced through the thought of Hilbert, Wittgenstein, and Turing. The communicability and reproducibility of proof, with certainty, are seen as earmarked by the “surveyability” of symbols, sequences, and structures of proof in all these thinkers. Hilbert initiated the idea within his metamathematics, Wittgenstein took up a kind of game formalism in the 1920s and early 1930s in response. Turing carried Hilbert’s conception of the “surveyability” of proof in metamathematics through into his analysis (...) of what a formal system (what a step in a computation) is in “On computable numbers, with an application to the Entscheidungsproblem” (1936). Wittgenstein’s 1939 investigations of the significance of surveyability to the concept of “proof “in Principia Mathematica were influenced, both by Turing’s remarkable everyday analysis of the Hilbertian idea, and by conversations with Turing. Although Turing does not use the word “surveyability” explicitly, it is clear that the Hilbertian idea plays a recurrent role in his work, refracted through his engagement with Wittgenstein’s idea of a “language-game”. This is evinced in some of his later writings, where the “reform” of mathematical notation for the sake of human surveyability (1944/45) may be seen to draw out the Hilbertian idea. For Turing, as for Wittgenstein, the need for “surveyability” earmarks the evolving culture of humans located in an evolving social and scientific world, just as it had for Hilbert. (shrink)

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, (...) though, thesis M is not easy to give counterexamples to, but it is never asked why—how come that a thesis that transfers a notion from the strictly human domain to the general physical domain just happens to be so difficult to falsify. In this paper I articulate this question and consider several tentative answers to it. (shrink)

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 (...) Thesis, as Gödel and others suggested may be possible. In a similar way, but with a different set of basic operations, one can prove Turing's Thesis, characterizing the effective string functions, and--in particular--the effectively-computable functions on string representations of numbers. (shrink)

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.

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 (...) regarding the nature of CTT, and taking note of the fact that this thesis is “intrinsically cognitive” (§2), we: sketch out, for context, an open-minded position on CTT and related matters (§3); explain the formal structure of squeezing arguments (§4); after a review of KU-machines, formalize Smith’s case (§5); give our objections to certain assumptions in Smith’s argument (§6); support these objections with some evidence from general but limited-agent problem solving (§7); and explain why Smith’s argument is inconclusive (§8). We end with some brief, concluding remarks, some of which point toward near-future work that will build on the present paper (§9). (shrink)