If we take "experimental philosophy" in a wider sense, it is almost the same as methodological naturalism in philosophy. Experiments of this kind would be available and also fruitful in the philosophy of mathematics. They surely will have a substantial contribution to epistemology of mathematics. At present, however, the phrase "experimental philosophy" is used in a much narrower sense. It refers exclusively to a branch of naturalized philosophy that uses the data gathered through questionnaire surveys to investigate the intuitions of (...) ordinary people. We claim that experimental philosophy in this narrower sense will have little relevance to the philosophy of mathematics, since the philosophy of mathematics is not engaged in conceptual analysis despite of its appearance. (shrink)

Computational complexity theory is a branch of computer science dedicated to classifying computational problems in terms of their difficulty. While computability theory tells us what we can compute in principle, complexity theory informs us regarding our practical limits. In this chapter I argue that the science of \emph{quantum computing} illuminates complexity theory by emphasising that its fundamental concepts are not model-independent, but that this does not, as some suggest, force us to radically revise the foundations of the theory. For model-independence (...) never has been essential to those foundations. The fundamental aim of complexity theory is to describe what is achievable in practice under various models of computation for our various practical purposes. Reflecting on quantum computing illuminates complexity theory by reminding us of this, too often under-emphasised, fact. (shrink)

This paper reveals two fallacies in Turing's undecidability proof of first-order logic (FOL), namely, (i) an 'extensional fallacy': from the fact that a sentence is an instance of a provable FOL formula, it is inferred that a meaningful sentence is proven, and (ii) a 'fallacy of substitution': from the fact that a sentence is an instance of a provable FOL formula, it is inferred that a true sentence is proven. The first fallacy erroneously suggests that Turing's proof of the non-existence (...) of a circle-free machine that decides whether an arbitrary machine is circular proves a significant proposition. The second fallacy suggests that FOL is undecidable. (shrink)

