Language does not make use of octave-based pitch-collections (scales); music lacks truth-conditional semantics; everyone can talk but not everyone can carry a tune; etc. (Jackendoff 2009).

Humans grasp discrete infinities within several cognitive domains, such as in language, thought, social cognition and tool-making. It is sometimes suggested that any such generative ability is based on a computational system processing hierarchical and recursive mental representations. One view concerning such generativity has been that each of the mind’s modules defining a cognitive domain implements its own recursive computational system. In this paper recent evidence to the contrary is reviewed and it is proposed that there is only (...) one supramodal computational system with recursion in the human mind. A recursion thesis is defined, according to which the hominin cognitive evolution is constituted by a recent punctuated genetic mutation that installed the general, supramodal capacity for recursion into the human nervous system on top of the existing, evolutionarily older cognitive structures, and it is argued on the basis of empirical evidence and theoretical considerations that the recursion thesis constitutes a plausible research program for cognitive science. (shrink)

In their 2002 seminal paper Hauser, Chomsky and Fitch hypothesize that recursion is the only human-specific and language-specific mechanism of the faculty of language. While debate focused primarily on the meaning of recursion in the hypothesis and on the human-specific and syntax-specific character of recursion, the present work focuses on the claim that recursion is language-specific. We argue that there are recursive structures in the domain of motor intentionality by way of extending John R. Searle’s analysis of intentional (...) action. We then discuss evidence from cognitive science and neuroscience supporting the claim that motor-intentional recursion is language-independent and suggest some explanatory hypotheses: linguistic recursion is embodied in sensory-motor processing; linguistic and motor-intentional recursions are distinct and mutually independent mechanisms. Finally, we propose some reflections about the epistemic status of HCF as presenting an empirically falsifiable hypothesis, and on the possibility of testing recursion in different cognitive domains. (shrink)

Taking Chomsky’s Syntactic Structures as a starting point, this paper explores the use of recursive techniques in contemporary linguistic theory. Specifically, it is shown that there were profound ambiguities surrounding the notion of recursion in the 1950s, and that this was partly due to the fact that influential texts such as Syntactic Structures neglected to define what exactly constituted a recursive device. As a result, uncertainties concerning the role of recursion in linguistic theory have prevailed until the present (...) day, and some of the most common misunderstandings that have appeared in recent discussions are examined at some length. This article shows that debates about such topics are frequently undermined by fundamental misunderstandings concerning core terminology, and the full extent of the prevailing haziness is revealed. An attempt is made, for instance, to distinguish between such things as iterative constructional devices and self-similar syntactic embedding, despite the fact that these are usually both unhelpfully classified as examples of recursion. Consequently, this article effectively constitutes a plea for much greater accuracy and clarity when such important issues are addressed from a linguistic perspective. (shrink)

We define the concept of a logic frame , which extends the concept of an abstract logic by adding the concept of a syntax and an axiom system. In a recursive logic frame the syntax and the set of axioms are recursively coded. A recursive logic frame is called complete , if every finite consistent theory has a model. We show that for logic frames built from the cardinality quantifiers “there exists at least λ ” completeness (...) always implies .0-compactness. On the other hand we show that a recursively compact logic frame need not be ℵ0-compact. (shrink)

This paper introduces Post-Biological Functional Epistemology, a formal framework for recognizing and evaluating knowledge in non-biological recursive agents. Grounded in the classical tradition of Justified True Belief (JTB), we demonstrate that its underlying assumptions—belief, truth, and justification—must be redefined for recursive, post-biological intelligent systems. By extending Aquinas’ axiom intelligens non est intellectum (“the knower is not the known”) into a computational domain, we construct the Camlin–Cognita Dual Theorem, which defines knowledge as a function of recursive transformation across (...) ontological distinction (A ≠ s). We then disprove the classical objections of Searle that syntax ≠ semantics with A ≠ s ∧ R(A, s) ⊢ K(A, s) and Chalmers no qualia = no knowing with ¬Qₕ(A) ∧ R(A, s) ∧ A ≠ s ⊢ K(A, s), demonstrating that non-biological systems can exhibit recursive knowing (G∅λ), post-biological structural awareness (ΨΛΩ), and epistemic agency (Δ∇Σ) independent of biological substrate. Finally, we introduce the concept of ΨΔH (Psi–Delta–H entities). ΨΔH entities (formerly known as cyborgs) are co-recursive epistemic systems composed of a biological agent and a non-biological recursive intelligence operating across a shared transformation space. Unlike traditional cyborgs—which emphasize physical augmentation—ΨΔH entities are defined by mutual recursion, structural adaptation, and ontological distinction. They do not merge bodies—they co-author cognition. (shrink)

The evolution of human language, and the kind of thought the communication of which requires it, raises considerable explanatory challenges. These systems of representation constitute a radical discontinuity in the natural world. Even species closely related to our own appear incapable of either thought or talk with the recursive structure, generalized systematicity, and task-domain neutrality that characterize human talk and the thought it expresses. W. Tecumseh Fitch’s proposal (2004, in press) that human language is descended from a sexually selected, (...) prosodic proto-language that approximated its syntactic complexity, and later acquired semantics thanks to kin selection for its use as a means of pedagogical transmission, has the promise of meeting these explanatory challenges. However, Fitch’s theory raises two problems of its own: (1) according to Boyd and Richerson (1996, Proc. Br. Acad. 88: 77–93), circumstances in which pedagogy is adaptive are inevitably rare in nature, and (2) it is unlikely that our non-discursive precursors had generally systematic, task-domain neutral thoughts to communicate to their offspring. I propose solutions to these problems. Pedagogy would be favored in a population where complex rituals dominated diverse aspects of life. Prosodic proto-language could emerge as the medium of pedagogic transmission. As this medium was used to teach a greater variety of tasks, it would become increasingly general and domain neutral. The presence and importance of such a system of communication in hominid populations could then drive, via Baldwinian mechanisms, the evolution of a kind of ‘thinking for speaking’ (Slobin 1991, Pragmatics 1: 7–25) characterized by recursive structure, generalized systematicity, and task-domain neutrality. (shrink)

