Ranging from Alan Turing’s seminal 1936 paper to the latest work on Kolmogorov complexity and linear logic, this comprehensive new work clarifies the relationship between computability on the one hand and constructivity on the other. The authors argue that even though constructivists have largely shed Brouwer’s solipsistic attitude to logic, there remain points of disagreement to this day. Focusing on the growing pains computability experienced as it was forced to address the demands of rapidly expanding applications, the content maps (...) the developments following Turing’s ground-breaking linkage of computation and the machine, the resulting birth of complexity theory, the innovations of Kolmogorov complexity and resolving the dissonances between proof theoretical semantics and canonical proof feasibility. Finally, it explores one of the most fundamental questions concerning the interface between constructivity and computability: whether the theory of recursive functions is needed for a rigorous development of constructive mathematics. This volume contributes to the unity of science by overcoming disunities rather than offering an overarching framework. It posits that computability’s adoption of a classical, ontological point of view kept these imperatives separated. In studying the relationship between the two, it is a vital step forward in overcoming the disagreements and misunderstandings which stand in the way of a unifying view of logic. (shrink)

Definitionally: _strongly effectively immune_ sets are infinite and their c.e. subsets have _maximums_ effectively bounded in their c.e. indices; whereas, for _effectively immune_ sets, their c.e. subsets’ _cardinalities_ are what’re effectively bounded. This definitional difference between these two kinds of sets is very nicely paralleled by the following difference between their _complements_. McLaughlin: _strongly_ effectively immune sets can_not_ have _immune complements_; whereas, the main theorem herein: _effectively_ immune sets can_not_ have _hyperimmune complements_. Ullian: _effectively_ immune sets _can_ have _effectively_ immune (...) complements. The main theorem _improves_ Arslanov’s, effectively hyperimmune sets can_not_ have _effectively_ hyperimmune complements: the _improvement_ omits the second ‘_effectively_’. Two _natural_ examples of _strongly effectively immune_ sets are presented with new cases of the first proved herein. The first is the set of minimal-Blum-size programs for the partial computable functions; the second, the set of Kolmogorov-random strings. A proved, _natural_ example is presented of an _effectively dense simple_, _not_ strongly effectively simple set; its complement is a set of maximal run-times. Further motivations for this study are presented. _Kleene_ recursion theorem proofs herein emphasize how to conceptualize them. Finally, is suggested, future, related work—illustrated by a first, _natural_, _strongly effectively_ \(\Sigma _2^0\) -_immune set_—included: solution of an open problem from Rogers’ book. (shrink)

We review and contrast three ways to make up a formal Euclidean geometry which one might call constructive, in a computational sense. The starting point is the first-order geometry created by Tarski.

This is a survey of Gödel's perennial preoccupations with the limits of finitism, its relations to constructivity, and the significance of his incompleteness theorems for Hilbert's program, using his published and unpublished articles and lectures as well as the correspondence between Bernays and Gödel on these matters. There is also an important subtext, namely the shadow of Hilbert that loomed over Gödel from the beginning to the end.

Book Review: Dubucs, J., & Bourdeau, M.. Constructivity and Computability in Historical and Philosophical Perspective. Springer Netherlands, XI. 214, pp. ISBN: 978-94-017-9216-5 978-94-017-9217-2, €83.29.

