Logic and Computation is concerned with techniques for formal theorem-proving, with particular reference to Cambridge LCF (Logic for ComputableFunctions). Cambridge LCF is a computer program for reasoning about computation. It combines methods of mathematical logic with domain theory, the basis of the denotational approach to specifying the meaning of statements in a programming language. This book consists of two parts. Part I outlines the mathematical preliminaries: elementary logic and domain theory. They are explained at an intuitive level, (...) giving references to more advanced reading. Part II provides enough detail to serve as a reference manual for Cambridge LCF. It will also be a useful guide for implementors of other programs based on the LCF approach. (shrink)
"A valuable collection both for original source material as well as historical formulations of current problems."-- The Review of Metaphysics "Much more than a mere collection of papers . . . a valuable addition to the literature."-- Mathematics of Computation An anthology of fundamental papers on undecidability and unsolvability by major figures in the field, this classic reference opens with Godel's landmark 1931 paper demonstrating that systems of logic cannot admit proofs of all true assertions of arithmetic. Subsequent papers by (...) Godel, Church, Turing, and Post single out the class of recursive functions as computable by finite algorithms. Additional papers by Church, Turing, and Post cover unsolvable problems from the theory of abstract computing machines, mathematical logic, and algebra, and material by Kleene and Post includes initiation of the classification theory of unsolvable problems. Suitable for graduate and undergraduate courses. 1965 ed. (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.
This is an annotated reading list on the beginning elements of the theory of computablefunctions. It is now structured so as to complement the first eight lectures of Thomas Forster’s Part III course in Lent 2011 (see the first four chapters of his evolving handouts).
Horsten and Roelants have raised a number of important questions about my analysis of effective procedures and my evaluation of the Church-Turing thesis. They suggest that, on my account, effective procedures cannot enter the mathematical world because they have a built-in component of causality, and, hence, that my arguments against the Church-Turing thesis miss the mark. Unfortunately, however, their reasoning is based upon a number of misunderstandings. Effective mundane procedures do not, on my view, provide an analysis of ourgeneral concept (...) of an effective procedure; mundane procedures and Turing machine procedures are different kinds of procedure. Moreover, the same sequence ofparticular physical action can realize both a mundane procedure and a Turing machine procedure; it is sequences of particular physical actions, not mundane procedures, which enter the world of mathematics. I conclude by discussing whether genuinely continuous physical processes can enter the world of real numbers and compute real-valued functions. I argue that the same kind of correspondence assumptions that are made between non-numerical structures and the natural numbers, in the case of Turing machines and personal computers, can be made in the case of genuinely continuous, physical processes and the real numbers. (shrink)
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 computablefunctions 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 primary problem in the area of natural language processing has been semantic analysis. This book looks at the semantics of natural languages in context. It presents an approach to the computational processing of English text that combines current theories of knowledge representation and reasoning in Artificial Intelligence with the latest linguistic views of lexical semantics. The book will interest postgraduates and researchers in computational linguistics as well as industrial research groups specializing in natural language processing.
The productivity of (human) information processing as an economic activity is a question that is raising some interest. Using Marschak's evaluation framework, Radner and Stiglitz have shown that, under certain conditions, the production function of this activity has increasing marginal returns in its initial stage. This paper shows that, under slightly different conditions, this information processing function has repeated convexities with ongoing processing activity. Even for smooth changes in the signals' likelihoods, the function is only piecewise smooth (...) with non-differentiable convexities at points of conditional changes of action. For linear likelihood functions the processing value proves to be piecewise linear with convexities at these levels. (shrink)
The paper has three parts. First, a survey and analysis is given ofthe structure of individual rights in the recent EU Directive ondata protection. It is argued that at the core of this structure isan unexplicated notion of what the data subject can `reasonablyexpect' concerning the further processing of information about himor herself. In the second part of the paper it is argued thattheories of privacy popular among philosophers are not able to shed much light on the issues (...) treated in the Directive, whichare, arguably, among the central problems pertaining to theprotection of individual rights in the information society. Inthe third part of the paper, some suggestions are made for a richerphilosophical theory of data protection and privacy. It is arguedthat this account is better suited to the task of characterizingthe central issues raised by the Directive. (shrink)
We study the complexity of (finitely-valued and transfinitely-valued) Euclidean functions for computable Euclidean domains. We examine both the complexity of the minimal Euclidean function and any Euclidean function. Additionally, we draw some conclusions about the proof-theoretical strength of minimal Euclidean functions in terms of reverse mathematics.
Classic text considersgeneral theory of computability, computablefunctions, operations on computablefunctions, Turing machines self-applied, unsolvable decision problems, applications of general theory, mathematical logic, Kleene hierarchy, computable functionals, classification of unsolvable decision problems and more.
We extend the concept that life is an informational phenomenon, at every level of organisation, from molecules to the global ecological system. According to this thesis: (a) living is information processing, in which memory is maintained by both molecular states and ecological states as well as the more obvious nucleic acid coding; (b) this information processing has one overall function—to perpetuate itself; and (c) the processing method is filtration (cognition) of, and synthesis of, information at lower levels (...) to appear at higher levels in complex systems (emergence). We show how information patterns, are united by the creation of mutual context, generating persistent consequences, to result in ‘functional information’. This constructive process forms arbitrarily large complexes of information, the combined effects of which include the functions of life. Molecules and simple organisms have already been measured in terms of functional information content; we show how quantification may be extended to each level of organisation up to the ecological. In terms of a computer analogy, life is both the data and the program and its biochemical structure is the way the information is embodied. This idea supports the seamless integration of life at all scales with the physical universe. The innovation reported here is essentially to integrate these ideas, basing information on the ‘general definition’ of information, rather than simply the statistics of information, thereby explaining how functional information operates throughout life. (shrink)
Lexical semantics has become a major research area within computational linguistics, drawing from psycholinguistics, knowledge representation, computer algorithms and architecture. Research programmes whose goal is the definition of large lexicons are asking what the appropriate representation structure is for different facets of lexical information. Among these facets, semantic information is probably the most complex and the least explored.Computational Lexical Semantics is one of the first volumes to provide models for the creation of various kinds of computerised lexicons for the automatic (...) treatment of natural language, with applications to machine translation, automatic indexing, and database front-ends, knowledge extraction, among other things. It focuses on semantic issues, as seen by linguists, psychologists, and computer scientists. Besides describing academic research, it also covers ongoing industrial projects. (shrink)
Quantum mechanical measurements on a physical system are represented by observables - Hermitian operators on the state space of the observed system. It is an important question whether all observables may be realized, in principle, as measurements on a physical system. Dirac’s influential text ( [1], page 37) makes the following assertion on the question: The question now presents itself – Can every observable be measured? The answer theoretically is yes. In practice it may be very awkward, or perhaps even (...) beyond the ingenuity of the experimenter, to devise an apparatus which could measure some particular observable, but the theory always allows one to imagine that the measurement can be made. This Letter re-examines the question of whether it is possible, even in principle, to measure every quantum mechanical observable. Unexpectedly, ideas from com-. (shrink)
The LNCS series reports state-of-the-art results in computer science research, development, and education, at a high level and in both printed and electronic form.
There are currently considerable confusion and disarray about just how we should view computationalism, connectionism and dynamicism as explanatory frameworks in cognitive science. A key source of this ongoing conflict among the central paradigms in cognitive science is an equivocation on the notion of computation simpliciter. ‘Computation’ is construed differently by computationalism, connectionism, dynamicism and computational neuroscience. I claim that these central paradigms, properly understood, can contribute to an integrated cognitive science. Yet, before this claim can be defended, a better (...) understanding of ‘computation’ is required. ‘Digital computation’ is an ambiguous concept. It is not just the classical dichotomy between analogue and digital computation that is the basis for the equivocation on ‘computation’ simpliciter in cognitive science, but also the diversity of extant accounts of digital computation. There are many answers on what it takes for a system to perform digital computation. Answers to this problem range from Turing machine computation, through the formal manipulation of symbols, the execution of algorithms and others, to the strong-pancomputational thesis, according to which every physical system computes every Turing-computable function. Despite some overlap among them, extant accounts of concrete digital computation are non-equivalent, thus, rendering ‘digital computation’ ambiguous. The objective of this dissertation is twofold. First, it is to promote a clearer understanding of concrete digital computation. Accordingly, my main thesis is that not only are extant accounts of concrete digital computation non-equivalent, but most of them are inadequate. I show that these accounts are not just intensionally different (this is quite trivially the case), but also extensionally distinct. In the course of examining several key accounts of concrete digital computation, I propose the instructional information processing account, according to which digital computation is the processing of discrete data in accordance with finite instructional information. The second objective is to establish the foundational role of computation in cognitive science whilst rejecting the purported representational nature of 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)
Since the cognitive revolution, it’s 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 theoristError: Illegal entry in bfrange (...) block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMaps of cognition be explicit and careful in choosing 1 notions of computation and information and connecting them together. Much confusion can be avoided by doing so. Keywords: computation, information processing, computationalism, computational theory of mind, cognitivism. (shrink)
Machine generated contents note: -- Acknowledgements -- Disrupting the Impression of Stability in the Gender-Technology Relation -- Changing Images of Computers and its Users since 1980 -- Discursive Developments Within Computer Education -- Variations in Gender-ICT Relations Among Male and Female Computer Students -- Stories About Individual Change and Transformation -- Layered Meanings and Differences Within -- Is there an Elsewhere? -- References -- Endnotes -- Index.
Computation and information processing are among the most fundamental notions in cognitive science. They are also among the most imprecisely discussed. Many cognitive scientists take it for granted that cognition involves computation, information processing, or both – although others disagree vehemently. Yet different cognitive scientists use ‘computation’ and ‘information processing’ to mean different things, sometimes without realizing that they do. In addition, computation and information processing are surrounded by several myths; first and foremost, that they are (...) the same thing. In this paper, we address this unsatisfactory state of affairs by presenting a general and theory-neutral account of computation and information processing. We also apply our framework by analyzing the relations between computation and information processing on one hand and classicism and connectionism on the other. We defend the relevance to cognitive science of both computation, in a generic sense that we fully articulate for the first time, and information processing, in three important senses of the term. Our account advances some foundational debates in cognitive science by untangling some of their conceptual knots in a theory-neutral way. By leveling the playing field, we pave the way for the future resolution of the debates’ empirical aspects. (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. Including a selection of exercises, adjusted for this edition, at the end of each chapter, it offers a new and simpler treatment of the representability of recursive functions, (...) a traditional stumbling block for students on the way to the Godel incompleteness theorems. (shrink)
This paper draws attention to an increasingly common method of using computer simulations to establish evidential standards in physics. By simulating an actual detection procedure on a computer, physicists produce patterns of data (‘signatures’) that are expected to be observed if a sought-after phenomenon is present. Claims to detect the phenomenon are evaluated by comparing such simulated signatures with actual data. Here I provide a justification for this practice by showing how computer simulations establish the reliability of detection (...) procedures. I argue that this use of computer simulation undermines two fundamental tenets of the Bogen–Woodward account of evidential reasoning. Contrary to Bogen and Woodward’s view, computer-simulated signatures rely on ‘downward’ inferences from phenomena to data. Furthermore, these simulations establish the reliability of experimental setups without physically interacting with the apparatus. I illustrate my claims with a study of the recent detection of the superfluid-to-Mott-insulator phase transition in ultracold atomic gases. (shrink)
This introduction to certain mathematical topics central to theoretical computer science treats computability and recursive functions, formal languages and automata, computational complexity, and cruptography. The presentation is essentially self-contained with detailed proofs of all statements provided. Although it begins with the basics, it proceeds to some of the most important recent developments in theoretical computer science.
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. Including a selection of exercises, adjusted for this edition, at the end of each chapter, it offers a new and simpler treatment of the representability of recursive functions, (...) a traditional stumbling block for students on the way to the Godel incompleteness theorems. (shrink)
Behrendt & Young (B&Y) propose that a dysfunction in the reticular thalamic nucleus contributes to disinhibition of specific thalamic nuclei, allowing cortical attention mechanisms to engage thalamic relay neurons, causing underconstrained activation of the cortex and hallucinations. The following hypothesis challenges the notion of impaired sensory gating by providing the alternative view that hypofrontality reduces the power of incoming stimuli, causing internal drives to override consciousness, resulting in hallucinations.
Raymond Turner first provides a logical framework for specification and the design of specification languages, then uses this framework to introduce and study ...
Recent findings indicate that the constituting digits of multi-digit numbers are processed, decomposed into units, tens, and so on, rather than integrated into one entity. This is suggested by interfering effects of unit digit processing on two-digit number comparison. In the present study, we extended the computational model for two-digit number magnitude comparison of Moeller, Huber, Nuerk, and Willmes (2011a) to the case of three-digit number comparison (e.g., 371_826). In a second step, we evaluated how hundred-decade and hundred-unit compatibility (...) effects were moderated by varying the percentage of within-hundred (e.g., 539_582) and within-hundred-and-decade filler items (e.g., 483_489). From the results we predict that numerical distance as well as compatibility effects should indeed be modulated by the relevance of tens and units in three-digit number magnitude comparison: While in particular the hundred distance effect should decrease, we predict hundred-decade and hundred-unit compatibility effects to increase with the relevance of tens and units. (shrink)
New success criteria of inductive inference in computational learning theory are introduced which model learning total (not necessarily recursive) functions with (possibly everywhere) imprecise theories from (possibly always) inaccurate data. It is proved that for any level of error allowable by the new success criteria, there exists a class of recursive functions such that not all f are identifiable via the criterion at that level of error. Also, necessary and sufficient conditions on the error level are given (...) for when more classes of functions may be identified. (shrink)
In this paper we focus on the modularity of visual functions in the human visual cortex, that is, the specific problems that the visual system must solve in order to achieve recognition of objects and visual space. The computational theory of early visual functions is briefly reviewed and is then used as a basis for suggesting computational constraints on the higher-level visual computations. The remainder of the paper presents neurological evidence for the existence of two visual systems in (...) man, one specialized for spatial vision and the other for object vision. We show further clinical evidence for the computational hypothesis that these two systems consist of several visual modules, some of which can be isolated on the basis of specific visual deficts which occur after lesions to selected areas in the visually responsive brain. We will provide examples of visual modules which solve information processing tasks that are mediated by specific anatomic areas. We will show that the clinical data from behavioral studies of monkeys (Ungerleider and Mishkin 1984) supports the distinction between two visual systems in monkeys, the 'what' system, involved in object vision, and the 'where' system, involved in spatial vision. (shrink)
How the Mind Works is a synthesis of cognitive science and evolutionary biology that aims to explain the human mind with three ideas: (1) Computation: thinking and feeling consist of information-processing in the brain; (2) Specialization: the mind is not a single entity, but a complex system of parts designed to solve different problems; (3) Evolution: as with the organs of the body, our complex mental faculties have biological functions ultimately related to survival and reproduction. The book lays (...) out criteria for attributing an evolutionary function to a trait, and applies them to many hypotheses using data from cognitive science, psychology, anthropology, and biology. (shrink)
Since 1991 the author has been Professor of Artificial Intelligence and Cognitive Science in the School of Computer Science at the University of Birmingham, UK.
This important book, which results from a series of presentations at American Philosophical Association conferences, explores the major ways in which computers ...
The chapters of this volume all have their own level of presentation. The topics have been chosen based on the active research interest associated with them. Since the interest in some topics is older than that in others, some presentations contain fundamental definitions and basic results while others relate very little of the elementary theory behind them and aim directly toward an exposition of advanced results. Presentations of the latter sort are in some cases restricted to a short survey of (...) recent results (due to the complexity of the methods and proofs themselves). Hence the variation in level of presentation from chapter to chapter only reflects the conceptual situation itself. One example of this is the collective efforts to develop an acceptable theory of computation on the real numbers. The last two decades has seen at least two new definitions of effective operations on the real numbers. (shrink)
This paper addresses the problem of upgrading functional information to knowledge. Functional information is defined as syntactically well-formed, meaningful and collectively opaque data. Its use in the formal epistemology of information theories is crucial to solve the debate on the veridical nature of information, and it represents the companion notion to standard strongly semantic information, defined as well-formed, meaningful and true data. The formal framework, on which the definitions are based, uses a contextual version of the verificationist principle (...) of truth in order to connect functional to semantic information, avoiding Gettierization and decoupling from true informational contents. The upgrade operation from functional information uses the machinery of epistemic modalities in order to add data localization and accessibility as its main properties. We show in this way the conceptual worthiness of this notion for issues in contemporary epistemology debates, such as the explanation of knowledge process acquisition from information retrieval systems, and open data repositories. (shrink)
Robertson's earlier work, The New Renaissance projected the likely future impact of computers in changing our culture. Phase Change builds on and deepens his assessment of the role of the computer as a tool driving profound change by examining the role of computers in changing the face of the sciences and mathematics. He shows that paradigm shifts in understanding in science have generally been triggered by the availability of new tools, allowing the investigator a new way of seeing into questions (...) that had not earlier been amenable to scientific probing. (shrink)
The theme of this book is formed by a pair of concepts: the concept of formal language as carrier of the precise expression of meaning, facts and problems, and the concept of algorithm or calculus, i.e. a formally operating procedure for the solution of precisely described questions and problems. The book is a unified introduction to the modern theory of these concepts, to the way in which they developed first in mathematical logic and computability theory and later in automata theory, (...) and to the theory of formal languages and complexity theory. Apart from considering the fundamental themes and classical aspects of these areas, the subject matter has been selected to give priority throughout to the new aspects of traditional questions, results and methods which have developed from the needs or knowledge of computer science and particularly of complexity theory. It is both a textbook for introductory courses in the above-mentioned disciplines as well as a monograph in which further results of new research are systematically presented and where an attempt is made to make explicit the connections and analogies between a variety of concepts and constructions. (shrink)
Together, Models and Computability and its sister volume Sets and Proofs will provide readers with a comprehensive guide to the current state of mathematical logic. All the authors are leaders in their fields and are drawn from the invited speakers at 'Logic Colloquium '97' (the major international meeting of the Association of Symbolic Logic). It is expected that the breadth and timeliness of these two volumes will prove an invaluable and unique resource for specialists, post-graduate researchers, and the informed and (...) interested nonspecialist. (shrink)
Recent new paradigms of computation, based on biological and physical models, address in a radically new way questions of efficiency and challenge assumptions ...
This unique book presents a comprehensive and rigorous treatment of the theory of computability which is introductory yet self-contained. It takes a novel approach by looking at the subject using computation models rather than a limitation orientation, and is the first book of its kind to include software. Accompanying software simulations of almost all computational models are available for use in conjunction with the text, and numerous examples are provided on disk in a user-friendly format. Its applications to computer science (...) itself include interesting links to programming language theory, compiler design theory, and algorithm design. The software, numerous examples, and solutions make this book ideal for self-study by computer scientists and mathematicians alike. (shrink)
In addition, this book contains tools that, in principle, can search a set of algorithms to see whether a problem is solvable, or more specifically, if it can be solved by an algorithm whose computations are efficient.
How can computers distinguish the coherent from the unintelligible, recognize new information in a sentence, or draw inferences from a natural language passage? Computational semantics is an exciting new field that seeks answers to these questions, and this volume is the first textbook wholly devoted to this growing subdiscipline. The book explains the underlying theoretical issues and fundamental techniques for computing semantic representations for fragments of natural language. This volume will be an essential text for computer scientists, linguists, and anyone (...) interested in the development of computational semantics. (shrink)
The book focuses on relations between information and computation. Information is a basic structure of the world, while computation is a process of the dynamic change of information. In order for anything to exist for an individual, the individual must get information on it, either by means of perception or by re-organization of the existing information into new patterns and networks in the brain. With the advent of World Wide Web and a prospect of semantic web, the ways of information (...) supply for individuals, networks of humans and machines and for humanity as a whole are becoming strategically important in a number of ways. Information becomes pivotal for communication, research, education systems, government, businesses and basic functioning of everyday life. At the same time, information may be understood only if we understand its dynamics - time changes of informational structure, that is, we should understand information processing and its primary form - computation. As there is no information without (physical) representation, the dynamics of information is implemented on different levels of granularity by different physical processes, including the level of computation performed by computing machines. There are a lot of open problems of the nature of information and computation, as well as their relationships. How exactly is information dynamics implemented in computational systems, machines as well as living organisms? Are computers processing only data or information and knowledge as well? How does information processing relate to knowledge management and sciences, especially to science of information itself? What do we know of computational processes in machines and living organisms and how these processes are related? What can we learn from natural computational processes that can be useful for information systems and knowledge management? These and similar problems related to information and computation are treated in the book. (shrink)
In this paper we specialize the notion of abstract computational procedure previously introduced for intensionally presented structures to those which are extensionally given. This is provided by a form of generalized recursion theory which uses schemata for explicit definition, conditional definition and least fixed point (LFP) recursion in functionals of type level ≤ 2 over any appropriate structure. It is applied here to the case of potentially infinite (and more general partial) streams as an abstract data type.
Ethical problems are related to computer data bases, containing data on individuals and groups of persons, as well as to computer knowledge bases, containing general rules and elements of expert systems.In the present essay the following conclusions are made regarding computer data bases: privacy, security, and confidentiality of medical computer data bases should be ensured. This duty should rest with physicians in hospitals. The principle of informed consent should be applied to gathering information which is to (...) be stored and processed by computers. Information stored in computer data bases should not be used for purposes for which the subjects (patients as well as personnel) have not given their consent. In order to decrease the possibility of misuses of medical data bases containing information on individuals, these registers should not be linked to other central data bases. (shrink)
Electronic publications are not accessible without technical aids and need constant, time consuming attention; a look back at the data media and data formats utilized in the past 25Â years illustrates this. Recently, an increasing number of conferences and studies address the problem. Use of standard data formats, media and platform independence of data, as well as data centering instead of process centering are requirements for long-term availability. For the humanities, texts are not only the (...) sources of information but also objects of scholarly investigation. Therefore publication in a presentation format only is not sufficient. In addition to more sophisticated tools for analysis, search and navigation, a form of publication is required which does not focus on layout but gives easy access to the content and structure of the published document. Both for the creation and the scholarly evaluation of such documents, tools are required which offer additional functions compared to those provided by commercial publication and access tools. The necessary flexibility is guaranteed by the provision of basic functions of text dataprocessing which do not anticipate or preclude any particular questions. This is illustrated by examples for the evaluation and preparation of digital texts. (shrink)
This book provides a systematic study of three foundational issues in the semantics of natural language that have been relatively neglected in the past few decades. focuses on the formal characterization of intensions, the nature of an adequate type system for natural language semantics, and the formal power of the semantic representation language proposes a theory that offers a promising framework for developing a computational semantic system sufficiently expressive to capture the properties of natural language meaning while remaining computationally tractable (...) written by two leading researchers and of interest to students and researchers in formal semantics, computational linguistics, logic, artificial intelligence, and the philosophy of language. (shrink)
Based on the theoretical analysis of self-consciousness concepts, we hypothesized that the spatio-temporal pattern of functional connectivity within the default-mode network (DMN) should persist unchanged across a variety of different cognitive tasks or acts, thus being task-unrelated. This supposition is in contrast with current understanding that DMN activated when the subjects are resting and deactivated during any attention-demanding cognitive tasks. To test our proposal, we used, in retrospect, the results from our two early studies ([Fingelkurts, 1998] and [Fingelkurts et al., (...) 2003]). In both studies for the majority of experimental trails we indeed found a constellation of operationally synchronized cortical areas (indexed as DMN) that was persistent across all studied experimental conditions in all subjects. Furthermore, we found three major elements comprising this DMN: two symmetrical occipito-parieto-temporal and one frontal spatio-temporal patterns. This new data directly supports the notion that DMN has a specific functional connotation – it provides neurophysiologic basis for self-processing operations, namely first-person perspective taking and an experience of agency. -/- . (shrink)
In this particularly well written volume Graeme Hirst presents a theoretically motivated foundation for semantic interpretation (conceptual analysis) by computer, and shows how this framework facilitates the resolution of both lexical and syntactic ambiguities.
We explore the interaction between oculomotor control and language comprehension on the sentence level using two well-tested computational accounts of parsing difficulty. Previous work (Boston, Hale, Vasishth, & Kliegl, 2011) has shown that surprisal (Hale, 2001; Levy, 2008) and cue-based memory retrieval (Lewis & Vasishth, 2005) are significant and complementary predictors of reading time in an eyetracking corpus. It remains an open question how the sentence processor interacts with oculomotor control. Using a simple linking hypothesis proposed in Reichle, Warren, and (...) McConnell (2009), we integrated both measures with the eye movement model EMMA (Salvucci, 2001) inside the cognitive architecture ACT-R (Anderson et al., 2004). We built a reading model that could initiate short “Time Out regressions” (Mitchell, Shen, Green, & Hodgson, 2008) that compensate for slow postlexical processing. This simple interaction enabled the model to predict the re-reading of words based on parsing difficulty. The model was evaluated in different configurations on the prediction of frequency effects on the Potsdam Sentence Corpus. The extension of EMMA with postlexical processing improved its predictions and reproduced re-reading rates and durations with a reasonable fit to the data. This demonstration, based on simple and independently motivated assumptions, serves as a foundational step toward a precise investigation of the interaction between high-level language processing and eye movement control. (shrink)
The automatic verification of large parts of mathematics has been an aim of many mathematicians from Leibniz to Hilbert. While Gödel's first incompleteness theorem showed that no computer program could automatically prove certain true theorems in mathematics, the advent of electronic computers and sophisticated software means in practice there are many quite effective systems for automated reasoning that can be used for checking mathematical proofs. This book describes the use of a computer program to check the proofs of several celebrated (...) theorems in metamathematics including those of Gödel and Church-Rosser. The computer verification using the Boyer-Moore theorem prover yields precise and rigorous proofs of these difficult theorems. It also demonstrates the range and power of automated proof checking technology. The mechanization of metamathematics itself has important implications for automated reasoning, because metatheorems can be applied as labor-saving devices to simplify proof construction. (shrink)
We give a self-contained and streamlined version of the classification of the provably computablefunctions of PA. The emphasis is put on illuminating as well as seems possible the intrinsic computational character of the standard cut elimination process. The article is intended to be suitable for teaching purposes and just requires basic familiarity with PA and the ordinals below ε0. (Familiarity with a cut elimination theorem for a Gentzen or Tait calculus is helpful but not presupposed).
The James–Lange theory considers emotional feelings as perceptions of physiological body changes. This approach has recently resurfaced and modified in both neuroscientific and philosophical concepts of embodiment of emotional feelings. In addition to the body, the role of the environment in emotional feeling needs to be considered. I here claim that the environment has not merely an indirect and thus instrumental role on emotional feelings via the body and its sensorimotor and vegetative functions. Instead, the environment may have a (...) direct and non-instrumental, i.e., constitutional role in emotional feelings; this implies that the environment itself in the gestalt of the person–environment relation is constitutive of emotional feeling rather than the bodily representation of the environment. Since the person–environment relation is crucial in this approach, I call it the relational concept of emotional feeling. After introducing the relational concept of emotional feeling, the present paper investigates the neurophilosophical question whether current neuroimaging data on human emotion processing and anatomical connectivity are empirically better compatible with the “relational” or the “embodied” concept of emotional feeling. These data lend support to the empirical assumption that neural activity in subcortical and cortical midline regions code the relationship between intero- and exteroceptive stimuli in a relational mode, i.e. their actual balance, rather than in a translational mode, i.e., by translating extero- into interoceptive stimulus changes. Such intero-exteroceptive relational mode of neural coding may have implications for the characterization of emotional feeling with regard to phenomenal consciousness and intentionality. I therefore conclude that the here advanced relational concept of emotional feeling may be considered neurophilosophically more plausible and better compatible with current neuroscientific data than the embodied concept as presupposed in the James–Lange theory and its modern neuroscientific and philosophical versions. (shrink)
Single cell recordings in monkeys provide strong evidence for an important role of the motor system in action understanding. This evidence is backed up by data from studies of the (human) mirror neuron system using neuroimaging or TMS techniques, and behavioral experiments. Although the data acquired from single cell recordings are generally considered to be robust, several debates have shown that the interpretation of these data is far from straightforward. We will show that research based on single-cell (...) recordings allows for unlimited content attribution to mirror neurons. We will argue that a theoretical analysis of the mirroring process, combined with behavioral and brain studies, can provide the necessary limitations. A complexity analysis of the type of processing attributed to the mirror neuron system can help formulate restrictions on what mirroring is and what cognitive functions could, in principle, be explained by a mirror mechanism. We argue that processing at higher levels of abstraction needs assistance of non-mirroring processes to such an extent that subsuming the processes needed to infer goals from actions under the label ?mirroring? is not warranted. (shrink)
In this paper, I argue for a modified version of what Devitt (2006) calls the Representational Thesis (RT). According to RT, syntactic rules or principles are psychologically real, in the sense that they are represented in the mind/brain of every linguistically competent speaker/hearer. I present a range of behavioral and neurophysiological evidence for the claim that the human sentence processing mechanism constructs mental representations of the syntactic properties of linguistic stimuli. I then survey a range of psychologically plausible computational (...) models of comprehension and show that they are all committed to RT. I go on to sketch a framework for thinking about the nature of the representations involved in sentence processing. My claim is that these are best characterized not as propositional attitudes but, rather, as subpersonal states whose representational properties are determined by their functional role. Finally, I distinguish between explicit and implicit representations and argue that the latter can be drawn on as data by the algorithms that constitute our sentence processing routines. I conclude that skepticism concerning the psychological reality of grammars cannot be sustained. (shrink)
Single-unit data from the cortex of monkeys performing working-memory tasks support the main point of the target article. Those data, however, also indicate that the activation of long-term memory is essential to the processing of all cognitive functions. The activation of cortical long-term memory networks is a key neural mechanism in attention (working memory is a form thereof), perception, memory acquisition and retrieval, intelligence, and language.
Mack and Rock show evidence that no consciousperception occurs without a prior attentiveact. Subjects already executing attention taskstend to neglect visible elements extraneous tothe attentional task, apparently lacking evenbetter-than-chance ``implicit perception,''except in certain cases where the unattendedstimulus is a meaningful word or has uniquepre-tuned salience similar to that ofmeaningful words. This is highly consistentwith ``enactive'' notions that consciousnessrequires selective attention via emotional subcortical and limbic motivationalactivation as it influences anterior attentionmechanisms. Occipital activation withoutconsciousness suggests that motivated search,enacted through the organism's (...) subcorticalmotivational functions, is needed beforevisual stimulation engenders consciousness.This enactive view – that searching for,rather than receiving or processing input isthe basis of consciousness – was slow ingaining acceptance lacking empirical evidenceof this kind, combined with thestimulus-response assumption that brain eventssubserving perceptual consciousness must resultfrom transformation of perceptual input ratherthan from the organism's self-regulatedactivity as manifested through subcorticalactivity. Implicit perception occurring withword priming is ``paradoxical'' according to Mackand Rock, suggesting late selection forattention after extensive unconsciousprocessing, while most trials involvingnonverbal rather than verbal images mightsuggest earlier selection, sinceunattended objects are unseen, apparently evenimplicitly. This paper argues that anteriorand subcortical motivational mechanisms play animportant role in early selection; posteriormechanisms then unconsciously enhance signals;if data survive early gating andcorticothalamic enhancement, then still further anterior-limbic loops motivatedlyactivate ``image schemas'' resonating withposterior nonconscious processing; at thatpoint, consciousness occurs. (shrink)
Neuroenhancement offers the prospect of improving the cognitive, emotional and motivational functions of healthy individuals. Of all the conceivable interventions, psychopharmacology provides the most readily available ones, such as antidepressants which are thought to make people better than well . However, up until now, whether they possess such an enhancing ability remains controversial and therefore in this systematic review we will evaluate the effect and safety of modern antidepressants in healthy individuals. A search of MEDLINE and EMBASE databases and (...) cross-references was carried out and the pharmaceutical industry was contacted for suitable data. Trials published in any language through the third week of July 2007 were regarded. Included were single or double blind randomised or quasi-randomised controlled trials that compared a placebo to one or more of the following antidepressants: bupropion, citalopram, duloxetine, escitalopram, fluoxetine, fluvoxamine, moclobemide, paroxetine, reboxetine, sertraline or venlafaxine in any dose or dosing schedule. Eligible studies were those involving healthy people of any age and either sex who showed no evidence of a psychiatric disorder, cognitive decline or other disease. One hundred thirty-five articles met our inclusion criteria reporting single dose trials and trials with repeated drug administration. Sixty-five of these articles were eligible for a statistical analysis. Based on a linear mixed model, a meta-analysis and a fixed effects meta-regression were performed. Pooling of results by meta-analysis was stratified by the outcome measures (a) mood, (b) emotional processing, (c) wakefulness, (d) attention, (e) memory, and (f) executive functions. On a significance level of p < 0.05 the following significant results emerged: After a single dose of an antidepressant, a significant effect was shown in two of the analysed outcomes. Firstly, there was a small yet significant negative effect on wakefulness. On memory, a positive effect after several measurements was found, but this result could be traced to the results of the one study out of all included studies, which had that many assessment points. The analysis of trials with repeated drug administration (mean duration 14 days, standard deviation 9) yielded the following effects: on mood, a non-significant positive effect was detected that was continuously increasing and reached significance at the last assessment point. Regarding attention, a fluctuating effect was found, while for memory, the fact that the two groups started with a group difference confounded the results. For wakefulness there was no significant effect in any particular assessment point, while for emotional processing and executive functions, the small number of studies did not allow for any effect to emerge. In summary, no consistent evidence for enhancing effects of antidepressants could be found. There is little evidence so far to support the popular opinion that antidepressants have a positive effect on the mood of healthy individuals after repeated administration. No evidence of a significant adverse event profile could be found. The studies included in this systematic review not only provide insufficient evidence for or against any effect in healthy people, but they are inapt to be used for answering this question. This may be explained by the fact that most of them were not designed to examine neuroenhancement effects. The growing public interest in neuroenhancement stands in stark contrast to the paucity of data on enhancement effects of available psychopharmacological agents. (shrink)
Antonyms are a ubiquitous part of everyday language, and this book provides a detailed, comprehensive account of the phenomenon.This book demonstrates how ...
Although Grodzinsky's target article has merit, it neglects the importance of neural mechanisms underlying language functions. We present results from our clinical studies on different levels of temporal information processing in aphasic patients and briefly review the existing data on neurobiology of language to cast new light on the main thesis of the target article.
This book reflects the growing influence of corpus linguistics in a variety of areas such as lexicography, translation studies, genre analysis, and language ...
In this paper we study a new approach to classify mathematical theorems according to their computational content. Basically, we are asking the question which theorems can be continuously or computably transferred into each other? For this purpose theorems are considered via their realizers which are operations with certain input and output data. The technical tool to express continuous or computable relations between such operations is Weihrauch reducibility and the partially ordered degree structure induced by it. We have identified (...) certain choice principles such as co-finite choice, discrete choice, interval choice, compact choice and closed choice, which are cornerstones among Weihrauch degrees and it turns out that certain core theorems in analysis can be classified naturally in this structure. In particular, we study theorems such as the Intermediate Value Theorem, the Baire Category Theorem, the Banach Inverse Mapping Theorem, the Closed Graph Theorem and the Uniform Boundedness Theorem. We also explore how existing classifications of the Hahn—Banach Theorem and Weak Kőnig's Lemma fit into this picture. Well-known omniscience principles from constructive mathematics such as LPO and LLPO can also naturally be considered as Weihrauch degrees and they play an important role in our classification. Based on this we compare the results of our classification with existing classifications in constructive and reverse mathematics and we claim that in a certain sense our classification is finer and sheds some new light on the computational content of the respective theorems. Our classification scheme does not require any particular logical framework or axiomatic setting, but it can be carried out in the framework of classical mathematics using tools of topology, computability theory and computable analysis. We develop a number of separation techniques based on a new parallelization principle, on certain invariance properties of Weihrauch reducibility, on the Low Basis Theorem of Jockusch and Soare and based on the Baire Category Theorem. Finally, we present a number of metatheorems that allow to derive upper bounds for the classification of the Weihrauch degree of many theorems and we discuss the Brouwer Fixed Point Theorem as an example. (shrink)
Neural organization: Structure, function, and dynamics shows how theory and experiment can supplement each other in an integrated, evolving account of the brain's structure, function, and dynamics. (1) Structure: Studies of brain function and dynamics build on and contribute to an understanding of many brain regions, the neural circuits that constitute them, and their spatial relations. We emphasize Szentágothai's modular architectonics principle, but also stress the importance of the microcomplexes of cerebellar circuitry and the lamellae of hippocampus. (2) Function: Control (...) of eye movements, reaching and grasping, cognitive maps, and the roles of vision receive a functional decomposition in terms of schemas. Hypotheses as to how each schema is implemented through the interaction of specific brain regions provide the basis for modeling the overall function by neural networks constrained by neural data. Synthetic PET integrates modeling of primate circuitry with data from human brain imaging. (3) Dynamics: Dynamic system theory analyzes spatiotemporal neural phenomena, such as oscillatory and chaotic activity in both single neurons and (often synchronized) neural networks, the self-organizing development and plasticity of ordered neural structures, and learning and memory phenomena associated with synaptic modification. Rhythm generation involves multiple levels of analysis, from intrinsic cellular processes to loops involving multiple brain regions. A variety of rhythms are related to memory functions. The Précis presents a multifaceted case study of the hippocampus. We conclude with the claim that language and other cognitive processes can be fruitfully studied within the framework of neural organization that the authors have charted with John Szentágothai. Key Words: cognitive maps; computational neuroscience; dynamics; hippocampus; memory; modular architectonics; neural modeling; neural organization; neural plasticity; rhythmogenesis; Szentágothai. (shrink)
To see whether the mental and the neural have common attributes that could resolve some of the traditional dichotomies, we review neuroscientific data on the visual system. The results show that neuronal and perceptual function share a parallel and hierarchical architecture which is manifest not only in the anatomy and physiology of the visual system, but also in normal perception and in the deficits caused by lesions in different parts of the system. Based on the description of parallel hierarchical (...) levels of active information processing in the visual brain, we suggest a concept of dissociable levels of perception, advocating that the phenomenal perception and recognition is realized in the functional integrity of a network of reciprocal cortico-cortical connections. The properties shared by neuronal and perceptional functions provide a basis for a neuromental monism in which both functions are attributed a causal role. (shrink)
Probabilistic models of sentence comprehension are increasingly relevant to questions concerning human language processing. However, such models are often limited to syntactic factors. This restriction is unrealistic in light of experimental results suggesting interactions between syntax and other forms of linguistic information in human sentence processing. To address this limitation, this article introduces two sentence processing models that augment a syntactic component with information about discourse co-reference. The novel combination of probabilistic syntactic components with co-reference classifiers permits (...) them to more closely mimic human behavior than existing models. The first model uses a deep model of linguistics, based in part on probabilistic logic, allowing it to make qualitative predictions on experimental data; the second model uses shallow processing to make quantitative predictions on a broad-coverage reading-time corpus. (shrink)
We reformulate minimalist grammars as partial functions on term algebras for strings and trees. Using filler/role bindings and tensor product representations, we construct homomorphisms for these data structures into geometric vector spaces. We prove that the structure-building functions as well as simple processors for minimalist languages can be realized by piecewise linear operators in representation space. We also propose harmony, i.e. the distance of an intermediate processing step from the final well-formed state in representation space, as (...) a measure of processing complexity. Finally, we illustrate our findings by means of two particular arithmetic and fractal representations. (shrink)
We discuss the role of short-term auditory verbal storage within a working memory system. Data from single case studies of patients with left parietal lesions and selective impairment of memory span are discussed in order to address the question of the functions of short-term memory in language processing. The backup resource of auditory verbal short-term memory is required for those tasks that necessitate backtracking in order to integrate a verbal message within a developing central cognitive representation.
Correcting the relationship between tonic and burst firing modes in dopamine neurons may help normalise stimulus-reinforcement gradients and contingent behaviour in attention-deficit/hyperactivity disorder (ADHD) children. But appropriate evaluations of stimuli for developing adaptive plans and controlling impulsivity will not occur without moderating the gain-like functions of serotonin. The “dynamic theory” correctly highlights the need to account for variability in ADHD. The dysmaturation of pre-executive information processing is proposed as an explanation. At the core of the article by Sagvolden (...) and colleagues there is a set of data that throws light on an aspect of the ADHD phenomenon. But one asks if the authors are a measure too brave to generalise so broadly from the unusually steep reinforcement gradients reported for the human condition and an animal model to the syndrome as a whole. (shrink)