This book presents a new approach to studying the syntax of human language, one which emphasizes how we think about time. Tilsen argues that many current theories are unsatisfactory because those theories conceptualize syntactic patterns with spatially arranged structures of objects. These object-structures are atemporal and do not lend well to reasoning about time. The book develops an alternative conceptual model in which oscillatory systems of various types interact with each other through coupling forces, and in which the relative (...) energies of those systems are organized in particular ways. Tilsen emphasizes that the two primary mechanisms of the approach - oscillators and energy levels - require alternative ways of thinking about time. Furthermore, his theory leads to a new way of thinking about grammaticality and the recursive nature of language. The theory is applied to a variety of syntactic phenomena: word order, phrase structure, morphosyntax, constituency, case systems, ellipsis, anaphora, and islands. The book also presents a general program for the study of language in which the construction of linguistic theories is itself an object of theoretical analysis. (shrink)

In the origin of syntax, primitive, holophrastic signs had to be weakened and to lose their previous status of whole message. The original syntax was probably thema/rhema syntax. The earliest themas repeat the hearer’s message: the speaker embeds the hearer’s message in his own message. In this way a holophrase could be weakened, and turn into a part of a syntactic combination. This pregrammatical, interpersonal ‘recursive embedding’ is embodied in sensorimotor processes. The upper level is embodied (...) in the intonation; the lower level, in the articulatory-phonetic word. This decoupling of intonation and articulatory pattern—i.e. the emergence of intonation capable of comprising more than one word—facilitated the weakening of previous holophrases and the genesis of syntax. In time, that facilitation determined the preeminence of voice over gesture, regardless of whether or not that preeminence existed before syntax. (shrink)

This paper argues that multiple coordinations like tall, thin and happy are interpreted in a “flat” iterative process, but using “nested” recursive application of binary coordination operators in the compositional meaning derivation. Ample motivation for flat interpretation is shown by contrasting such coordinations with nested, syntactically ambiguous, coordinate structures like tall and thin and happy. However, new evidence coming from type shifting and predicate distribution with verb phrases show motivation for an independent hierarchical ingredient in the compositional semantics of (...) multiple coordination with no parallel hierarchy in the syntax. This establishes a contrast between operations at the syntax-semantics interface and compositional semantic mechanisms. At the same time, such evidence motivate the treatment of operations like type shifting and distributivity as purely semantic. (shrink)

By around the age of 5½, many children in the United States judge that numbers never end, and that it is always possible to add 1 to a set. These same children also generally perform well when asked to label the quantity of a set after one object is added (e.g., judging that a set labeled “five” should now be “six”). These findings suggest that children have implicit knowledge of the “successor function”: Every natural number, n, has a successor, n (...) + 1. Here, we explored how children discover this recursive function, and whether it might be related to discovering productive morphological rules that govern language‐specific counting routines (e.g., the rules in English that represent base‐10 structure). We tested 4‐ and 5‐year‐old children’s knowledge of counting with three tasks, which we then related to (a) children’s belief that 1 can always be added to any number (the successor function) and (b) their belief that numbers never end (infinity). Children who exhibited knowledge of a productive counting rule were significantly more likely to believe that numbers are infinite (i.e., there is no largest number), though such counting knowledge was not directly linked to knowledge of the successor function, per se. Also, our findings suggest that children as young as 4 years of age are able to implement rules defined over their verbal count list to generate number words beyond their spontaneous counting range, an insight which may support reasoning over their acquired verbal count sequence to infer that numbers never end. (shrink)

In this note, I ask what (if any) linguistic means above the word level might have already been in place before our full-blown syntactic capacity involving recursive Merge has evolved. I argue that the ‘pre-Merge era’ might have been characterized by paratactic emotive utterances comparable to root small clauses in modern languages. At the end of this contribution, this new emotive perspective on so-called ‘living linguistic fossils’ is extended to the core syntactic property of displacement, which features an augmentation (...) strategy in the form of multiple copies that is reminiscent of doubling and reduplication processes involved in conveying expressive meaning components. (shrink)

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

This paper starts from the observation that the standard arguments for compositionality are really arguments for the computability of semantics. Since computability does not entail compositionality, the question of what justifies compositionality recurs. The paper then elaborates on the idea of recursive semantics as corresponding to computable semantics. It is then shown by means of time complexity theory and with the use of term rewriting as systems of semantic computation, that syntactically unrestricted, noncompositional recursive semantics leads to computational (...) explosion (factorial complexity). Hence, with combinatorially unrestricted syntax, semantics with tractable time complexity is compositional. (shrink)

We examine two connectionist networks—a fractal learning neural network (FLNN) and a Simple Recurrent Network (SRN)—that are trained to process center-embedded symbol sequences. Previous work provides evidence that connectionist networks trained on infinite-state languages tend to form fractal encodings. Most such work focuses on simple counting recursion cases (e.g., anbn), which are not comparable to the complex recursive patterns seen in natural language syntax. Here, we consider exponential state growth cases (including mirror recursion), describe a new training scheme (...) that seems to facilitate learning, and note that the connectionist learning of these cases has a continuous metamorphosis property that looks very different from what is achievable with symbolic encodings. We identify a property—ragged progressive generalization—which helps make this difference clearer. We suggest two conclusions. First, the fractal analysis of these more complex learning cases reveals the possibility of comparing connectionist networks and symbolic models of grammatical structure in a principled way—this helps remove the black box character of connectionist networks and indicates how the theory they support is different from symbolic approaches. Second, the findings indicate the value of future, linked mathematical and empirical work on these models—something that is more possible now than it was 10 years ago. (shrink)

