One recursively enumerable real α dominates another one β if there are nondecreasing recursive sequences of rational numbers (a[n] : n ∈ ω) approximating α and (b[n] : n ∈ ω) approximating β and a positive constant C such that for all n, C(α − a[n]) ≥ (β − b[n]). See [R. M. Solovay, Draft of a Paper (or Series of Papers) on Chaitin’s Work, manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1974, p. 215] and [G. J. (...) Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. We show that every recursively enumerable random real dominates all other recursively enumerable reals. We conclude that the recursively enumerable random reals are exactly the Ω-numbers [G. J. Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. Second, we show that the sets in a universal Martin-Lof test for randomness have random measure, and every recursively enumerable random number is the sum of the measures represented in a universal Martin-Lof test. (shrink)

This book constitutes the strictly refereed post-workshop proceedings of the 11th International Workshop on Computer Science Logic, CSL '97, held as the 1997 Annual Conference of the European Association on Computer Science Logic, EACSL, in Aarhus, Denmark, in August 1997. The volume presents 26 revised full papers selected after two rounds of refereeing from initially 92 submissions; also included are four invited papers. The book addresses all current aspects of computer science logics and its applications and thus presents the state (...) of the art in the area. (shrink)

Theory of Mind (ToM), the cognitive capacity to attribute internal mental states to oneself and others, is a crucial component of social skills. Its formal study has become important, witness recent research on reasoning and information update by intelligent agents, and some proposals for its formal modelling have put forward settings based on Epistemic Logic (EL). Still, due to intrinsic idealisations, it is questionable whether EL can be used to model the high-order cognition of ‘real’ agents. This manuscript proposes a (...) framework that takes visibility, memory, perspective and communication as the main factors underpinning mental attributions. This is more in-line with findings in cognitive science and allows us to model well-known False-Belief Tasks that are typically used in testing people's ToM. We discuss some of the framework's technical features, arguing why it does justice to empirical observations. (shrink)

Begin discussing various forms of G1 put into the form: If a first order theory satisfies one or more adequacy conditions then it has one or more wildness properties. We continue with the new ‘no interpretation’ forms of G2, which are fundamentally model theoretic formulations. We also give corresponding model theoretic characterizations of the consistency statement Con(T) for finitely axiomatized T. We present the known proof of the 1-Con form by G2 by transparent diagonalization and discuss attempts to do so (...) for G2. (shrink)

We consider the informal concept of "computability" or "effective calculability" and two of the formalisms commonly used to define it, "(Turing) computability" and "(general) recursiveness". We consider their origin, exact technical definition, concepts, history, general English meanings, how they became fixed in their present roles, how they were first and are now used, their impact on nonspecialists, how their use will affect the future content of the subject of computability theory, and its connection to other related areas. (...) After a careful historical and conceptual analysis of computability and recursion we make several recommendations in section §7 about preserving the intensional differences between the concepts of "computability" and "recursion." Specifically we recommend that: the term "recursive" should no longer carry the additional meaning of "computable" or "decidable;" functions defined using Turing machines, register machines, or their variants should be called "computable" rather than "recursive;" we should distinguish the intensional difference between Church's Thesis and Turing's Thesis, and use the latter particularly in dealing with mechanistic questions; the name of the subject should be "Computability Theory" or simply Computability rather than "Recursive Function Theory.". (shrink)

The problem of intentional identity, as originally offered by Peter Geach, says that there can be an anaphoric link between an indefinite term and a pronoun across a sentential boundary and across propositional attitude contexts, where the actual existence of an individual for the indefinite term is not presupposed. In this paper, a semantic resolution to this elusive puzzle is suggested, based on a new quantified intensional logic and game-theoretic semantics (GTS) of imperfect information. This constellation leads to an expressive (...) intensional language with a property of informational independence, argued to produce a purely semantic explication to intentional identity statements. One consequence is that various extra-logical and pragmatic factors become of secondary concern; it is possible to solve the puzzle by logico-semantic methods, albeit somewhat radically renewed ones. (shrink)

Lorenzen's article has immediately been recognised as a landmark in the history of infinitary proof theory. We propose a translation and this introduction in order to publicise its approach and method of proof, without any ordinal assignment. It is best known for providing a constructive proof of consistency for ramified type theory without axiom of reducibility by showing that it is a part of a trivially consistent ‘inductive calculus’ that describes our knowledge of arithmetic without detour; the proof resorts only (...) to the inductive definition of formulas and theorems. It proposes a definition of semilattices, of distributive lattices, of pseudocomplemented semilattices, and of countably complete boolean algebras as deductive calculi, and constructs conservatively the respective free objects over a given preordered set. It illustrates that lattice theory is a bridge between algebra and logic: the construction of an element corresponds to a step in a proof. The fruitfulness of its use of the ω-rule is immediately recognised by Schütte. It triggers the analysis by Ackermann (1951) of the infinitary inductive definition of the accessibility predicate with the goal of proving transfinite induction up to ordinal terms beyond ϵ0. (shrink)

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)

Let M be a smooth, compact manifold of dimension n ≥ 5 and sectional curvature | K | ≤ 1. Let Met (M) = Riem(M)/Diff(M) be the space of Riemannian metrics on M modulo isometries. Nabutovsky and Weinberger studied the connected components of sublevel sets (and local minima) for certain functions on Met (M) such as the diameter. They showed that for every Turing machine T e , e ∈ ω, there is a sequence (uniformly effective in e) of homology (...) n-spheres {P k e } k ∈ ω which are also hypersurfaces, such that P k e is diffeomorphic to the standard n-sphere S n (denoted P k e ≈ diff S n ) iff T e halts on input k, and in this case the connected sum N k e =M ♯ P k e ≈ diff M , so N k e ∈ Met(M), and N k e is associated with a local minimum of the diameter function on Met(M) whose depth is roughly equal to the settling time σ e (k) of T e on inputs y i } ∈ ω of c.e. sets so that for all i the settling time of the associated Turing machine for A i dominates that for A i + 1 , even when the latter is composed with an arbitrary computable function. From this, Nabutovsky and Weinberger showed that the basins exhibit a "fractal" like behavior with extremely big basins, and very much smaller basins coming off them, and so on. This reveals what Nabutovsky and Weinberger describe in their paper on fractals as "the astonishing richness of the space of Riemannian metrics on a smooth manifold, up to reparametrization." From the point of view of logic and computability, the Nabutovsky-Weinberger results are especially interesting because: (1) they use c.e. sets to prove structural complexity of the geometry and topology, not merely undecidability results as in the word problem for groups, Hilbert's Tenth Problem, or most other applications; (2) they use nontrivial information about c.e. sets, the Soare sequence {A i } i ∈ ω above, not merely G öodel's c.e. noncomputable set K of the 1930's; and (3) without using computability theory there is no known proof that local minima exist even for simple manifolds like the torus T 5 (see §). (shrink)