Heuristics are often invoked in the philosophical, psychological, and cognitive science literatures to describe or explain methodological techniques or "shortcut" mental operations that help in inference, decision-making, and problem-solving. Yet there has been surprisingly little philosophical work done on the nature of heuristics and heuristic reasoning, and a close inspection of the way(s) in which "heuristic" is used throughout the literature reveals a vagueness and uncertainty with respect to what heuristics are and their role in cognition. This dissertation seeks to (...) remedy this situation by motivating philosophical inquiry into heuristics and heuristic reasoning, and then advancing a theory of how heuristics operate in cognition. I develop a positive working characterization of heuristics that is coherent and robust enough to account for a broad range of phenomena in reasoning and inference, and makes sense of empirical data in a systematic way. I then illustrate the work this characterization does by considering the sorts of problems that many philosophers believe heuristics solve, namely those resulting from the so-called frame problem. Considering the frame problem motivates the need to gain a better understanding of how heuristics work and the cognitive structures over which they operate. I develop a general theory of cognition which I argue underwrites the heuristic operations that concern this dissertation. I argue that heuristics operate over highly organized systems of knowledge, and I offer a cognitive architecture to accommodate this view. I then provide an account of the systems of knowledge that heuristics are supposed to operate over, in which I suggest that such systems of knowledge are concepts. The upshot, then, is that heuristics operate over concepts. I argue, however, that heuristics do not operate over conceptual content, but over metainformational relations between activated and primed concepts and their contents. Finally, to show that my thesis is empirically adequate, I consider empirical evidence on heuristic reasoning and argue that my account of heuristics explains the data. (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.

We analyse the connection between the computability and continuity of functions in the case of homomorphisms between topological algebraic structures. Inspired by the Pour-El and Richards equivalence theorem between computability and boundedness for closed linear operators on Banach spaces, we study the rather general situation of partial homomorphisms between metric partial universal algebras. First, we develop a set of basic notions and results that reveal some of the delicate algebraic, topological and effective properties of partial algebras. Our main computability concepts (...) are based on numerations and include those of effective metric partial algebras and effective partial homomorphisms. We prove a general equivalence theorem that includes a version of the Pour-El and Richards Theorem, and has other applications. Finally, the Pour-El and Richards axioms for computable sequence structures on Banach spaces are generalised to computable partial sequence structures on metric algebras, and we prove their equivalence with our computability model based on numerations. (shrink)

A version of the Church-Turing Thesis states that every effectively realizable physical system can be simulated by Turing Machines (‘Thesis P’). In this formulation the Thesis appears to be an empirical hypothesis, subject to physical falsification. We review the main approaches to computation beyond Turing definability (‘hypercomputation’): supertask, non-well-founded, analog, quantum, and retrocausal computation. The conclusions are that these models reduce to supertasks, i.e. infinite computation, and that even supertasks are no solution for recursive incomputability. This yields that the realization (...) of hypercomputing devices is implausible, and that Thesis P is not essentially different from the standard Church-Turing Thesis. (shrink)

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; (...) Turing’s analysis of computability; Turing’s Notational Thesis. (shrink)

Since the cognitive revolution, it has become commonplace that cognition involves both computation and information processing. Is this one claim or two? Is computation the same as information processing? The two terms are often used interchangeably, but this usage masks important differences. In this paper, we distinguish information processing from computation and examine some of their mutual relations, shedding light on the role each can play in a theory of cognition. We recommend that theorists of cognition be explicit and careful (...) in choosing notions of computation and information and connecting them together.Keywords: Computation; Information processing; Computationalism; Computational theory of mind; Cognitivism. (shrink)

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.

logiikka on lopullinen ja täydellinen logiikka. Sittemmin logiikka on kuitenkin kokenut melkoisen mullistuksen. Käsitykset siitä, mikä tässä muutoksessa oli olennaista ja milloin se todella tapahtui, vaihtelevat.

This essay accounts for the notion of _Lebensform_ by assigning it a _logical _role in Wittgenstein’s later philosophy. Wittgenstein’s additions of the notion to his manuscripts of the _PI_ occurred during the initial drafting of the book 1936-7, after he abandoned his effort to revise _The Brown Book_. It is argued that this constituted a substantive step forward in his attitude toward the notion of simplicity as it figures within the notion of logical analysis. Next, a reconstruction of his later (...) remarks on _Lebensformen_ is offered which factors in his reading of Alan Turing’s “On computable numbers, with an application to the _Entscheidungsproblem_“, as well as his discussions with Turing 1937-1939. An interpretation of the five occurrences of _Lebensform_ in the PI is then given in terms of a logical “regression” to _Lebensform_ as a fundamental notion. This regression characterizes Wittgenstein’s mature answer to the question, “What is the nature of the logical?”. (shrink)

It is commonly believed that there is no equivalent of the Church–Turing thesis for computation over the reals. In particular, computational models on this domain do not exhibit the convergence of formalisms that supports this thesis in the case of integer computation. In the light of recent philosophical developments on the different meanings of the Church–Turing thesis, and recent technical results on analog computation, I will show that this current belief confounds two distinct issues, namely the extension of the notion (...) of effective computation to the reals on the one hand, and the simulation of analog computers by Turing machines on the other hand. I will argue that it is possible in both cases to defend an equivalent of the Church–Turing thesis over the reals. Along the way, we will learn some methodological caveats on the comparison of different computational models, and how to make it meaningful. (shrink)

An original quantum foundations concept of a deep learning computational Universe is introduced. The fundamental information of the Universe (or Triuniverse)is postulated to evolve about itself in a Red, Green and Blue (RGB) tricoloured stable self-mutuality in three information processing loops. The colour is a non-optical information label. The information processing loops form a feedback-reinforced deep learning macrocycle with trefoil knot topology. Fundamental information processing is driven by ψ-Epistemic Drive, the Natural appetite for information selected for advantageous knowledge. From its (...) substrate of Mathematics, the knotted information processing loops determine emergent Physics and thence the evolution of super-emergent Life (biological and artificial intelligence). RGB-tricoloured information is processed in sequence in an Elemental feedback loop (R), then an Operational feedback loop (G), then a Structural feedback loop (B) and back to an Elemental feedback loop (R), and so on around the trefoil in deep learning macrocycles. It is postulated that hierarchical information correspondence from Mathematics through Physics to Life is mapped and conserved within each colour. The substrate of Mathematics has RGB-tricoloured feedback loops which are respectively Algebra (R), Algorithms (G) and Geometry (B). In Mathematics, the trefoil macrocycle is Algebraic Algorithmic Geometry and its correlation system is a Tensor Neural Knot Network enabling Qutrit Entanglement. Emergent Physics has corresponding RGB-tricoloured feedback loops of Quantum Mechanics (R), Quantum Deep Learning (G) and Quantum Geometrodynamics(B). In Physics, the trefoil macrocycle is Quantum Intelligent Geometrodynamics and its correlation system is Quantum Darwinism. Super-emergent Life has corresponding RGB-tricoloured loops of Variation (R), Selection (G) and Heredity (B). In the evolution of Life, the trefoil macrocycle is Variational Selective Heredity and its correlation ecosystem is Darwin’s ecologically “Entangled Bank”. (shrink)

The idea that simplicity matters in science is as old as science itself, with the much cited example of Ockham's Razor, 'entia non sunt multiplicanda praeter necessitatem': entities are not to be multiplied beyond necessity. A problem with Ockham's razor is that nearly everybody seems to accept it, but few are able to define its exact meaning and to make it operational in a non-arbitrary way. Using a multidisciplinary perspective including philosophers, mathematicians, econometricians and economists, this 2002 monograph examines simplicity (...) by asking six questions: what is meant by simplicity? How is simplicity measured? Is there an optimum trade-off between simplicity and goodness-of-fit? What is the relation between simplicity and empirical modelling? What is the relation between simplicity and prediction? What is the connection between simplicity and convenience? The book concludes with reflections on simplicity by Nobel Laureates in Economics. (shrink)

If the Trade Descriptions Act were applied to academic labels, cognitive scientists would be in trouble. For what they do is much wider than the name suggests—and wider, too, than most philosophers assume. They give you more for your money than you may have expected.

Leonid Levin showed that every algorithm computing a function has an optimal inverter. Recently, we applied his result in various contexts: existence of optimal acceptors, existence of hard sequences for algorithms and proof systems, proofs of Gödel’s incompleteness theorems, analysis of the complexity of the clique problem assuming the nonuniform Exponential Time Hypothesis. We present all these applications here. Even though a simple diagonalization yields Levin’s result, we believe that it is worthwhile to be aware of the explicit result. The (...) purpose of this survey is to convince the reader of our view. (shrink)

The -logic of Terwijn is a variant of first-order logic with the same syntax in which the models are equipped with probability measures and the quantifier is interpreted as ‘there exists a set A of a measure such that for each,...’. Previously, Kuyper and Terwijn proved that the general satisfiability and validity problems for this logic are, i) for rational, respectively -complete and -hard, and ii) for, respectively decidable and -complete. The adjective ‘general’ here means ‘uniformly over all languages’. We (...) extend these results in the scenario of finite models. In particular, we show that the problems of satisfiability and validity with respect to finite models in E-logic are, i) for rational, respectively -complete and -complete, and ii) for, respectively decidable and -complete. Although partial results toward the countable case are also achieved, the computability of E-logic over countable models still remains largely unsolved. In addition, most o... (shrink)

