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)

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)

We investigate the connections between computability theory and Nonstandard Analysis. In particular, we investigate the two following topics and show that they are intimately related. A basic property of Cantor space$2^ $ is Heine–Borel compactness: for any open covering of $2^ $, there is a finite subcovering. A natural question is: How hard is it to compute such a finite subcovering? We make this precise by analysing the complexity of so-called fan functionals that given any $G:2^ \to $, (...) output a finite sequence $\langle f_0, \ldots,f_n \rangle $ in $2^ $ such that the neighbourhoods defined from $\overline {f_i } G\left$ for $i \le n$ form a covering of $2^ $. A basic property of Cantor space in Nonstandard Analysis is Abraham Robinson’s nonstandard compactness, i.e., that every binary sequence is “infinitely close” to a standard binary sequence. We analyse the strength of this nonstandard compactness property of Cantor space, compared to the other axioms of Nonstandard Analysis and usual mathematics.Our study of yields exotic objects in computability theory, while leads to surprising results in Reverse Mathematics. We stress that and are highly intertwined, i.e., our study is holistic in nature in that results in computability theory yield results in Nonstandard Analysis and vice versa. (shrink)

Over the past thirty years, it is been common to hear the mind likened to a digital computer. This essay is concerned with a particular philosophical view that holds that the mind literally is a digital computer (in a specific sense of “computer” to be developed), and that thought literally is a kind of computation. This view—which will be called the “Computational Theory of Mind” (CTM)—is thus to be distinguished from other and broader attempts to connect the mind with (...) computation, including (a) various enterprises at modeling features of the mind using computational modeling techniques, and (b) employing some feature or features of production-model computers (such as the stored program concept, or the distinction between hardware and software) merely as a guiding metaphor for understanding some feature of the mind. This entry is therefore concerned solely with the Computational Theory of Mind (CTM) proposed by Hilary Putnam [1961] and developed most notably for philosophers by Jerry Fodor [1975, 1980, 1987, 1993]. The senses of ‘computer’ and ‘computation’ employed here are technical; the main tasks of this entry will therefore be to elucidate: (a) the technical sense of ‘computation’ that is at issue, (b) the ways in which it is claimed to be applicable to the mind, (c) the philosophical problems this understanding of the mind is claimed to solve, and (d) the major criticisms that have accrued to this view. (shrink)

The Computational Theory of Mind (CTM) holds that the mind is a computer and that cognition is the manipulation of representations. CTM is commonly viewed as the main hypothesis in cognitive science, with classical CTM (related to the Language of Thought Hypothesis) being the most popular variant. However, other computational accounts of the mind either reject LOTH or do not subscribe to RTM. CTM proponents argue that it clarifies how thought and content are causally relevant in the physical world, (...) and they frame this argument in terms of the physical symbol hypothesis, formalism, or syntactic engines. This article focuses on specific problems with CTM, with four main sections covering the introduction of the three main variants of CTM, the most important conceptions of computational explanation in cognitive science, skeptical arguments against CTM raised by Hilary Putnam, and common objections to CTM. (shrink)

Very plausibly, nothing can be a genuine computing system unless it meets an input-sensitivity requirement. Otherwise all sorts of objects, such as rocks or pails of water, can count as performing computations, even such as might suffice for mentality—thus threatening computationalism about the mind with panpsychism. Maudlin in J Philos 86:407–432, ( 1989 ) and Bishop ( 2002a , b ) have argued, however, that such a requirement creates difficulties for computationalism about conscious experience, putting it in conflict with the (...) very intuitive thesis that conscious experience supervenes on physical activity. Klein in Synthese 165:141–153, ( 2008 ) proposes a way for computationalists about experience to avoid panpsychism while still respecting the supervenience of experience on activity. I argue that his attempt to save computational theories of experience from Maudlin’s and Bishop’s critique fails. (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)

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 computability theory and provides an extensive treatment of data structures and program correctness. It makes accessible some of the author's work on generalized recursion theory, particularly the material on the logic programming language PROLOG, which is currently of great interest. Fitting considers the relation of PROLOG logic programming to the LISP type of language.

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;.

The widespread belief that the mind is a computer embodies a failure to distinguish between computers and information-processing systems. Minds are information-processing systems, but they are not computers.

Daniele Mundici and Wilfred Sieg. Computability Theory.

This study explores the dynamic feature of organizational citizenship behaviors under the condition of challenge stressors, as this has not been addressed by previous research. Combining the cybernetic theory of stress and social exchange theory, this study builds a dynamic computational model regarding the circular causality between challenge stressors and organizational citizenship behaviors. By conducting a series of simulation experiments, we validated and demonstrated important questions regarding organizational citizenship behaviors. Specifically, when both the initial value of challenge stressors (...) and the importance of challenge appraisal are higher, organizational citizenship behaviors tend to show a sharped inverted U shape at the early stage. When both the equilibrium level of job satisfaction and the initial value of challenge stressors are higher, organizational citizenship behaviors will show an inverted N shape over time. The number and frequency of assigned challenge tasks have an interactive effect on the accumulation of organizational citizenship behaviors within a period. Our theory contributes to identifying the dynamic relationship between challenge stressors and organizational citizenship behaviors. Findings from dynamic computational theory can offer suggestions for managers to encourage employees’ engagement in organizational citizenship behaviors. (shrink)

