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)

Since its conception nearly 20 years ago, Logic Programming - the idea of using logic as a programming language - has been developed to the point where it now plays an important role in areas such as database theory, artificial intelligence and software engineering. However, there are still many challenging research issues to be addressed and the UK branch of the Association for Logic Programming was set up to provide a forum where the flourishing research community could discuss important issues (...) of Logic Programming which were often by-passed at the large international conferences. This volume contains the twelve papers which were presented at the ALPUK's 3rd conference which was held in Edinburgh, 10-12 April 1991. The aim of the conference was to give a broad but detailed technical insight into the work currently being done in this field, both in the UK and by researchers as far afield as Canada and Bulgaria. The breadth of interest in this area of Computer Science is reflected in the range of the papers which cover - amongst other areas - massively parallel implementation, constraint logic programming, circuit modelling, algebraic proof of program properties, deductive databases, specialised editors and standardisation. The resulting volume gives a good overview of the current progress being made in the field and will be of interest to researchers and students of any aspects of logic programming, parallel computing or database techniques and management. (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)

Logic has pride of place in mathematics and its 20th century offshoot, computer science. Modern symbolic logic was developed, in part, as a way to provide a formal framework for mathematics: Frege, Peano, Whitehead and Russell, as well as Hilbert developed systems of logic to formalize mathematics. These systems were meant to serve either as themselves foundational, or at least as formal analogs of mathematical reasoning amenable to mathematical study, e.g., in Hilbert’s consistency program. Similar efforts continue, but have been (...) expanded by the development of sophisticated methods to study the properties of such systems using proof and model theory. In parallel with this evolution of logical formalisms as tools for articulating mathematical theories (broadly speaking), much progress has been made in the quest for a mechanization of logical inference and the investigation of its theoretical limits, culminating recently in the development of new foundational frameworks for mathematics with sophisticated computer-assisted proof systems. In addition, logical formalisms developed by logicians in mathematical and philosophical contexts have proved immensely useful in describing theories and systems of interest to computer scientists, and to some degree, vice versa. Three examples of the influence of logic in computer science are automated reasoning, computer verification, and type systems for programming languages. (shrink)

This book compiles and reviews the most prominent linguistic theories into a single source that serves as an essential reference for future solutions to one of the most important challenges of our age.

. Computational chemistry grew in a new era of “desktop modeling,” which coincided with a growing demand for modeling software, especially from the pharmaceutical industry. Parameterization of models in computational chemistry is an arduous enterprise, and we argue that this activity leads, in this specific context, to tensions among scientists regarding the epistemic opacity transparency of parameterized methods and the software implementing them. We relate one flame war from the Computational Chemistry mailing List in order to assess in detail the (...) relationships between modeling methods, parameterization, software and the various forms of their enclosure or disclosure. Our claim is that parameterization issues are an important and often neglected source of epistemic opacity and that this opacity is entangled in methods and software alike. Models and software must be addressed together to understand the epistemological tensions at stake. (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)

Textbook on Gödel’s incompleteness theorems and computability theory, based on the Open Logic Project. Covers recursive function theory, arithmetization of syntax, the first and second incompleteness theorem, models of arithmetic, second-order logic, and the lambda calculus.

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)

The computational view of mind rests on certain intuitions regarding the fundamental similarity between computation and cognition. We examine some of these intuitions and suggest that they derive from the fact that computers and human organisms are both physical systems whose behavior is correctly described as being governed by rules acting on symbolic representations. Some of the implications of this view are discussed. It is suggested that a fundamental hypothesis of this approach is that there is a natural domain of (...) human functioning that can be addressed exclusively in terms of a formal symbolic or algorithmic vocabulary or level of analysis. Much of the paper elaborates various conditions that need to be met if a literal view of mental activity as computation is to serve as the basis for explanatory theories. The coherence of such a view depends on there being a principled distinction between functions whose explanation requires that we posit internal representations and those that we can appropriately describe as merely instantiating causal physical or biological laws. In this paper the distinction is empirically grounded in a methodological criterion called the " cognitive impenetrability condition." Functions are said to be cognitively impenetrable if they cannot be influenced by such purely cognitive factors as goals, beliefs, inferences, tacit knowledge, and so on. Such a criterion makes it possible to empirically separate the fixed capacities of mind from the particular representations and algorithms used on specific occasions. In order for computational theories to avoid being ad hoc, they must deal effectively with the "degrees of freedom" problem by constraining the extent to which they can be arbitrarily adjusted post hoc to fit some particular set of observations. This in turn requires that the fixed architectural function and the algorithms be independently validated. It is argued that the architectural assumptions implicit in many contemporary models run afoul of the cognitive impenetrability condition, since the required fixed functions are demonstrably sensitive to tacit knowledge and goals. The paper concludes with some tactical suggestions for the development of computational cognitive theories. (shrink)