Constructibility and complexity play central roles in recent research in computer science, mathematics and physics. For example, scientists are investigating the complexity of computer programs, constructive proofs in mathematics and the randomness of physical processes. But there are different approaches to the explication of these concepts. This volume presents important research on the state of this discussion, especially as it refers to quantum mechanics. This `foundational debate' in computer science, mathematics and physics was already fully developed in 1930 in the (...) Vienna Circle. A special section is devoted to its real founder Hans Hahn, referring to his contribution to the history and philosophy of science. The documentation section presents articles on the early Philipp Frank and on the Vienna Circle in exile. Reviews cover important recent literature on logical empiricism and related topics. (shrink)

Recently, constructive neutral evolution has been touted as an important concept for the understanding of the emergence of cellular complexity. It has been invoked to help explain the development and retention of, amongst others, RNA splicing, RNA editing and ribosomal and mitochondrial respiratory chain complexity. The theory originated as a welcome explanation of isolated small scale cellular idiosyncrasies and as a reaction to ‘overselectionism’. Here I contend, that in its extended form, it has major conceptual problems, can not explain observed (...) patterns of complex processes, is too easily dismissive of alternative selectionist models, underestimates the creative force of complexity as such, and – if seen as a major evolutionary mechanism for all organisms – could stifle further thought regarding the evolution of highly complex biological processes. (shrink)

The child directed speech of twelve English‐speaking motherswas analyzed in terms of utterance‐level constructions. First, the mothers' utterances were categorized in terms of general constructional categories such as Wh‐questions, copulas and transitives. Second, mothers' utterances within these categories were further specified in terms of the initial words that framed the utterance, item‐based phrases such as Are you …, I'll …, It's …, Let's …, What did … The findings were: (i) overall, only about 15% of all maternal utterances had SVO (...) form (most were questions, imperatives, copulas, and fragments); (ii) 51% of all maternal utterances began with one of 52 item‐based phrases, mostly consisting of two words or morphemes (45% began with one of just 17 words); and (iii) children used many of these same item‐based phrases, in some cases at a rate that correlated highly with their own mother's frequency of use. We suggest that analyses of adult–child linguistic interaction should take into account not just general constructional categories, but also the item‐based constructions that adults and children use and the frequency with which they use them. (shrink)

Nursing has improved over the centuries from the physician's handmaiden to a recognised profession. Yet, the image of a nurse is often associated with notions of caring and nurturing‐ attributes considered feminine. Indeed, cultural, and societal biases exist that can deter men from entering the nursing profession where their sense of masculinity is questioned. Several studies have highlighted the existence of gender‐based stereotypes, stigma, rejection, loneliness and discrimination which impact the retention of men in the nursing profession. Despite the established (...) evidence regarding negative experiences, it appears limited attention has been paid to the men who decide to stay in nursing: how do they thrive in a profession wherein biases are evident within and in the wider societal context? Undoubtedly, several factors such as job security and financial incentives may contribute to men remaining in nursing. Beyond these, we borrow the notion of ‘constructive resistance’ to underscore that though the biases may be apparent, male nurses are able to construct alternatives that accommodate the image of a man in the nursing profession. Strategies such as developing the image as a ‘super nurse’ can create opportunities for male nurses to be preferred by other healthcare providers as well as female nurses. Thus, although resistance may usually appear as a negative phenomenon, constructive resistance represents hidden advantages which offers an opportunity to retain male nurses. These need to be highlighted and explored more as they can offer deeper insight into strategies that can be employed to improve retention and representation of men in nursing particularly at a time when the impact of nursing shortage remains a global issue. (shrink)

Constructions of Intersubjectivity shows that the meaning of grammatical constructions often has more to do with the human cognitive capacity for taking other peoples' points of view than with describing the world. Treating pragmatics, semantics, and syntax in parallel and integrating insights from linguistics, psychology, and animal communication, Arie Verhagen develops a new understanding of linguistic communication. In doing so he shows the continuity between language and animal communication and reveals the nature of human linguistic specialization. Professor Verhagen uses Dutch (...) and English data from a wide variety of sources and considers the contributions of grammar to the coherence of discourse. He argues that important problems in semantics and syntax may be resolved if language is understood as an instrument for exerting influence and coordinating different perspectives. The grammatical phenomena he discusses include negative expressions, the let alone construction, complementation constructions, and discourse connectives.This powerfully argued and original explanation of the nature and operation of communication will interest a wide range of scholars and advanced students in linguistics, cognitive science, and human evolution. (shrink)

This paper provides a constructive topological semantics for non-deducibility of a first order intuitionistic formula. Formal topology theory, in particular the recently introduced notion of a binary positivity predicate, and co-induction are two needful tools.

There is ample evidence that speakers’ linguistic knowledge extends well beyond what can be described in terms of rules of compositional interpretation stated over combinations of single words. We explore a range of multiword constructions to get a handle both on the extent of the phenomenon and on the grammatical constraints that may govern it. We consider idioms of various sorts, collocations, compounds, light verbs, syntactic nuts, and assorted other constructions, as well as morphology. Our conclusion is that MWCs highlight (...) the central role that grammar plays in licensing MWCs in the lexicon and the creation of novel MWCs, and they help to clarify how the lexicon articulates with the rest of the grammar. (shrink)

The theory of constructive (recursive) models follows from works of Froehlich, Shepherdson, Mal'tsev, Kuznetsov, Rabin, and Vaught in the 50s. Within the framework of this theory, algorithmic properties of abstract models are investigated by constructing representations on the set of natural numbers and studying relations between algorithmic and structural properties of these models. This book is a very readable exposition of the modern theory of constructive models and describes methods and approaches developed by representatives of the Siberian school of algebra (...) and logic and some other researchers (in particular, Nerode and his colleagues). The main themes are the existence of recursive models and applications to fields, algebras, and ordered sets (Ershov), the existence of decidable prime models (Goncharov, Harrington), the existence of decidable saturated models (Morley), the existence of decidable homogeneous models (Goncharov and Peretyat'kin), properties of the Ehrenfeucht theories (Millar, Ash, and Reed), the theory of algorithmic dimension and conditions of autostability (Goncharov, Ash, Shore, Khusainov, Ventsov, and others), and the theory of computable classes of models with various properties. Future perspectives of the theory of constructive models are also discussed. Most of the results in the book are presented in monograph form for the first time. The theory of constructive models serves as a basis for recursive mathematics. It is also useful in computer science, in particular, in the study of programming languages, higher level languages of specification, abstract data types, and problems of synthesis and verification of programs. Therefore, the book will be useful for not only specialists in mathematical logic and the theory of algorithms but also for scientists interested in the mathematical fundamentals of computer science. The authors are eminent specialists in mathematical logic. They have established fundamental results on elementary theories, model theory, the theory of algorithms, field theory, group theory, applied logic, computable numberings, the theory of constructive models, and the theoretical computer science. (shrink)