Narrative passages told from a character's perspective convey the character's thoughts and perceptions. We present a discourse process that recognizes characters'.

In the late 1960s and early 1970s David Marr produced three astonishing papers in which he gave a detailed account of how the fine structure and known cell types of the cerebellum, hippocampus and neocortex perform the functions that they do. Marr went on to become one of the main founders of Computational Neuroscience. In his classic work 'Vision' he distinguished between the computational, algorithmic, and implementational levels, and the three early theories concerned implementation. However, they were produced when Neuroscience (...) was in its infancy.Now that so much more is known, it is timely to revisit these early theories to see to what extent they are still valid and what needs to be altered to produce viable theories that stand up to current evidence. This book brings together some of the most distinguished scientists in their fields to evaluate Marr's legacy. (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)

In this paper I review some leading developments in the empirical theory of affect. I argue that (1) affect is a distinct perceptual representation governed system, and (2) that there are significant modular factors in affect. The paper concludes with the observation thatfeeler (affective perceptual system) may be a natural kind within cognitive science. The main purpose of the paper is to explore some hitherto unappreciated connections between the theory of affect and the computational theory of mind.

Despite its significance in neuroscience and computation, McCulloch and Pitts's celebrated 1943 paper has received little historical and philosophical attention. In 1943 there already existed a lively community of biophysicists doing mathematical work on neural networks. What was novel in McCulloch and Pitts's paper was their use of logic and computation to understand neural, and thus mental, activity. McCulloch and Pitts's contributions included (i) a formalism whose refinement and generalization led to the notion of finite automata (an important formalism in (...) computability theory), (ii) a technique that inspired the notion of logic design (a fundamental part of modern computer design), (iii) the first use of computation to address the mind–body problem, and (iv) the first modern computational theory of mind and brain. (shrink)

Although Kurt Gödel does not figure prominently in the history of computabilty theory, he exerted a significant influence on some of the founders of the field, both through his published work and through personal interaction. In particular, Gödel’s 1931 paper on incompleteness and the methods developed therein were important for the early development of recursive function theory and the lambda calculus at the hands of Church, Kleene, and Rosser. Church and his students studied Gödel 1931, and Gödel taught (...) a seminar at Princeton in 1934. Seen in the historical context, Gödel was an important catalyst for the emergence of computability theory in the mid 1930s. (shrink)

The target article claims that we should speak in code to understand property, because natural language is too ambiguous. Yet the best computer programmers tell us the opposite: Arbitrary code is too ambiguous, so we should use natural language for variables, functions, and classes. I discuss how meaningless code makes Boyer's theory too enigmatic to properly debate.

The “Slicing Problem” is a thought experiment that raises questions for substrate-neutral computational theories of consciousness, including those that specify a certain causal structure for the computation like Integrated Information Theory. The thought experiment uses water-based logic gates to construct a computer in a way that permits cleanly slicing each gate and connection in half, creating two identical computers each instantiating the same computation. The slicing can be reversed and repeated via an on/off switch, without changing the amount of (...) matter in the system. The question is what do different computational theories of consciousness believe is happening to the number and nature of individual conscious units as this switch is toggled. Under a token interpretation, there are now two discrete conscious entities; under a type interpretation, there may remain only one. Both interpretations lead to different implications depending on the adopted theoretical stance. Any route taken either allows mechanisms for “consciousness-multiplying exploits” or requires ambiguous boundaries between conscious entities, raising philosophical and ethical questions for theorists to consider. We discuss resolutions under different theories of consciousness for those unwilling to accept consciousness-multiplying exploits. In particular, we specify three features that may help promising physicalist theories to navigate such thought experiments. (shrink)

Moods have global and profound effects on our thoughts, motivations and behavior. To understand human behavior and cognition fully, we must understand moods. In this paper I critically examine and reject the methodology of conventional ?cognitive theories? of affect. I lay the foundations of a new theory of moods that identifies them with processes of our cognitive functional architecture. Moods differ fundamentally from some of our other affective states and hence require distinct explanatory tools. The computational theory of (...) mood I propose places them within the context of other mental phenomena and is consistent with the empirical data on moods. (shrink)

A standing challenge for the science of mind is to account for the datum that every mind faces in the most immediate – that is, unmediated – fashion: its phenomenal experience. The complementary tasks of explaining what it means for a system to give rise to experience and what constitutes the content of experience (qualia) in computational terms are particularly challenging, given the multiple realizability of computation. In this paper, we identify a set of conditions that a computational theory (...) must satisfy for it to constitute not just a sufficient but a necessary, and therefore naturalistic and intrinsic, explanation of qualia. We show that a common assumption behind many neurocomputational theories of the mind, according to which mind states can be formalized solely in terms of instantaneous vectors of activities of representational units such as neurons, does not meet the requisite conditions, in part because it relies on inactive units to shape presently experienced qualia and implies a homogeneous representation space, which is devoid of intrinsic structure. We then sketch a naturalistic computational theory of qualia, which posits that experience is realized by dynamical activity-space trajectories (rather than points) and that its richness is measured by the representational capacity of the trajectory space in which it unfolds. (shrink)