This systematic investigation of computation and mental phenomena by a noted psychologist and computer scientist argues that cognition is a form of computation, that the semantic contents of mental states are encoded in the same general way as computer representations are encoded. It is a rich and sustained investigation of the assumptions underlying the directions cognitive science research is taking. 1 The Explanatory Vocabulary of Cognition 2 The Explanatory Role of Representations 3 The Relevance of Computation 4 The Psychological Reality (...) of Programs: Strong Equivalence 5 Constraining Functional Architecture 6 The Bridge from Physical to Symbolic: Transduction 7 Functional Architecture and Analogue Processes 8 Mental Imagery and Functional Architecture 9 Epilogue: What is Cognitive Science the Science of? (shrink)

Computability and Logic has become a classic because of its accessibility to students without a mathematical background and because it covers not simply the staple topics of an intermediate logic course, such as Godel's incompleteness theorems, but also a large number of optional topics, from Turing's theory of computability to Ramsey's theorem. This 2007 fifth edition has been thoroughly revised by John Burgess. Including a selection of exercises, adjusted for this edition, at the end of each chapter, it offers a (...) simpler treatment of the representability of recursive functions, a traditional stumbling block for students on the way to the Godel incompleteness theorems. This updated edition is also accompanied by a website as well as an instructor's manual. (shrink)

This book addresses key conceptual issues relating to the modern scientific and engineering use of computer simulations. It analyses a broad set of questions, from the nature of computer simulations to their epistemological power, including the many scientific, social and ethics implications of using computer simulations. The book is written in an easily accessible narrative, one that weaves together philosophical questions and scientific technicalities. It will thus appeal equally to all academic scientists, engineers, and researchers in industry interested in questions (...) related to the general practice of computer simulations. (shrink)

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

What can computers do in principle? What are their inherent theoretical limitations? These are questions to which computer scientists must address themselves. The theoretical framework which enables such questions to be answered has been developed over the last fifty years from the idea of a computable function: intuitively a function whose values can be calculated in an effective or automatic way. This book is an introduction to computability theory (or recursion theory as it is traditionally known to mathematicians). Dr Cutland (...) begins with a mathematical characterisation of computable functions using a simple idealised computer (a register machine); after some comparison with other characterisations, he develops the mathematical theory, including a full discussion of non-computability and undecidability, and the theory of recursive and recursively enumerable sets. The later chapters provide an introduction to more advanced topics such as Gildel's incompleteness theorem, degrees of unsolvability, the Recursion theorems and the theory of complexity of computation. Computability is thus a branch of mathematics which is of relevance also to computer scientists and philosophers. Mathematics students with no prior knowledge of the subject and computer science students who wish to supplement their practical expertise with some theoretical background will find this book of use and interest. (shrink)

A Critique of Artificial Reason Hubert L. Dreyfus . HUBERT L. DREYFUS What Computers Still Can't Do Thi s One XZKQ-GSY-8KDG What. WHAT COMPUTERS STILL CAN'T DO Front Cover.

I propose to consider the question, "Can machines think?" This should begin with definitions of the meaning of the terms "machine" and "think." The definitions might be framed so as to reflect so far as possible the normal use of the words, but this attitude is dangerous, If the meaning of the words "machine" and "think" are to be found by examining how they are commonly used it is difficult to escape the conclusion that the meaning and the answer to (...) the question, "Can machines think?" is to be sought in a statistical survey such as a Gallup poll. But this is absurd. Instead of attempting such a definition I shall replace the question by another, which is closely related to it and is expressed in relatively unambiguous words. The new form of the problem can be described in terms of a game which we call the 'imitation game." It is played with three people, a man (A), a woman (B), and an interrogator (C) who may be of either sex. The interrogator stays in a room apart front the other two. The object of the game for the interrogator is to determine which of the other two is the man and which is the woman. He knows them by labels X and Y, and at the end of the game he says either "X is A and Y is B" or "X is B and Y is A." The interrogator is allowed to put questions to A and B. We now ask the question, "What will happen when a machine takes the part of A in this game?" Will the interrogator decide wrongly as often when the game is played like this as he does when the game is played between a man and a woman? These questions replace our original, "Can machines think?". (shrink)