In our 2015 book Imagination and Convention, we explore the scope and limits of linguistic knowledge in semantics and pragmatics for natural language. We draw heavily on the notion of coordination from David Lewis' book on conventions. To the extent that the account we develop is right, general principles like Grice's cooperative principle and the maxims of conversation have little to say about about interpretation. Three commentators—Anne Bezuidenhout, Laurence Horn, and Zoltan Gendler Szabo—discuss and evaluate our program in three essays (...) in this issue. What follows is our response to their challenges. (shrink)

It has been just over 100 years since the birth of Alan Turing and more than 65 years since he published in Mind his seminal paper, Computing Machinery and Intelligence. In the Mind paper, Turing asked a number of questions, including whether computers could ever be said to have the power of “thinking”. Turing also set up a number of criteria—including his imitation game—under which a human could judge whether a computer could be said to be “intelligent”. Turing’s paper, as (...) well as his important mathematical and computational insights of the 1930s and 1940s led to his popular acclaim as the “Father of Artificial Intelligence”. In the years since his paper was published, however, no computational system has fully satisfied Turing’s challenge. In this paper we focus on a different question, ignored in, but inspired by Turing’s work: How might the Artificial Intelligence practitioner implement “intelligence” on a computational device? Over the past 60 years, although the AI community has not produced a general-purpose computational intelligence, it has constructed a large number of important artifacts, as well as taken several philosophical stances able to shed light on the nature and implementation of intelligence. This paper contends that the construction of any human artifact includes an implicit epistemic stance. In AI this stance is found in commitments to particular knowledge representations and search strategies that lead to a product’s successes as well as its limitations. Finally, we suggest that computational and human intelligence are two different natural kinds, in the philosophical sense, and elaborate on this point in the conclusion. (shrink)