Machine generated contents note: 1. The Computability Concept;2. General Recursive Functions;3. Programs and Machines;4. Recursive Enumerability;5. Connections to Logic;6. Degrees of Unsolvability;7. Polynomial-Time Computability;Appendix: Mathspeak;Appendix: Countability;Appendix: Decadic Notation;.

Several results about the game of cops and robbers on infinite graphs are analyzed from the perspective of computability theory. Computable robber-win graphs are constructed with the property that no computable robber strategy is a winning strategy, and such that for an arbitrary computable ordinal \, any winning strategy has complexity at least \}\). Symmetrically, computable cop-win graphs are constructed with the property that no computable cop strategy is a winning strategy. Locally finite infinite trees and graphs are explored. (...) The Turing computability of a binary relation used to classify cop-win graphs is studied, and the computational difficulty of determining the winner for locally finite computable graphs is discussed. (shrink)

The question about the scientific nature of computing has been widely debated with no universal consensus reached about its disciplinary status. Positions vary from acknowledging computing as the science of computers to defining it as a synthetic engineering discipline. In this paper, we aim at discussing the nature of computing from a methodological perspective. We consider, in particular, the nature and role of experiments in this field, whether they can be considered close to the traditional experimental scientific method or, instead, (...) they possess peculiar and unique features. We argue that this experimental perspective should be taken into account when discussing the status of computing. We critically survey how the experimental method has been conceived and applied in computing, and some open issues that could be tackled with the aid of the history of science, the philosophy of science, and the philosophy of technology. (shrink)