The relationship between abstract formal procedures and the activities of actual physical systems has proved to be surprisingly subtle and controversial, and there are a number of competing accounts of when a physical system can be properly said to implement a mathematical formalism and hence perform a computation. I defend an account wherein computational descriptions of physical systems are high-level normative interpretations motivated by our pragmatic concerns. Furthermore, the criteria of utility and success vary according to our diverse purposes and (...) pragmatic goals. Hence there is no independent or uniform fact to the matter, and I advance the ‘anti-realist’ conclusion that computational descriptions of physical systems are not founded upon deep ontological distinctions, but rather upon interest-relative human conventions. Hence physical computation is a ‘conventional’ rather than a ‘natural’ kind. (shrink)

The Computational Theory of Mind (CTM) holds that cognitive processes are essentially computational, and hence computation provides the scientific key to explaining mentality. The Representational Theory of Mind (RTM) holds that representational content is the key feature in distinguishing mental from non-mental systems. I argue that there is a deep incompatibility between these two theoretical frameworks, and that the acceptance of CTM provides strong grounds for rejecting RTM. The focal point of the incompatibility is the fact that representational content is (...) extrinsic to formal procedures as such, and the intended interpretation of syntax makes no difference to the execution of an algorithm. So the unique 'content' postulated by RTM is superfluous to the formal procedures of CTM. And once these procedures are implemented in a physical mechanism, it is exclusively the causal properties of the physical mechanism that are responsible for all aspects of the system's behaviour. So once again, postulated content is rendered superfluous. To the extent that semantic content may appear to play a role in behaviour, it must be syntactically encoded within the system, and just as in a standard computational artefact, so too with the human mind/brain - it's pure syntax all the way down to the level of physical implementation. Hence 'content' is at most a convenient meta-level gloss, projected from the outside by human theorists, which itself can play no role in cognitive processing. (shrink)

Understanding Computers and Cognition presents an important and controversial new approach to understanding what computers do and how their functioning is related to human language, thought, and action. While it is a book about computers, Understanding Computers and Cognition goes beyond the specific issues of what computers can or can't do. It is a broad-ranging discussion exploring the background of understanding in which the discourse about computers and technology takes place. Understanding Computers and Cognition is written for a wide audience, (...) not just those professionals involved in computer design or artificial intelligence. It represents an important contribution to the ongoing discussion about what it means to be a machine, and what it means to be human. Book jacket. (shrink)

Classic text considersgeneral theory of computability, computable functions, operations on computable functions, Turing machines self-applied, unsolvable decision problems, applications of general theory, mathematical logic, Kleene hierarchy, computable functionals, classification of unsolvable decision problems and more.

This fourth edition of one of the classic logic textbooks has been thoroughly revised by John Burgess. The aim is to increase the pedagogical value of the book for the core market of students of philosophy and for students of mathematics and computer science as well. This book has become a classic because of its accessibility to students without a mathematical background, and because it covers not simply the staple topics of an intermediate logic course such as Godel's Incompleteness Theorems, (...) but also a large number of optional topics from Turing's theory of computability to Ramsey's theorem. John Burgess has now enhanced the book by adding a selection of problems at the end of each chapter, and by reorganising and rewriting chapters to make them more independent of each other and thus to increase the range of options available to instructors as to what to cover and what to defer. (shrink)

We present a computational evaluation of three hypotheses about sources of deficit in sentence comprehension in aphasia: slowed processing, intermittent deficiency, and resource reduction. The ACT-R based Lewis and Vasishth model is used to implement these three proposals. Slowed processing is implemented as slowed execution time of parse steps; intermittent deficiency as increased random noise in activation of elements in memory; and resource reduction as reduced spreading activation. As data, we considered subject vs. object relative sentences, presented in a self-paced (...) listening modality to 56 individuals with aphasia and 46 matched controls. The participants heard the sentences and carried out a picture verification task to decide on an interpretation of the sentence. These response accuracies are used to identify the best parameters that correspond to the three hypotheses mentioned above. We show that controls have more tightly clustered parameter values than IWA; specifically, compared to controls, among IWA there are more individuals with slow parsing times, high noise, and low spreading activation. We find that individual IWA show differential amounts of deficit along the three dimensions of slowed processing, intermittent deficiency, and resource reduction, overall, there is evidence for all three sources of deficit playing a role, and IWA have a more variable range of parameter values than controls. An important implication is that it may be meaningless to talk about sources of deficit with respect to an abstract verage IWA; the focus should be on the individual's differential degrees of deficit along different dimensions, and on understanding the causes of variability in deficit between participants. (shrink)