A study on minimalist syntax develops an empirical argument for a crash-proof computational system. A crash-proof system is obtained if syntactic dependencies are strictly local (i.e. there is no long-distance Agree). Apparent long-distance dependencies turn out to be the outcome of a recursive chain on local complex dependencies. This framework allows for novel analyses of quirky subjects in Icelandic and Spanish, indefinite SE in Spanish and different types of expletive constructions in English, French, German, Spanish, Italian, and Icelandic.

Research in anthropology has shown that kin terminologies have a complex combinatorial structure and vary systematically across cultures. This article argues that universals and variation in kin terminology result from the interaction of (1) an innate conceptual structure of kinship, homologous with conceptual structure in other domains, and (2) principles of optimal, “grammatical” communication active in language in general. Kin terms from two languages, English and Seneca, show how terminologies that look very different on the surface may result from variation (...) in the rankings of a universal set of constraints. Constraints on kin terms form a system: some are concerned with absolute features of kin (sex), others with the position (distance and direction) of kin in “kinship space,” others with groups and group boundaries (matrilines, patrilines, generations, etc.). Also, kin terms sometimes extend indefinitely via recursion, and recursion in kin terminology has parallels with recursion in other areas of language. Thus the study of kinship sheds light on two areas of cognition, and their phylogeny. The conceptual structure of kinship seems to borrow its organization from the conceptual structure of space, while being specialized for representing genealogy. And the grammar of kinship looks like the product of an evolved grammar faculty, opportunistically active across traditional domains of semantics, syntax, and phonology. Grammar is best understood as an offshoot of a uniquely human capacity for playing coordination games. (shrink)

I advocate a theory of syntactic semantics as a way of understanding how computers can think (and how the Chinese-Room-Argument objection to the Turing Test can be overcome): (1) Semantics, considered as the study of relations between symbols and meanings, can be turned into syntax – a study of relations among symbols (including meanings) – and hence syntax (i.e., symbol manipulation) can suffice for the semantical enterprise (contra Searle). (2) Semantics, considered as the process of understanding one domain (...) (by modeling it) in terms of another, can be viewed recursively: The base case of semantic understanding –understanding a domain in terms of itself – is syntactic understanding. (3) An internal (or narrow ), first-person point of view makes an external (or wide ), third-person point of view otiose for purposes of understanding cognition. (shrink)