The familiar theories of physics have the feature that the application of the theory to make predictions in specific circumstances can be done by means of an algorithm. We propose a more precise formulation of this feature—one based on the issue of whether or not the physically measurable numbers predicted by the theory are computable in the mathematical sense. Applying this formulation to one approach to a quantum theory of gravity, there are found indications that there may exist no such (...) algorithms in this case. Finally, we discuss the issue of whether the existence of an algorithm to implement a theory should be adopted as a criterion for acceptable physical theories.“Can it then be that there is... something of use for unraveling the universe to be learned from the philosophy of computer design?” —J. A. Wheeler(1). (shrink)

Computational modeling has long been one of the traditional pillars of cognitive science. Unfortunately, the computer models of cognition being developed today have not kept up with the enormous changes that have taken place in computer technology and, especially, in human-computer interfaces. For all intents and purposes, modeling is still done today as it was 25, or even 35, years ago. Everyone still programs in his or her own favorite programming language, source code is rarely made available, accessibility of models (...) to non-programming researchers is essentially non-existent, and even for other modelers, the profusion of source code in a multitude of programming languages, written without programming guidelines, makes it almost impossible to access, check, explore, re-use, or continue to develop. It is high time to change this situation, especially since the tools are now readily available to do so. We propose that the modeling community adopt three simple guidelines that would ensure that computational models would be accessible to the broad range of researchers in cognitive science. We further emphasize the pivotal role that journal editors must play in making computational models accessible to readers of their journals. (shrink)

First-ever comprehensive introduction to the major new subject of quantum computing and quantum information.

Topologists Nabutovsky and Weinberger discovered how to embed computably enumerable (c.e.) sets into the geometry of Riemannian metrics modulo diffeomorphisms. They used the complexity of the settling times of the c.e. sets to exhibit a much greater complexity of the depth and density of local minima for the diameter function than previously imagined. Their results depended on the existence of certain sequences of c.e. sets, constructed at their request by Csima and Soare, whose settling times had the necessary dominating properties. (...) Although these computability results had been announced earlier, their proofs have been deferred until this paper. Computably enumerable sets have long been used to prove undecidability of mathematical problems such as the word problem for groups and Hilbert's Tenth Problem. However, this example by Nabutovsky and Weinberger is perhaps the first example of the use of c.e. sets to demonstrate specific mathematical or geometric complexity of a mathematical structure such as the depth and distribution of local minima. (shrink)

criticism defend the idea that an individual reader's understanding of a text can be a factor in determining the meaning of what is written in that text, and hence must play a part in determining the very identity conditions of works of literary art. We examine some accounts that have been given of the type of readerly ‘competence’ that a reader must have in order for her responses to a text to play this sort of constitutive role. We argue that (...) the analogy drawn by Stanley Fish and Jonathan Culler between literary and linguistic competence is philosophically flawed and explanatorily unfruitful, and that a better way of understanding the notion of literary competence can be constructed by appeal to some limitation results in formal logic and computability theory. (shrink)

This book is dedicated to a classic presentation of the theory of computable functions in the context of the foundations of mathematics. Part I motivates the study of computability with discussions and readings about the crisis in the foundations of mathematics in the early 20th century, while presenting the basic ideas of whole number, function, proof, and real number. Part II starts with readings from Turing and Post leading to the formal theory of recursive functions. Part III presents sufficient (...) formal logic to give a full development of Gödel's incompleteness theorems. Part IV considers the significance of the technical work with a discussion of Church's Thesis and readings on the foundations of mathematics. This new edition contains the timeline "Computability and Undecidability" as well as the essay "On mathematics". (shrink)