We begin by distinguishing computationalism from a number of other theses that are sometimes conflated with it. We also distinguish between several important kinds of computation: computation in a generic sense, digital computation, and analog computation. Then, we defend a weak version of computationalism—neural processes are computations in the generic sense. After that, we reject on empirical grounds the common assimilation of neural computation to either analog or digital computation, concluding that neural computation is sui generis. Analog computation requires continuous (...) signals; digital computation requires strings of digits. But current neuroscientific evidence indicates that typical neural signals, such as spike trains, are graded like continuous signals but are constituted by discrete functional elements (spikes); thus, typical neural signals are neither continuous signals nor strings of digits. It follows that neural computation is sui generis. Finally, we highlight three important consequences of a proper understanding of neural computation for the theory of cognition. First, understanding neural computation requires a specially designed mathematical theory (or theories) rather than the mathematical theories of analog or digital computation. Second, several popular views about neural computation turn out to be incorrect. Third, computational theories of cognition that rely on non-neural notions of computation ought to be replaced or reinterpreted in terms of neural computation. (shrink)

This book describes a program of research in computable structure theory. The goal is to find definability conditions corresponding to bounds on complexity which persist under isomorphism. The results apply to familiar kinds of structures (groups, fields, vector spaces, linear orderings Boolean algebras, Abelian p-groups, models of arithmetic). There are many interesting results already, but there are also many natural questions still to be answered. The book is self-contained in that it includes necessary background material from recursion theory (ordinal notations, (...) the hyperarithmetical hierarchy) and model theory (infinitary formulas, consistency properties). (shrink)

The main claim of this paper is that notions of implementation based on an isomorphic correspondence between physical and computational states are not tenable. Rather, ``implementation'' has to be based on the notion of ``bisimulation'' in order to be able to block unwanted implementation results and incorporate intuitions from computational practice. A formal definition of implementation is suggested, which satisfies theoretical and practical requirements and may also be used to make the functionalist notion of ``physical realization'' precise. The upshot of (...) this new definition of implementation is that implementation cannot distinguish isomorphic bisimilar from non-isomporphic bisimilar systems anymore, thus driving a wedge between the notions of causal and computational complexity. While computationalism does not seem to be affected by this result, the consequences for functionalism are not clear and need further investigations. (shrink)

Computational explanations focus on information processing required in specific cognitive capacities, such as perception, reasoning or decision-making. These explanations specify the nature of the information processing task, what information needs to be represented, and why it should be operated on in a particular manner. In this article, the focus is on three questions concerning the nature of computational explanations: What type of explanations they are, in what sense computational explanations are explanatory and to what extent they involve a special, “independent” (...) or “autonomous” level of explanation. In this paper, we defend the view computational explanations are genuine explanations, which track non-causal/formal dependencies. Specifically, we argue that they do not provide mere sketches for explanation, in contrast to what for example Piccinini and Craver :283–311, 2011) suggest. This view of computational explanations implies some degree of “autonomy” for the computational level. However, as we will demonstrate that does not make this view “computationally chauvinistic” in a way that Piccinini or Kaplan :339–373, 2011) have charged it to be. (shrink)

By applying research in artificial intelligence to problems in the philosophy of science, Paul Thagard develops an exciting new approach to the study of scientific reasoning. This approach uses computational ideas to shed light on how scientific theories are discovered, evaluated, and used in explanations. Thagard describes a detailed computational model of problem solving and discovery that provides a conceptually rich yet rigorous alternative to accounts of scientific knowledge based on formal logic, and he uses it to illuminate such topics (...) as the nature of concepts, hypothesis formation, analogy, and theory justification. (shrink)

Is the mathematical function being computed by a given physical system determined by the system’s dynamics? This question is at the heart of the indeterminacy of computation phenomenon (Fresco et al. [unpublished]). A paradigmatic example is a conventional electrical AND-gate that is often said to compute conjunction, but it can just as well be used to compute disjunction. Despite the pervasiveness of this phenomenon in physical computational systems, it has been discussed in the philosophical literature only indirectly, mostly with reference (...) to the debate over realism about physical computation and computationalism. A welcome exception is Dewhurst’s ([2018]) recent analysis of computational individuation under the mechanistic framework. He rejects the idea of appealing to semantic properties for determining the computational identity of a physical system. But Dewhurst seems to be too quick to pay the price of giving up the notion of computational equivalence. We aim to show that the mechanist need not pay this price. The mechanistic framework can, in principle, preserve the idea of computational equivalence even between two different enough kinds of physical systems, say, electrical and hydraulic ones. (shrink)

