Saul Kripke once noted that there is a tight connection between computation and de re knowledge of whatever the computation acts upon. For example, the Euclidean algorithm can produce knowledge of which number is the greatest common divisor of two numbers. Arguably, algorithms operate directly on syntactic items, such as strings, and on numbers and the like only via how the numbers are represented. So we broach matters of notation. The purpose of this article is to explore the relationship between (...) the notations acceptable for computation, the usual idealizations involved in theories of computability, flowing from Alan Turing’s monumental work, and de re propositional attitudes toward numbers and other mathematical objects. (shrink)

Turing used the expression “emotional” in three distinct ways: to state his philosophical theory of the concept of intelligence, to classify arguments for and against the possibility of machine intelligence, and to describe the education of a “child machine”. The remarks on emotion include several of the most important philosophical claims. This paper analyses these remarks and their significance for current research in Artificial Intelligence.

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 (...) studies entities as represented in certain ways, rather than entities detached from any means of representing them. (shrink)

In the framework of Stewart Shapiro, computations are performed directly on strings of symbols (numerals) whose abstract numerical interpretation is determined by a notation. Shapiro showed that a total unary function (unary relation) on natural numbers is computable in every injective notation if and only if it is almost constant or almost identity function (finite or co-finite set). We obtain a syntactic generalization of this theorem, in terms of quantifier-free definability, for functions and relations relatively intrinsically computable on certain types (...) of equivalence structures. We also characterize the class of relations and partial functions of arbitrary finite arities which are computable in every notation (be it injective or not). We consider the same question for notations in which certain equivalence relations are assumed to be computable. Finally, we discuss connections with a theorem by Ash, Knight, Manasse and Slaman which allow us to deduce some (but not all) of our results, based on quantifier elimination. (shrink)

Turing and Church formulated two different formal accounts of computability that turned out to be extensionally equivalent. Since the accounts refer to different properties they cannot both be adequate conceptual analyses of the concept of computability. This insight has led to a discussion concerning which account is adequate. Some authors have suggested that this philosophical debate—which shows few signs of converging on one view—can be circumvented by regarding Church’s and Turing’s theses as explications. This move opens up the possibility that (...) both accounts could be adequate, albeit in their own different ways. In this paper, I focus on the question of whether Church’s thesis can be seen as an explication in the precise Carnapian sense. Most importantly, I address an additional constraint that Carnap puts on the explicative power of axiomatic systems—an axiomatisation explicates when it is clear which mathematical entities form the theory’s intended model—and that implicitly applies to axiomatisations of recursion theory used in Church’s account of computability. To overcome this difficulty, I propose two possible clarifications of the pre-systematic concept of “computability” that can both be captured in recursion theory, and I show how both clarifications avoid an objection arising from Carnap’s constraint. (shrink)

I examine the classical idea of ‘algorithm’ as a sequential, step-by-step, deterministic procedure (i.e., the idea of ‘algorithm’ that was already in use by the 1930s), with respect to three themes, its relation to the notion of an ‘effective procedure’, its different roles and uses in logic, computer science, and mathematics (focused on numerical analysis), and its different formal definitions proposed by practitioners in these areas. I argue that ‘algorithm’ has been conceptualized and used in contrasting ways in the above (...) areas, and discuss challenges and prospects for adopting a final foundational theory of (classical) ‘algorithms’. (shrink)