Several notions of computability-theoretic reducibility between [Formula: see text] principles have been studied. This paper contributes to the program of analyzing the behavior of versions of Ramsey’s Theorem and related principles under these notions. Among other results, we show that for each [Formula: see text], there is an instance of RT[Formula: see text] all of whose solutions have PA degree over [Formula: see text] and use this to show that König’s Lemma lies strictly between RT[Formula: see text] and RT[Formula: (...) see text] under one of these notions. We also answer two questions raised by Dorais, Dzhafarov, Hirst, Mileti, and Shafer on comparing versions of Ramsey’s Theorem and of the Thin Set Theorem with the same exponent but different numbers of colors. Still on the topic of the effect of the number of colors on the computable aspects of Ramsey-theoretic properties, we show that for each [Formula: see text], there is an [Formula: see text]-coloring [Formula: see text] of [Formula: see text] such that every [Formula: see text]-coloring of [Formula: see text] has an infinite homogeneous set that does not compute any infinite homogeneous set for [Formula: see text], and connect this result with the notion of infinite information reducibility introduced by Dzhafarov and Igusa. Next, we introduce and study a new notion that provides a uniform version of the idea of implication with respect to [Formula: see text]-models of RCA0, and related notions that allow us to count how many applications of a principle [Formula: see text] are needed to reduce another principle to [Formula: see text]. Finally, we fill in a gap in the proof of Theorem 12.2 in Cholak, Jockusch, and Slaman. (shrink)

Gualtiero Piccinini articulates and defends a mechanistic account of concrete, or physical, computation. A physical system is a computing system just in case it is a mechanism one of whose functions is to manipulate vehicles based solely on differences between different portions of the vehicles according to a rule defined over the vehicles. Physical Computation discusses previous accounts of computation and argues that the mechanistic account is better. Many kinds of computation are explicated, such as digital vs. analog, serial vs. (...) parallel, neural network computation, program-controlled computation, and more. Piccinini argues that computation does not entail representation or information processing although information processing entails computation. Pancomputationalism, according to which every physical system is computational, is rejected. A modest version of the physical Church-Turing thesis, according to which any function that is physically computable is computable by Turing machines, is defended. (shrink)

We study the computability-theoretic complexity and proof-theoretic strength of the following statements: (1) "If X is a well-ordering, then so is ε X ", and (2) "If X is a well-ordering, then so is φ(α, X)", where α is a fixed computable ordinal and φ represents the two-placed Veblen function. For the former statement, we show that ω iterations of the Turing jump are necessary in the proof and that the statement is equivalent to ${\mathrm{A}\mathrm{C}\mathrm{A}}_{0}^{+}$ over RCA₀. To prove (...) the latter statement we need to use ω α iterations of the Turing jump, and we show that the statement is equivalent to ${\mathrm{\Pi }}_{{\mathrm{\omega }}^{\mathrm{\alpha }}}^{0}{-\mathrm{C}\mathrm{A}}_{0}$ . Our proofs are purely computability-theoretic. We also give a new proof of a result of Friedman: the statement "if x is a well-ordering, then so is φ(x, 0)" is equivalent to ATR₀ over RCA₀. (shrink)

Computability logic (CL) is a recently launched program for redeveloping logic as a formal theory of computability, as opposed to the formal theory of truth that logic has more traditionally been. Formulas in it represent computational problems, "truth" means existence of an algorithmic solution, and proofs encode such solutions. Within the line of research devoted to finding axiomatizations for ever more expressive fragments of CL, the present paper introduces a new deductive system CL12 and proves its soundness and (...) completeness with respect to the semantics of CL. Conservatively extending classical predicate calculus and offering considerable additional expressive and deductive power, CL12 presents a reasonable, computationally meaningful, constructive alternative to classical logic as a basis for applied theories. To obtain a model example of such theories, this paper rebuilds the traditional, classical-logic-based Peano arithmetic into a computability-logic-based counterpart. Among the purposes of the present contribution is to provide a starting point for what, as the author wishes to hope, might become a new line of research with a potential of interesting findings—an exploration of the presumably quite unusual metatheory of CL-based arithmetic and other CL-based applied systems. (shrink)

The problem of computational complexity of semantics for some natural language constructions – considered in [M. Mostowski, D. Wojtyniak 2004] – motivates an interest in complexity of Ramsey quantifiers in finite models. In general a sentence with a Ramsey quantifier R of the following form Rx, yH(x, y) is interpreted as ∃A(A is big relatively to the universe ∧A2 ⊆ H). In the paper cited the problem of the complexity of the Hintikka sentence is reduced to the problem of computational (...) complexity of the Ramsey quantifier for which the phrase “A is big relatively to the universe” is interpreted as containing at least one representative of each equivalence class, for some given equvalence relation. In this work we consider quantifiers Rf, for which “A is big relatively to the universe” means “card(A) > f (n), where n is the size of the universe”. Following [Blass, Gurevich 1986] we call R mighty if Rx, yH(x, y) defines N P – complete class of finite models. Similarly we say that Rf is N P –hard if the corresponding class is N P –hard. We prove the following theorems. (shrink)

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 argue that these counterpossibles don’t just appear in the periphery of relative computability theory but instead they play an ineliminable role in the development of the theory. Finally, I present and discuss a model theory for these counterfactuals that is a straightforward extension of the familiar comparative similarity models. (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)