We examine the verification of simple quantifiers in natural language from a computational model perspective. We refer to previous neuropsychological investigations of the same problem and suggest extending their experimental setting. Moreover, we give some direct empirical evidence linking computational complexity predictions with cognitive reality.<br>In the empirical study we compare time needed for understanding different types of quantifiers. We show that the computational distinction between quantifiers recognized by finite-automata and push-down automata is psychologically relevant. Our research improves upon hypothesis and (...) explanatory power of recent neuroimaging studies as well as provides<br>evidence. (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)

The birth, growth, stabilization and subsequent understanding of a new field of practical and theoretical enquiry is always a conceptual process including several typologies of events, phenomena an...

Fetzer famously claims that program verification is not even a theoretical possibility, and offers a certain argument for this far-reaching claim. Unfortunately for Fetzer, and like-minded thinkers, this position-argument pair, while based on a seminal insight that program verification, despite its Platonic proof-theoretic airs, is plagued by the inevitable unreliability of messy, real-world causation, is demonstrably self-refuting. As I soon show, Fetzer is like the person who claims: ‘My sole claim is that every claim expressed by an English sentence and (...) starting with the phrase “My sole claim” is false’. Or, more accurately, such thinkers are like the person who claims that modus tollens is invalid, and supports this claim by giving an argument that itself employs this rule of inference. (shrink)

We have begun a theory of measurement in which an experimenter and his or her experimental procedure are modeled by algorithms that interact with physical equipment through a simple abstract interface. The theory is based upon using models of physical equipment as oracles to Turing machines. This allows us to investigate the computability and computational complexity of measurement processes. We examine eight different experiments that make measurements and, by introducing the idea of an observable indicator, we identify three distinct forms (...) of measurement process and three types of measurement algorithm. We give axiomatic specifications of three forms of interfaces that enable the three types of experiment to be used as oracles to Turing machines, and lemmas that help certify an experiment satisfies the axiomatic specifications. For experiments that satisfy our axiomatic specifications, we give lower bounds on the computational power of Turing machines in polynomial time using nonuniform complexity classes. These lower bounds break the barrier defined by the Church-Turing Thesis. (shrink)

The question ‘What is computation?’ might seem a trivial one to many, but this is far from being in consensus in philosophy of mind, cognitive science and even in physics. The lack of consensus leads to some interesting, yet contentious, claims, such as that cognition or even the universe is computational. Some have argued, though, that computation is a subjective phenomenon: whether or not a physical system is computational, and if so, which computation it performs, is entirely a matter of (...) an observer choosing to view it as such. According to one view, which we dub bold anti-realist pancomputationalism, every physical object (can be said to) computes every computer program. According to another, more modest view, some computational systems can be ascribed multiple computational descriptions. We argue that the first view is misguided, and that the second view need not entail observer-relativity of computation. At least to a large extent, computation is an objective phenomenon. Construed as a form of information processing, we argue that information-processing considerations determine what type of computation takes place in physical systems. (shrink)

Turing’s paper on computable numbers has played its role in underpinning different perspectives on the world of information. On the one hand, it encourages a digital ontology, with a perceived flatness of computational structure comprehensively hosting causality at the physical level and beyond. On the other, it can give an insight into the way in which higher order information arises and leads to loss of computational control—while demonstrating how the control can be re-established, in special circumstances, via suitable type reductions. (...) We examine the classical computational framework more closely than is usual, drawing out lessons for the wider application of information–theoretical approaches to characterizing the real world. The problem which arises across a range of contexts is the characterizing of the balance of power between the complexity of informational structure and the means available to bring this information back into the computational fold. We proceed via appropriate mathematical modelling to a more coherent view of the computational structure of information, relevant to a wide spectrum of areas of investigation. (shrink)