Models of memory in cognitive science and philosophy have traditionally explained human remembering in terms of storage and retrieval. This tendency has been entrenched by reliance on computationalist explanations over the course of the twentieth century; even research programs that eschew computationalism in name, or attempt the revision of traditional models, demonstrate tacit commitment to computationalist assumptions. It is assumed that memory must be stored by means of an isomorphic trace, that memory processes must divide into conceptually distinct systems and (...) phases, and that human remembering consists in inner, cognitive processes that are implemented by distinct neural processes. This dissertation draws on recent empirical work, and on philosophical arguments from Ludwig Wittgenstein and others, to demonstrate that this latent computationalism in the study of memory is problematic, and that it can and should be eliminated. Cognitive psychologists studying memory have encountered numerous data in recent decades that belie archival models. In cognitive neuroscience, establishing the neural basis of storage and retrieval processes has proven elusive. A number of revised models on offer in memory science, that have taken these issues into account, fail to sufficiently extricate the archival framework. Several impasses in memory science are products of these underlying computationalist assumptions. Wittgenstein and other philosophers offer a number of arguments against the need for, and the efficacy of, the storage and retrieval of traces in human remembering. A study of these arguments clarifies the ways that these computationalist assumptions are presently impeding the science of memory, and provides ways forward in removing them. We can and should characterize and model human memory without invoking the storage and retrieval of traces. A range of work in connectionism, dynamical systems theory, and recent philosophical accounts of memory demonstrate how the science of memory can proceed without these assumptions, toward non-archival models of remembering. (shrink)

A. N. Turing’s 1936 concept of computability, computing machines, and computable binary digital sequences, is subject to Turing’s Cardinality Paradox. The paradox conjoins two opposed but comparably powerful lines of argument, supporting the propositions that the cardinality of dedicated Turing machines outputting all and only the computable binary digital sequences can only be denumerable, and yet must also be nondenumerable. Turing’s objections to a similar kind of diagonalization are answered, and the implications of the paradox for the concept of a (...) Turing machine, computability, computable sequences, and Turing’s effort to prove the unsolvability of the Entscheidungsproblem, are explained in light of the paradox. A solution to Turing’s Cardinality Paradox is proposed, positing a higher geometrical dimensionality of machine symbol-editing information processing and storage media than is available to canonical Turing machine tapes. The suggestion is to add volume to Turing’s discrete two-dimensional machine tape squares, considering them instead as similarly ideally connected massive three-dimensional machine information cells. Three-dimensional computing machine symbol-editing information processing cells, as opposed to Turing’s two-dimensional machine tape squares, can take advantage of a denumerably infinite potential for parallel digital sequence computing, by which to accommodate denumerably infinitely many computable diagonalizations. A three-dimensional model of machine information storage and processing cells is recommended on independent grounds as better representing the biological realities of digital information processing isomorphisms in the three-dimensional neural networks of living computers. (shrink)

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.

Many philosophers contend that Turing’s work provides a conceptual analysis of numerical computability. In (Rescorla, 2007), I dissented. I argued that the problem of deviant notations stymies existing attempts at conceptual analysis. Copeland and Proudfoot respond to my critique. I argue that their putative solution does not succeed. We are still awaiting a genuine conceptual analysis.

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 (...) a definition of a notation, which will be further used in a definition of the concept of computation yields an obvious vicious circle. The circularity of this definition causes trouble in distinguishing on the theoretical level, what is an acceptable notation from what is not an acceptable notation, or as it is usually referred to in the literature, “deviant encodings”. Deviant encodings appear explicitly in discussions about what is an adequate or correct conceptual analysis of the concept of computation. In this paper, I focus on philosophical examples where the phenomenon appears implicitly, in a “disguised” version. In particular, I present its use in the analysis of the concept of natural number. I also point at additional phenomena related to deviant encodings: conceptual fixed points and apparent “computability” of uncomputable functions. In parallel, I develop the idea that Carnapian explications provide a much more adequate framework for understanding the concept of computation, than the classical philosophical analysis. (shrink)

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 (...) function is computable? These are the acceptable notations. I argue for a use criterion of acceptability: the acceptable notations for a domain of objects D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {D}}$$\end{document} are the notations that we can use for the usual D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {D}}$$\end{document}-activities. Acceptable notations for natural numbers are ones that we can count with. Acceptable notations for logical formulas are the ones that we can use in inference and logical analysis. And so on. This criterion makes computability a relative notion—whether a function is computable depends on which notations are acceptable, which is relative to our interests and abilities. I argue that this is not a problem, however, since there is independent reason for taking the extension of computable function to be relative to contingent facts. Similarly, the fact that the use criterion makes a mathematical distinction depend on practical concerns is also not a problem because it dovetails with similar phenomena in other areas of computability theory, namely the roles of notation in computation over real numbers and of Extended Church’s Thesis in complexity theory. (shrink)