Proposals for quantum computation rely on superposed states implementing multiple computations simultaneously, in parallel, according to quantum linear superposition (e.g., Benioff, 1982; Feynman, 1986; Deutsch, 1985, Deutsch and Josza, 1992). In principle, quantum computation is capable of specific applications beyond the reach of classical computing (e.g., Shor, 1994). A number of technological systems aimed at realizing these proposals have been suggested and are being evaluated as possible substrates for quantum computers (e.g. trapped ions, electron spins, quantum dots, nuclear spins, etc., (...) see Table 1; Bennett, 1995; and Barenco, 1995). The main obstacle to realization of quantum computation is the problem of interfacing to the system (input, output) while also protecting the quantum state from environmental decoherence. If this problem can be overcome, then present day classical computers may evolve to quantum computers. (shrink)

Computational methods such as computer simulations, Monte Carlo methods, and agent-based modeling have become the dominant techniques in many areas of science. Extending Ourselves contains the first systematic philosophical account of these new methods, and how they require a different approach to scientific method. Paul Humphreys draws a parallel between the ways in which such computational methods have enhanced our abilities to mathematically model the world, and the more familiar ways in which scientific instruments have expanded our access to the (...) empirical world. This expansion forms the basis for a new kind of empiricism, better suited to the needs of science than the older anthropocentric forms of empiricism. Human abilities are no longer the ultimate standard of epistemological correctness.Humphreys also includes arguments for the primacy of properties rather than objects, the need to consider technological constraints when appraising scientific methods, and a detailed account of how the path from computational template to scientific application is constructed. This last feature allows us to hold a form of selective realism in which anti-realist arguments based on formal reconstructions of theories can be avoided. One important consequence of the rise of computational methods is that the traditional organization of the sciences is being replaced by an organization founded on computational templates.Extending Ourselves will be of interest to philosophers of science, epistemologists, and to anyone interested in the role played by computers in modern science. (shrink)

It is time for a new paper about open questions in the currently very active area of randomness and computability. Ambos-Spies and Kučera presented such a paper in 1999 [1]. All the question in it have been solved, except for one: is KL-randomness different from Martin-Löf randomness? This question is discussed in Section 6.Not all the questions are necessarily hard—some simply have not been tried seriously. When we think a question is a major one, and therefore likely to be (...) hard, we indicate this by the symbol ▶, the criterion being that it is of considerable interest and has been tried by a number of researchers. Some questions are close contenders here; these are marked by ▷. With few exceptions, the questions are precise. They mostly have a yes/no answer. However, there are often more general questions of an intuitive or even philosophical nature behind. We give an outline, indicating the more general questions.All sets will be sets of natural numbers, unless otherwise stated. These sets are identified with infinite strings over {0, 1}. Other terms used in the literature are sequence and real. (shrink)

This work is an attempt to lay foundations for a theory of interactive computation and bring logic and theory of computing closer together. It semantically introduces a logic of computability and sets a program for studying various aspects of that logic. The intuitive notion of computational problems is formalized as a certain new, procedural-rule-free sort of games between the machine and the environment, and computability is understood as existence of an interactive Turing machine that wins the game against (...) any possible environment. The formalism used as a specification language for computational problems, called the universal language, is a non-disjoint union of the formalisms of classical, intuitionistic and linear logics, with logical operators interpreted as certain—most basic and natural—operations on problems. Validity of a formula is understood as being “always computable”, and the set of all valid formulas is called the universal logic. The name “universal” is related to the potential of this logic to integrate, on the basis of one semantics, classical, intuitionistic and linear logics, with their seemingly unrelated or even antagonistic philosophies. In particular, the classical notion of truth turns out to be nothing but computability restricted to the formulas of the classical fragment of the universal language, which makes classical logic a natural syntactic fragment of the universal logic. The same appears to be the case for intuitionistic and linear logics . Unlike classical logic, these two do not have a good concept of truth, and the notion of computability restricted to the corresponding two fragments of the universal language, based on the intuitions that it formalizes, can well qualify as “intuitionistic truth” and “linear-logic truth”. The paper also provides illustrations of potential applications of the universal logic in knowledgebase, resourcebase and planning systems, as well as constructive applied theories. The author has tried to make this article easy to read. It is fully self-contained and can be understood without any specialized knowledge of any particular subfield of logic or computer science. (shrink)