Two aspects of cognitive coupling, as brought forward in the Extended Mind Hypothesis, are discussed in this paper: how shall the functional coupling between the organism and some entity in his environment be spelled out in detail? What are the paradigmatic external entities to enter into that coupling? These two related questions are best answered in the light of an aetiological variety of functionalist argument that adds historical depth to the “active externalism” promoted by Clark and Chalmers and helps to (...) counter some of the core criticisms levelled against this view. Under additional reference to conceptual parallels between the Extended Mind Hypothesis and a set of heterodox theories in biology—environmental constructivism, niche construction, developmental systems theory—an argument for the grounding of environmentally extended cognitive traits in evolved biological functions is developed. In a spirit that seeks to integrate extended functionalism with views from cognitive integration and complementarity, it is argued that instances of environmental coupling should be understood as being constitutive to cognitive functions in either of two distinct ways. It is further argued that the historically and systematically prior environmental counterparts in that coupling are features of the natural environment. Language and linguistically imbued artefacts are likely to have descended from more basic relations that have an extension over the environment. (shrink)

Marr's levels of analysis—computational, algorithmic, and implementation—have served cognitive science well over the last 30 years. But the recent increase in the popularity of the computational level raises a new challenge: How do we begin to relate models at different levels of analysis? We propose that it is possible to define levels of analysis that lie between the computational and the algorithmic, providing a way to build a bridge between computational- and algorithmic-level models. The key idea is to push the (...) notion of rationality, often used in defining computational-level models, deeper toward the algorithmic level. We offer a simple recipe for reverse-engineering the mind's cognitive strategies by deriving optimal algorithms for a series of increasingly more realistic abstract computational architectures, which we call “resource-rational analysis.”. (shrink)

Recently, many philosophers have been inclined to ascribe mentality to animals on the main grounds that they possess certain complex computational abilities. In this paper I contend that this view is misleading, since it wrongly assumes that those computational abilities demand a psychological explanation. On the contrary, they can be just characterised from a computational level of explanation, which picks up a domain of computation and information processing that is common to many computing systems but is autonomous from the domain (...) of psychology. Thus, I propose that it is possible to conceive insects and other animals as mere computing agents, without having any commitment to ascribe mentality to them. I conclude by sketching a proposal about how to draw the line between mere computing and genuine mentality. (shrink)

Traces the development of recursive functions from their origins in the late nineteenth century to the mid-1930s, with particular emphasis on the work and influence of Kurt Gödel.

We propose here an extension of Rice's Theorem to first-order logic, proven by totally elementary means. If P is any property defined over the collection of all first-order theories and P is non-trivial over the set of finitely axiomatizable theories , then P is undecidable. This not only means that the problem of deciding properties of first-order theories is as hard as the problem of deciding properties about languages accepted by Turing machines, but also offers a general setting for proving (...) several undecidability results in first-order theories. (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.

This essay will be divided into three parts. In the first part, we discuss the case of infintesimals seen as a bridge between the discrete and the continuous. This leads in the second part to a discussion of the nature of numbers. In the last part, we follow up with some observations on the obvious applicability of mathematics.

This paper explores different interpretations of the word ‘deep’ as it is used by mathematicians, with a large number of examples illustrating various criteria for depth. Most of the examples are theorems with ‘historical depth’, in the sense that many generations of mathematicians contributed to their proof. Some also have ‘foundational depth’, in the sense that they support large mathematical theories. Finally, concepts from mathematical logic suggest that it may be possible to order certain theorems or problems according to ‘logical (...) depth’. (shrink)

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 (...) for CTT by analyzing the processes carried out by a human computer. I then contend that if the Gandy–Sieg account is correct, then the notion of effective computability has changed after 1936. Today computer scientists view effective computability in terms of finite machine computation. My contention is supported by the current formulations of CTT, which always refer to machine computation, and by the current argumentation for CTT, which is different from the main arguments advanced by Turing and Church. I finally turn to discuss Robin Gandy's characterization of machine computation. I suggest that there is an ambiguity regarding the types of machines Gandy was postulating. I offer three interpretations, which differ in their scope and limitations, and conclude that none provides the basis for claiming that Gandy characterized finite machine computation. (shrink)