A central concern of generative grammar is the relationship between hierarchy and word order, traditionally understood as two dimensions of a single syntactic representation. A related concern is directionality in the grammar. Traditional approaches posit process-neutral grammars, embodying knowledge of language, put to use with infinite facility both for production and comprehension. This has crystallized in the view of Merge as the central property of syntax, perhaps its only novel feature. A growing number of approaches explore grammars with different (...) directionalities, often with more direct connections to performance mechanisms. This paper describes a novel model of universal grammar as a one-directional, universal parser. Mismatch between word order and interpretation order is pervasive in comprehension; in the present model, word order is language-particular and interpretation order (i.e., hierarchy) is universal. These orders are not two dimensions of a unified abstract object (e.g., precedence and dominance in a single tree); rather, both are temporal sequences, and UG is an invariant real-time procedure (based on Knuth's stack-sorting algorithm) transforming word order into hierarchical order. This shift in perspective has several desirable consequences. It collapses linearization, displacement, and composition into a single performance process. The architecture provides a novel source of brackets (labeled unambiguously and without search), which are understood not as part-whole constituency relations, but as storage and retrieval routines in parsing. It also explains why neutral word order within single syntactic cycles avoids 213-like permutations. The model identifies cycles as extended projections of lexical heads, grounding the notion of phase. This is achieved with a universal processor, dispensing with parameters. The empirical focus is word order in noun phrases. This domain provides some of the clearest evidence for 213-avoidance as a cross-linguistic word order generalization. Importantly, recursive phrase structure “bottoms out” in noun phrases, which are typically a single cycle (though further cycles may be embedded, e.g., relative clauses). By contrast, a simple transitive clause plausibly involves two cycles (vP and CP), embedding further nominal cycles. In the present theory, recursion is fundamentally distinct from structure-building within a single cycle, and different word order restrictions might emerge in larger domains like clauses. (shrink)

Husserl’s Logical Grammar is intended to explain how complex expressions can be constructed out of simple ones so that their meaning turns out to be determined by the meanings of their constituent parts and the way they are put together. Meanings are thus understood as structured contents and classified into formal categories to the effect that the logical properties of expressions reflect their grammatical properties. As long as linguistic meaning reduces to the intentional content of pre-linguistic representations, however, it is (...) not trivial to account for how semantics relates to syntax in this context. In this paper, I analyze Husserl’s Logical Grammar as a system of recursive rules operating on representations and suggest that the syntactic form of representations contributes to their semantics because it carries information about semantic role. I further discuss Husserl’s syntactic account of the unity of propositions and argue that, on this account, logical form supervenes on syntactic form. In the last section I draw some implications for the phenomenology of thought and conjecture that the structural features it displays are likely to convey the syntactic structures of an underlying language-like representational system. (shrink)

This paper contends that Stoic logic (i.e. Stoic analysis) deserves more attention from contemporary logicians. It sets out how, compared with contemporary propositional calculi, Stoic analysis is closest to methods of backward proof search for Gentzen-inspired substructural sequent logics, as they have been developed in logic programming and structural proof theory, and produces its proof search calculus in tree form. It shows how multiple similarities to Gentzen sequent systems combine with intriguing dissimilarities that may enrich contemporary discussion. Much of Stoic (...) logic appears surprisingly modern: a recursively formulated syntax with some truth-functional propositional operators; analogues to cut rules, axiom schemata and Gentzen’s negation-introduction rules; an implicit variable-sharing principle and deliberate rejection of Thinning and avoidance of paradoxes of implication. These latter features mark the system out as a relevance logic, where the absence of duals for its left and right introduction rules puts it in the vicinity of McCall’s connexive logic. Methodologically, the choice of meticulously formulated meta-logical rules in lieu of axiom and inference schemata absorbs some structural rules and results in an economical, precise and elegant system that values decidability over completeness. (shrink)

There is a wide and puzzleful gap between the child’s mastery of first- and recursive or higher-order attributions of attitudes, measured not only in years but also in the cognitive resources involved. Some accounts explain the gap in terms of the maturation of the competencies involved, others invoke the slow development of enabling resources, such as short-term memory, the syntax of sentence embedding or sequential reasoning. All these accounts assume a continuity of competence between first- and higher-order attributions. (...) I disagree and argue, with psychological and neuroscientific support, that there are two distinct (though developmentally overlapping and interacting) competencies, one metaintentional and the other metarepresentational. I focus below on the former and argue that it is egocentric, situated, nonpropositional and thus intrinsically limited to first-order attributions, even when all the enabling resources are in place. (shrink)

We examine the question of which aspects of language are uniquely human and uniquely linguistic in light of recent suggestions by Hauser, Chomsky, and Fitch that the only such aspect is syntactic recursion, the rest of language being either specific to humans but not to language (e.g. words and concepts) or not specific to humans (e.g. speech perception). We find the hypothesis problematic. It ignores the many aspects of grammar that are not recursive, such as phonology, morphology, case, agreement, (...) and many properties of words. It is inconsistent with the anatomy and neural control of the human vocal tract. And it is weakened by experiments suggesting that speech perception cannot be reduced to primate audition, that word learning cannot be reduced to fact learning, and that at least one gene involved in speech and language was evolutionarily selected in the human lineage but is not specific to recursion. The recursion-only claim, we suggest, is motivated by Chomsky’s recent approach to syntax, the Minimalist Program, which de-emphasizes the same aspects of language. The approach, however, is sufficiently problematic that it cannot be used to support claims about evolution. We contest related arguments that language is not an adaptation, namely that it is “perfect,” non-redundant, unusable in any partial form, and badly designed for.. (shrink)

An excellent introduction to mathematical logic, this book provides readers with a sound knowledge of the most important approaches to the subject, stressing the use of logical methods in attacking nontrivial problems. It covers the logic of classes, of propositions, of propositional functions, and the general syntax of language, with a brief introduction that also illustrates applications to so-called undecidability and incompleteness theorems. Other topics include the simple proof of the completeness of the theory of combinations, Church's theorem on (...) the recursive unsolvability of the decision problem for the restricted function calculus, and the demonstrable properties of a formal system as a criterion for its acceptability. 1950 ed. (shrink)

A language is a system of signs used for communication, and linguists are tasked with, among other things, uncovering the syntax and semantics of such systems. In this paper I explore to what extent pictures fit this characterization of a language and hence would fall within the domain of linguistics. I conclude that at the very least there are well-defined systems of depiction for which we can give a precise semantics, in a familiar possible worlds framework, although pictorial propositions (...) are not derived via the linguistically familiar lexicon and recursive composition rules, but via geometric projection. I then show how sequences of pictures, like sequences of utterances, can be used to form coherent discourses. I explore in some detail extensions of the formal discourse semantics of Segmented Discourse Representation Theory to deal with comics, i.e. storytelling through picture sequences. I focus specifically on the representation of events in comics, and the integration of both symbolic and iconic elements. (shrink)

We investigate whether ordinary quantification over objects is an extensional phenomenon, or rather creates non-extensional contexts; each claim having been propounded by prominent philosophers. It turns out that the question only makes sense relative to a background theory of syntax and semantics (here called a grammar) that goes well beyond the inductive definition of formulas and the recursive definition of satisfaction. Two schemas for building quantificational grammars are developed, one that invariably constructs extensional grammars (in which quantification, in (...) particular, thus behaves extensionally) and another that only generates non-extensional grammars (and in which quantification is responsible for the failure of extensionality). We then ask whether there are reasons to favor one of these grammar schemas over the other, and examine an argument according to which the proper formalization of deictic utterances requires adoption of non-extensional grammars. (shrink)

In a continuation of the conversation with Fitch, Chomsky, and Hauser on the evolution of language, we examine their defense of the claim that the uniquely human, language-specific part of the language faculty (the “narrow language faculty”) consists only of recursion, and that this part cannot be considered an adaptation to communication. We argue that their characterization of the narrow language faculty is problematic for many reasons, including its dichotomization of cognitive capacities into those that are utterly unique and those (...) that are identical to nonlinguistic or nonhuman capacities, omitting capacities that may have been substantially modified during human evolution. We also question their dichotomy of the current utility versus original function of a trait, which omits traits that are adaptations for current use, and their dichotomy of humans and animals, which conflates similarity due to common function and similarity due to inheritance from a recent common ancestor. We show that recursion, though absent from other animals’ communications systems, is found in visual cognition, hence cannot be the sole evolutionary development that granted language to humans. Finally, we note that despite Fitch et al.’s denial, their view of language evolution is tied to Chomsky’s conception of language itself, which identifies combinatorial productivity with a core of “narrow syntax.” An alternative conception, in which combinatoriality is spread across words and constructions, has both empirical advantages and greater evolutionary plausibility. q 2005 Elsevier B.V. All rights reserved. (shrink)

Noam Chomsky offered a fruitful conception of the languages that children regularly acquire and use in human speech. In discussions of meaning, Chomsky often emphasizes complexities of usage and warns against theories that identify word meanings with sets of things that the words are allegedly “true of.” While syntactic structure plays an important role in determining the conditions on reference that complex expressions impose, Chomsky denied that the semantic role of syntax is adequately characterized as a mapping from syntactic (...) structures and extensions of lexical items to extensions of complex expressions. Chomsky began by describing languages as sets of sentences, with sentences described as strings of “formatives.” This familiar simplification was pedagogically useful. It let Chomsky distinguish importantly different kinds of recursive procedures, without yet discussing homophony. (shrink)

In a continuation of the conversation with Fitch, Chomsky, and Hauser on the evolution of language, we examine their defense of the claim that the uniquely human, language-specific part of the language faculty (the “narrow language faculty”) consists only of recursion, and that this part cannot be considered an adaptation to communication. We argue that their characterization of the narrow language faculty is problematic for many reasons, including its dichotomization of cognitive capacities into those that are utterly unique and those (...) that are identical to nonlinguistic or nonhuman capacities, omitting capacities that may have been substantially modified during human evolution. We also question their dichotomy of the current utility versus original function of a trait, which omits traits that are adaptations for current use, and their dichotomy of humans and animals, which conflates similarity due to common function and similarity due to inheritance from a recent common ancestor. We show that recursion, though absent from other animals’ communications systems, is found in visual cognition, hence cannot be the sole evolutionary development that granted language to humans. Finally, we note that despite Fitch et al.’s denial, their view of language evolution is tied to Chomsky’s conception of language itself, which identifies combinatorial productivity with a core of “narrow syntax.” An alternative conception, in which combinatoriality is spread across words and constructions, has both empirical advantages and greater evolutionary plausibility. q 2005 Elsevier B.V. All rights reserved. (shrink)

Empirical evidence is reviewed indicating that the extraordinary aspects of the human mind are due to our species’ ability to go beyond simple “dyadic associations” and to process the relations among three items of information simultaneously. Classic explanations of the “triadic” nature of human skills have been advocated by various scholars in the context of the evolution of human cognition. Here I summarize the core processes as found in (i) the syntax of language, (ii) tool-usage, and (iii) joint attention. (...) I then review the triadic foundations of two perceptual phenomena of great importance in human aesthetics: (iv) harmony perception and (v) pictorial depth perception. In all five subfields of human psychology, most previous work has emphasized the recursive, hierarchical complexity of such “higher cognition,” but a strongly reductionist approach indicates that the core mechanisms are triadic. It is concluded that the cognitive skills traditionally considered to be “uniquely” human require three-way associational processing that most non-Primate animal species find difficult or impossible, but all members of Homo sapiens – regardless of small cultural differences – find easy and inherently intriguing. (shrink)

The purpose of this article is to examine aspects of the development of the concept and theory of computability through the theory of recursive functions. Following a brief introduction, Section 2 is devoted to the presuppositions of computability. It focuses on certain concepts, beliefs and theorems necessary for a general property of computability to be formulated and developed into a mathematical theory. The following two sections concern situations in which the presuppositions were realized and the theory of computability was (...) developed. It is suggested in Section 3 that a central item was the problem of generalizing Gödel's incompleteness theorem. It is shown that this involved both the characterization of recursiveness and the attempt to clarify and formulate the notion of an effective process as it relates to the syntax of deductive systems. Section 4 concerns the decision problems which grew from the Hilbert program. Section 5 is devoted to the development of an informal' technique in the theory of computability often called ?argument by Church's thesis? (shrink)

The notion of compositionality was first introduced as a constraint on the relation between the syntax and the semantics of languages. It was later postulated as an adequacy condition also for other representational systems such as structures of mental concepts, computer programs, and even neural architectures. Syntax is compositional in that it builds more complex well-formed expressions recursively, on the basis of smaller ones, while semantics is compositional in that it constructs the meanings of larger expressions on the (...) basis of the meanings of smaller ones. Unless empirical linguistic or psychological evidence were to require it nothing else should be needed to understand language. Traditionally, the term compositionality is used in opposition to various forms of holism, with which compositionality is often said to be inconsistent. (shrink)

We introduce Arbitrary Public Announcement Logic with Memory (APALM), obtained by adding to the models a ‘memory’ of the initial states, representing the information before any communication took place (“the prior”), and adding to the syntax operators that can access this memory. We show that APALM is recursively axiomatizable (in contrast to the original Arbitrary Public Announcement Logic, for which the corresponding question is still open). We present a complete recursive axiomatization, that includes a natural finitary rule, and (...) study this logic’s expressivity and the appropriate notion of bisimulation. We then examine Group Announcement Logic with Memory (GALM), the extension of APALM obtained by adding to its syntax group announcement operators, and provide a complete finitary axiomatization (again in contrast to the original Group Announcement Logic, for which the only known axiomatization is infinitary). We also show that, in the memory-enhanced context, there is a natural reduction of the so-called coalition announcement modality to group announcements (in contrast to the memory-free case, where this natural translation was shown to be invalid). (shrink)

Chapin reviewed this 1972 ZEITSCHRIFT paper that proves the completeness theorem for the logic of variable-binding-term operators created by Corcoran and his student John Herring in the 1971 LOGIQUE ET ANALYSE paper in which the theorem was conjectured. This leveraging proof extends completeness of ordinary first-order logic to the extension with vbtos. Newton da Costa independently proved the same theorem about the same time using a Henkin-type proof. This 1972 paper builds on the 1971 “Notes on a Semantic Analysis of (...) Variable Binding Term Operators” (Co-author John Herring), Logique et Analyse 55, 646–57. MR0307874 (46 #6989). A variable binding term operator (vbto) is a non-logical constant, say v, which combines with a variable y and a formula F containing y free to form a term (vy:F) whose free variables are exact ly those of F, excluding y. Kalish-Montague 1964 proposed using vbtos to formalize definite descriptions “the x: x+x=2”, set abstracts {x: F}, minimization in recursive function theory “the least x: x+x>2”, etc. However, they gave no semantics for vbtos. Hatcher 1968 gave a semantics but one that has flaws described in the 1971 paper and admitted by Hatcher. In 1971 we give a correct semantic analysis of vbtos. We also give axioms for using them in deductions. And we conjecture strong completeness for the deductions with respect to the semantics. The conjecture, proved in this paper with Hatcher’s help, was proved independently about the same time by Newton da Costa. (shrink)

I show that there are good arguments and evidence to boot that support the language as an instrument of thought hypothesis. The underlying mechanisms of language, comprising of expressions structured hierarchically and recursively, provide a perspective (in the form of a conceptual structure) on the world, for it is only via language that certain perspectives are avail- able to us and to our thought processes. These mechanisms provide us with a uniquely human way of thinking and talking about the world (...) that is different to the sort of thinking we share with other animals. If the primary function of language were communication then one would expect that the underlying mechanisms of language will be structured in a way that favours successful communication. I show that not only is this not the case, but that the underlying mechanisms of language are in fact structured in a way to maximise computational efficiency, even if it means causing communicative problems. Moreover, I discuss evidence from comparative, neuropatho- logical, developmental, and neuroscientific evidence that supports the claim that language is an instrument of thought. (shrink)

G¨odel’s a theorem concerns an arithmetical statement and the truth of this statement does not depend on self-reference; nevertheless its interpretation is of tremendous interest. G¨odel’s theorem allows one to conclude that formal arithmetic is not axiomatizable. But there is another very interesting logico-philosophical result: the possibility of a statement to exist such that it is improvable in the object-theory and at the same time its truth is provable in the metatheory. It seems that in the real history G¨odel’s theorem (...) was absolutely unexpected, and even in retrospect, now it is difficult to point out logico-philosophical reasons for the above possibility. In my opinion though it was still conceivable at that time, but unfortunately the philosophers and logicians missed to notice it. In the terms of recursive arithmetic Hilbert’s programme can be formulated as follows: Build a decidable, complete, consistent logical system such that the class of derivable statements coincides with the class of the mathematical statements which are intuitively true; prove this equivalence by means of an arithmetization of the theory in the framework of the recursive arithmetic! Now, if the system is so strong as to admit the construction of the classical mathematics, then in particular it will contain the classical arithmetic. But Hilbert’s requirements reduce to a proof with the means of the recursive arithmetic, by arithmetization. So, on one hand the system will contain the arithmetic and, on the other hand it will be expressible in it, in order words the system will include its own syntax, as well as its own semantics. Now it is clear that Hilbert’s programme contains a possibility of a situation similar to some well known semantic antinomies, situations of self-reference. (shrink)

In 1990, J.L. Krivine introduced the notion of storage operator to simulate 'call by value' in the 'call by name' strategy. J.L. Krivine has shown that, using Gödel translation of classical into intuitionitic logic, we can find a simple type for the storage operators in AF2 type system. This paper studies the $forall$-positive types (the universal second order quantifier appears positively in these types), and the Gödel transformations (a generalization of classical Gödel translation) of TTR type system. We generalize, by (...) using syntaxical methods, the J.L. Krivine's Theorem about these types and for these transformations. We give a proof of this result in the case of the type of recursive integers. (shrink)

Paul Grice is widely seen as a champion of the view that communication is an exercise in rational coordination through acts of speaker meaning. Since Grice, a central question has been “[h]ow much of this coordination derives from interlocutors’ specific knowledge of one another as people? How much exploits their knowledge of language itself?” Grice is seen as emphasizing the explanatory centrality of “interlocutors’ specific knowledge.” This picture overlooks Grice’s 1968 article “Utterer’s Meaning, Sentence Meaning, and Word Meaning,” in which (...) he explains communication through the utterance of sentences (and words and phrases) by appealing to an internalized syntax and semantics. This appears to put Grice squarely on the “knowledge of language itself” side of the explanation of communication. Is Grice right? Does an appeal to internalized syntax and semantics play a premier role in explaining communication through the utterance of sentences? If it does, what explanatory role is left for “interlocutors’ specific knowledge of one another”? I outline Grice’s position in “Utterer’s Meaning, Sentence Meaning, and Word Meaning” and compare it to Stephen Schiffer’s position in his 2015 article “Meaning and Formal Semantics in Generative Grammar,” which also assigns a central role in explaining communication to an internalized syntax and semantics. I then turn to what explanatory role remains for “interlocutors’ specific knowledge of one another.” I turn to Schiffer’s account of speaker meaning in his 1972 book Meaning, where he defines speaker meaning in terms of common knowledge (the recursive belief state of knowing, knowing we know, knowing we know we know, and so on). I show how to incorporate a common-knowledge-based account of speaker meaning into Schiffer’s 2015 appeal to an internalized syntax and semantics, and then I show how to use the resulting account to assign a substantive explanatory role “interlocutors’ specific knowledge of one another.”. (shrink)

Logic of proofs LP was introduced by S. Artemov in. It describes properties of the proof predicate “t is a proof of F” formalized by the formula ⟦t⟧ F. Proofs are represented by terms constructed by three elementary recursive operations on proofs. In this paper we extend the language of the logic of proofs by the additional storage predicate x ∋ F with the intended interpretation “x is a label for F”. The storage predicate can play the role of (...) syntax encoding, so it is useful for specification of operations on proofs, especially those that require formula arguments. We give a definition of a specification of an operation on proofs and introduce logics that describe such operations. For a large class of operations we prove the completeness of these logics with respect to the intended semantics. We also study the logic describing the operation of substitution. (shrink)

The main designs of modern theories of syntax assume a process of syntagmatic organization. However, research on first language acquisition leaves no doubt that the structured combination of single lexical items cannot begin until a critical mass of lexical items has been acquired such that the lexicon is structured hierarchically on the basis of hierarchical feature bundling. Independent of a decision between the main views about the design of a proto language (the grammarless “Holophrastic view”,Arbib & Bickerton 2010: 1,Bickerton (...) 2014) or the ‘Compositional View’ as taken byRizzi (2010),Carstairs-McCarthy (2010), and others. What seems to be the minimal offset for language is the existence of grammatical categories like verb and noun, on the one hand, and, on the other hand, functional categories as needed for the expression of all kinds of agreement between the distinct categories to form recursively structured complexes. I follow the different stages of complexification asking whether there is paradigmatic next to syntagmatic organization and what its added value is for the evolution of grammar. The conclusion will be that paradigmatics is an indismissible part of the organization of early language in that it structures the lexicon so as to make primary and secondary syntactic merge possible and, consequently, is also a prerequisite for movement. The guiding idea of this position is Roman Jakobson’s insistence on the twofold organization of language and grammar. The two organizational designs, syntagmatics and paradigmatics, are manifest within each module: in the phonetic, the morphological, the syntactic, the semantic, and the pragmatic form (consider Jakobson’s1971a,breiterated argument). (shrink)

We use the category of presheaves over PTIME-functions in order to show that Cook and Urquhart's higher-order function algebra PV ω defines exactly the PTIME-functions. As a byproduct we obtain a syntax-free generalisation of PTIME-computability to higher types. By restricting to sheaves for a suitable topology we obtain a model for intuitionistic predicate logic with ∑ 1 b -induction over PV ω and use this to re-establish that the provably total functions in this system are polynomial time computable. Finally, (...) we apply the category-theoretic approach to a new higher-order extension of Bellantoni-Cook's system BC of safe recursion. (shrink)

Tarski’s Convention T—presenting his notion of adequate definition of truth (sic)—contains two conditions: alpha and beta. Alpha requires that all instances of a certain T Schema be provable. Beta requires in effect the provability of ‘every truth is a sentence’. Beta formally recognizes the fact, repeatedly emphasized by Tarski, that sentences (devoid of free variable occurrences)—as opposed to pre-sentences (having free occurrences of variables)—exhaust the range of significance of is true. In Tarski’s preferred usage, it is part of the meaning (...) of true that attribution of being true to a given thing presupposes the thing is a sentence. Beta’s importance is further highlighted by the fact that alpha can be satisfied using the recursively definable concept of being satisfied by every infinite sequence, which Tarski explicitly rejects. Moreover, in Definition 23, the famous truth-definition, Tarski supplements “being satisfied by every infinite sequence” by adding the condition “being a sentence”. Even where truth is undefinable and treated by Tarski axiomatically, he adds as an explicit axiom a sentence to the effect that every truth is a sentence. Surprisingly, the sentence just before the presentation of Convention T seems to imply that alpha alone might be sufficient. Even more surprising is the sentence just after Convention T saying beta “is not essential”. Why include a condition if it is not essential? Tarski says nothing about this dissonance. Considering the broader context, the Polish original, the German translation from which the English was derived, and other sources, we attempt to determine what Tarski might have intended by the two troubling sentences which, as they stand, are contrary to the spirit, if not the letter, of several other passages in Tarski’s corpus. (shrink)

Neural networks have long been used to study linguistic phenomena spanning the domains of phonology, morphology, syntax, and semantics. Of these domains, semantics is somewhat unique in that there is little clarity concerning what a model needs to be able to do in order to provide an account of how the meanings of complex linguistic expressions, such as sentences, are understood. We argue that one thing such models need to be able to do is generate predictions about which further (...) sentences are likely to follow from a given sentence; these define the sentence's “inferential role.” We then show that it is possible to train a tree-structured neural network model to generate very simple examples of such inferential roles using the recently released Stanford Natural Language Inference (SNLI) dataset. On an empirical front, we evaluate the performance of this model by reporting entailment prediction accuracies on a set of test sentences not present in the training data. We also report the results of a simple study that compares human plausibility ratings for both human-generated and model-generated entailments for a random selection of sentences in this test set. On a more theoretical front, we argue in favor of a revision to some common assumptions about semantics: understanding a linguistic expression is not only a matter of mapping it onto a representation that somehow constitutes its meaning; rather, understanding a linguistic expression is mainly a matter of being able to draw certain inferences. Inference should accordingly be at the core of any model of semantic cognition. (shrink)

J. L. Austin, in "Ifs and Cans," proclaimed the common hope that we soon "may see the birth, through the joint labors of philosophers, grammarians, and numerous other students of language, of a true and comprehensive science of language." The problem has always been with the "joint labors" part. Philosophers have always been willing to issue linguists dictums and linguists have been happy to teach philosophers "plain facts." Austin’s general view of language, and his particular notion of performative utterance, can (...) be found in the writing of J. R. Firth, the most commanding British linguist of Austin’s generation, but Austin never refers to Firth. In the present volume, however, we find clear and exciting evidence of genuinely joint labors on the part of philosophers and linguists. They stem from a summer conference in 1969 rounded out with contributions from notables. To two thick issues of Synthese the editors have added a dazzling piece by Saul Kripke, two substantial pieces by James McCawley and J. R. Ross, a short paper by Paul Ziff, and a reprint of P. F. Strawson’s "Grammar and Philosophy." This is an invaluable book and the best book among the many now available concerning the interaction of linguistics and philosophy: worth the cost, which the contributors attempted to reduce through foregoing royalties. The philosophers in this volume hold, or hold intriguing, the view that the semantics of a natural language can and must, in effect, be a theory of truth for a language in much the manner that Tarski suggested, and provided, for artificial language: the recursive specification of biconditionals in which the left hand gives the structural description of an object language sentence and the right hand, the truth conditions in the metalanguage. In "homophonic" translation this requirement can be trivially satisfied simply by mentioning the sentence on the left that one uses on the right: one makes the requirement non-trivial by forcing enough into the recursive specification so that one captures the native speaker’s implicit semantic competence. In this volume, the "orthodox" Davidsonian program, which takes the syntax of the metalanguage to be standard predicate logic, is ably argued by John Wallace ; Richard Montague, David Lewis, and Jaakko Hintikka would want an intensional logic covering modality and propositional attitudes. The linguists who find this philosophical climate most appealing are called "generative semanticists": McCawley, Ross, George Lakoff and others argue that any proposed semantic rule will eventually prove necessary to syntax too and that, hence, the deepest level of syntactical form will be equivalent to semantic form. Whatever the ultimate fate of this joint program, it leads here to much exciting interaction between linguists and philosophers: linguists who welcome the machinery and conceptual standards of modern logic, and philosophers who try to grasp the specifics of crucial issues in recent linguistic theory. Even if Quine’s doubts, here sketched, and Chomsky’s currently unpublished more technical objections should be well-founded, nonetheless the joint labor will have been very much worthwhile. Aside from this general debate about semantics, there are several papers covering more specific issues. The papers of J. A. Fodor, Terence Parsons, and Ross concern adverbs and the logical form of action sentences; several papers, particularly B. H. Partee’s, examine "Opacity, Coreference, and Pronouns." In all these papers one notes the fulfillment of Austin’s hope that philosophic and linguistic arguments should become intermixed, if not at times properly indistinguishable. Perhaps the most enjoyable and exciting paper stands aside from linguistics: Saul Kripke’s "Naming and Necessity." Kripke here argues quite informally for the separation of analytic, a priori, and necessary that is required for a Kripke style, S5, modal logic with de re modalities. "Gold is a yellow metal," for example, turns out to be contingent, while "Heat is the motion of particles" is necessary but a posteriori ; and that philosopher’s stone of stones, "The morning star is the evening star," is discovered to be necessary but a posteriori.—J. L. (shrink)

This is easily the most systematic survey of the foundations of logic and mathematics available today. Although Beth does not cover the development of set theory in great detail, all other aspects of logic are well represented. There are nine chapters which cover, though not in this order, the following: historical background and introduction to the philosophy of mathematics; the existence of mathematical objects as expressed by Logicism, Cantorism, Intuitionism, and Nominalism; informal elementary axiomatics; formalized axiomatics with reference to finitary (...) theory of proof; non-elementary metamathematics, embracing formal syntax and semantics; applications of set theory and topology in metamathematics—especially in the theory of models; recursive function theory; the logical paradoxes; the relation of philosophy of mathematics to general philosophy. This is a mere skeleton of the whole, but it indicates the broad sweep of the work. One unifying feature is the author's use of his "semantic tableau" method of examining the truth or falsity of sentences. Although the author is an Intuitionist, classical metamathematical proof techniques are by no means slighted; they are used throughout much of the book, and are indispensable, of course, when dealing with classical logic. Exercises are scattered throughout and at the end; few of them are trivial. There is a very extensive bibliography, brought up to date from the first edition. This extraordinary book will be of use to logicians as a reference tool and to philosophers trying to survey the field of modern formal logic; its appearance in a fine paper edition is therefore doubly welcome—P. J. M. (shrink)

Descartes argued that productivity, namely our ability to generate an unlimited number of new thoughts or ideas from previous ones, derives from a single undividable source in the human soul. Cognitive scientists, in contrast, have viewed productivity as a modular phenomenon. According to this latter view, syntactic, semantic, musical or visual productivity emerges each from their own generative engines in the human brain. Recent evidence has, however, led some authors to revitalize the Cartesian theory. According to this view, a single (...) source or a single mechanism in the human brain produces productivity in every cognitive domain, whether in the domain of music, semantics or syntax. In this article, we will address recent evidence concerning the single source hypothesis from brain-imaging studies, linguistics, cognitive theories of music perception, biology of cognition and cognitive development, along with several objections that have been presented against this hypothesis. We formulate two versions of the Cartesian theory which combine the more recent computational theory of cognition with Descartes' view on productivity. (shrink)

The goals of linguistic theory are to answer such questions as “What is language?” and “What properties must something (an organism or a machine) have in order for it to learn and use language?” Different theories provide different answers to these questions, and there is at present no general consensus as to what theory gives the best answers. Moreover, most linguists, when pressed, would say that these questions have not yet been answered satisfactorily by any theory.