In this survey we discuss work of Levin and V’yugin on collections of sequences that are non-negligible in the sense that they can be computed by a probabilistic algorithm with positive probability. More precisely, Levin and V’yugin introduced an ordering on collections of sequences that are closed under Turing equivalence. Roughly speaking, given two such collections $\mathcal {A}$ and $\mathcal {B}$, $\mathcal {A}$ is below $\mathcal {B}$ in this ordering if $\mathcal {A}\setminus \mathcal {B}$ is negligible. The degree structure associated (...) with this ordering, the Levin–V’yugin degrees, can be shown to be a Boolean algebra, and in fact a measure algebra. We demonstrate the interactions of this work with recent results in computability theory and algorithmic randomness: First, we recall the definition of the Levin–V’yugin algebra and identify connections between its properties and classical properties from computability theory. In particular, we apply results on the interactions between notions of randomness and Turing reducibility to establish new facts about specific LV-degrees, such as the LV-degree of the collection of 1-generic sequences, that of the collection of sequences of hyperimmune degree, and those collections corresponding to various notions of effective randomness. Next, we provide a detailed explanation of a complex technique developed by V’yugin that allows the construction of semi-measures into which computability-theoretic properties can be encoded. We provide two examples of the use of this technique by explicating a result of V’yugin’s about the LV-degree of the collection of Martin-Löf random sequences and extending the result to the LV-degree of the collection of sequences of DNC degree. (shrink)

Computation is central to the foundations of modern cognitive science, but its role is controversial. Questions about computation abound: What is it for a physical system to implement a computation? Is computation sufficient for thought? What is the role of computation in a theory of cognition? What is the relation between different sorts of computational theory, such as connectionism and symbolic computation? In this paper I develop a systematic framework that addresses all of these questions. Justifying the role of computation (...) requires analysis of implementation, the nexus between abstract computations and concrete physical systems. I give such an analysis, based on the idea that a system implements a computation if the causal structure of the system mirrors the formal structure of the computation. This account can be used to justify the central commitments of artificial intelligence and computational cognitive science: the thesis of computational sufficiency, which holds that the right kind of computational structure suffices for the possession of a mind, and the thesis of computational explanation, which holds that computation provides a general framework for the explanation of cognitive processes. The theses are consequences of the facts that (a) computation can specify general patterns of causal organization, and (b) mentality is an organizational invariant, rooted in such patterns. Along the way I answer various challenges to the computationalist position, such as those put forward by Searle. I close by advocating a kind of minimal computationalism, compatible with a very wide variety of empirical approaches to the mind. This allows computation to serve as a true foundation for cognitive science. (shrink)

Written by world-leading experts, this book draws together a number of important strands in contemporary approaches to the philosophical and scientific questions that emerge when dealing with the issues of computing, information, cognition and the conceptual issues that arise at their intersections. It discovers and develops the connections at the borders and in the interstices of disciplines and debates. This volume presents a range of essays that deal with the currently vigorous concerns of the philosophy of information, ontology creation and (...) control, bioinformation and biosemiotics, computational and post-computation approaches to the philosophy of cognitive science, computational linguistics, ethics, and education. (shrink)

The identification of an informal concept of ‘effective calculability’ with a rigorous mathematical notion like ‘recursiveness’ or ‘Turing computability’ is still viewed as problematic, and I think rightly so. I analyze three different and conflicting perspectives Gödel articulated in the three decades from 1934 to 1964. The significant shifts in Gödel's position underline the difficulties of the methodological issues surrounding the Church-Turing Thesis.

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)