What is the mind? How does it work? How does it influence behavior? Some psychologists hope to answer such questions in terms of concepts drawn from computer science and artificial intelligence. They test their theories by modeling mental processes in computers. This book shows how computer models are used to study many psychological phenomena--including vision, language, reasoning, and learning. It also shows that computer modeling involves differing theoretical approaches. Computational psychologists disagree about some basic questions. For instance, should the mind (...) be modeled by digital computers, or by parallel-processing systems more like brains? Do computer programs consist of meaningless patterns, or do they embody (and explain) genuine meaning? (shrink)

The interplay between computability and randomness has been an active area of research in recent years, reflected by ample funding in the USA, numerous workshops, and publications on the subject. The complexity and the randomness aspect of a set of natural numbers are closely related. Traditionally, computability theory is concerned with the complexity aspect. However, computability theoretic tools can also be used to introduce mathematical counterparts for the intuitive notion of randomness of a set. Recent research shows that, conversely, concepts (...) and methods originating from randomness enrich computability theory.The book covers topics such as lowness and highness properties, Kolmogorov complexity, betting strategies and higher computability. Both the basics and recent research results are desribed, providing a very readable introduction to the exciting interface of computability and randomness for graduates and researchers in computability theory, theoretical computer science, and measure theory. (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)

The paper presents an extended argument for the claim that mental content impacts the computational individuation of a cognitive system (section 2). The argument starts with the observation that a cognitive system may simultaneously implement a variety of different syntactic structures, but that the computational identity of a cognitive system is given by only one of these implemented syntactic structures. It is then asked what are the features that determine which of implemented syntactic structures is the computational structure of the (...) system, and it is contended that these features are certain aspects of mental content. The argument helps (section 3) to reassess the thesis known as computational externalism, namely, the thesis that computational theories of cognition make essential reference to features in the individual's environment. It is suggested that the familiar arguments for computational externalism?which rest on thought experiments and on exegesis of Marr's theories of vision?are unconvincing, but that they can be improved. A reconstruction of the visex/audex thought experiment is offered in section 3.1. An outline of a novel interpretation of Marr's theories of vision is presented in section 3.2. The corrected arguments support the claim that computational theories of cognition are intentional. Computational externalism is still pending, however, upon the thesis that psychological content is extrinsic. (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)

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)

Provability, Computability and Reflection.

The computational theory of mind construes the mind as an information-processor and cognitive capacities as essentially representational capacities. Proponents of the view claim a central role for representational content in computational models of these capacities. In this paper I argue that the standard view of the role of representational content in computational models is mistaken; I argue that representational content is to be understood as a gloss on the computational characterization of a cognitive process.Keywords: Computation; Representational content; Cognitive capacities; Explanation.

Covering the basics as well as recent research results, this book provides a very readable introduction to the exciting interface of computability and ...

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)

Computability theory originated with the seminal work of Gödel, Church, Turing, Kleene and Post in the 1930s. This theory includes a wide spectrum of topics, such as the theory of reducibilities and their degree structures, computably enumerable sets and their automorphisms, and subrecursive hierarchy classifications. Recent work in computability theory has focused on Turing definability and promises to have far-reaching mathematical, scientific, and philosophical consequences. Written by a leading researcher, Computability Theory provides a concise, comprehensive, and authoritative introduction to contemporary (...) computability theory, techniques, and results. The basic concepts and techniques of computability theory are placed in their historical, philosophical and logical context. This presentation is characterized by an unusual breadth of coverage and the inclusion of advanced topics not to be found elsewhere in the literature at this level. The book includes both the standard material for a first course in computability and more advanced looks at degree structures, forcing, priority methods, and determinacy. The final chapter explores a variety of computability applications to mathematics and science. Computability Theory is an invaluable text, reference, and guide to the direction of current research in the field. Nowhere else will you find the techniques and results of this beautiful and basic subject brought alive in such an approachable and lively way. (shrink)

According to some philosophers, computational explanation is proprietary
to psychology—it does not belong in neuroscience. But neuroscientists routinely offer computational explanations of cognitive phenomena. In fact, computational explanation was initially imported from computability theory into the science of mind by neuroscientists, who justified this move on neurophysiological grounds. Establishing the legitimacy and importance of computational explanation in neuroscience is one thing; shedding light on it is another. I raise some philosophical questions pertaining to computational explanation and outline some promising answers that (...) are being developed by a number of authors. (shrink)