We don't yet have adequate theories of what the human mind is representing when it represents a social group. Worse still, many people think we do. This mistaken belief is a consequence of the state of play: Until now, researchers have relied on their own intuitions to link up the concept social group on the one hand and the results of particular studies or models on the other. While necessary, this reliance on intuition has been purchased at a considerable cost. (...) When looked at soberly, existing theories of social groups are either literal, but not remotely adequate, or simply metaphorical. Intuition is filling in the gaps of an explicit theory. This paper presents a computational theory of what, literally, a group representation is in the context of conflict: It is the assignment of agents to specific roles within a small number of triadic interaction types. This “mental definition” of a group paves the way for a computational theory of social groups – in that it provides a theory of what exactly the information-processing problem of representing and reasoning about a group is. For psychologists, this paper offers a different way to conceptualize and study groups, and suggests that a non-tautological definition of a social group is possible. For cognitive scientists, this paper provides a computational benchmark against which natural and artificial intelligences can be held. (shrink)

A new account of the of the laws of nature based upon Algorithmic Information Theory.

In this comment on Joshua Greene's essay, The Secret Joke of Kant's Soul, I argue that a notable weakness of Greene's approach to moral psychology is its neglect of computational theory. A central problem moral cognition must solve is to recognize (i.e., compute representations of) the deontic status of human acts and omissions. How do people actually do this? What is the theory which explains their practice?

Our digital technologies have inspired new ways of thinking about old religious topics. Digitalists include computer scientists, transhumanists, singularitarians, and futurists. Digitalists have worked out novel and entirely naturalistic ways of thinking about bodies, minds, souls, universes, gods, and life after death. Your Digital Afterlives starts with three digitalist theories of life after death. It examines personality capture, body uploading, and promotion to higher levels of simulation. It then examines the idea that reality itself is ultimately a system of self-surpassing (...) computations. On that view, you will have infinitely many digital lives across infinitely many digital worlds. Your Digital Afterlives looks at superhuman bodies and infinite bodies. Thinking of nature in purely computational terms has the potential to radically and positively change our understanding of life after death. (shrink)

We discuss a research project that develops and applies algorithms for computational contextual vocabulary acquisition (CVA): learning the meaning of unknown words from context. We try to unify a disparate literature on the topic of CVA from psychology, first- and secondlanguage acquisition, and reading science, in order to help develop these algorithms: We use the knowledge gained from the computational CVA system to build an educational curriculum for enhancing students’ abilities to use CVA strategies in their reading of science texts (...) at the middle-school and college undergraduate levels. The knowledge gained from case studies of students using our CVA techniques feeds back into further development of our computational theory. Keywords: artificial intelligence, knowledge representation, reading, reasoning, science education, vocabulary acquisition. (shrink)

The case for computationalism about the mind is in doubt when we acknowledge that there are mental phenomena that require, for a proper accounting, that we get below the level of symbol processing. Such phenomena show us that a computational theory of mind cannot be complete. Chief among these phenomena is emotion.

It is often helpful in metaphysics to reflect upon the principles that govern how existence claims are made in logic and mathematics. Consider, for example, the different ways in which mathematicians construct inductive definitions. In order to provide an inductive definition of a class of mathematical entities, one must first define a base class and then stipulate further conditions for inclusion by reference to the properties of members of the base class. These conditions can be deflationary, so that the target (...) class is a subclass of the base class, or inflationary, so that the base class is an important subclass of the target class. For example, in defining the set of well-formed sentences of first order logic, one can begin with the set of all possible strings and, in a deflationary manner, exclude the nonsentences. Or one can begin with the set of atomic formulae, and in an inflationary manner, build more complicated sentences out of the atomic formulae. (shrink)

David Marr's theory of vision has been widely cited by philosophers and psychologists. I have three projects in this paper. First, I try to offer a perspicuous characterization of Marr's theory. Next, I consider the implications of Marr's work for some currently popular philosophies of psychology, specifically, the "hegemony of neurophysiology view", the theories of Jerry Fodor, Daniel Dennett, and Stephen Stich, and the view that perception is permeated by belief. In the last section, I consider what the (...) phenomenon of vision must be like for Marr's project to succeed. (shrink)

The connections between mathematical logic and combinatorics have a rich history. This paper focuses on one aspect of this relationship: understanding the strength, measured using the tools of computability theory and reverse mathematics, of various partition theorems. To set the stage, recall two of the most fundamental combinatorial principles, König's Lemma and Ramsey's Theorem. We denote the set of natural numbers by ω and the set of finite sequences of natural numbers by ω<ω. We also identify each n (...) ∈ ω with its set of predecessors, so n = {0, 1, 2, …, n − 1}. (shrink)