One of the most striking characteristics of human beings is their ability to function successfully in complex environments about which they know very little. In light of our pervasive ignorance, we cannot get around in the world just reasoning deductively from our prior beliefs together with new perceptual input. As our conclusions are not guaranteed to be true, we must countenance the possibility that new information will lead us to change our minds, withdrawing previously adopted beliefs. In this sense, our (...) reasoning is “defeasible”. The question arises how defeasible reasoning works, or ought to work. In particular we need rules governing what a cognizer ought to believe given a set of interacting arguments some of which defeat others. That is what is called a “semantics” for defeasible reasoning, and this chapter will propose a new semantics that avoids certain clear counter-examples to all existing semantics. (shrink)

1. This paper is an informal exposition of a model-theoretic semantics for knowledge and belief set out in full detail else where. Considerations of space and simplicity prevent any recapitulation of tracts of formal definitions. My aim is simply to inform the reader of the alleged existence of one “new direction” in semantics, and to direct him to the original source for its detailed development. I shall explain certain self-imposed limitations on the scope and adequacy conditions of this (...) treatment. Then, in subsequent discussion of the semantical problems which I claim to have treated, I shall try to impart the flavour of the technical methods involved. (shrink)

Over the last decade, several extensions of Dung’s Abstract Argumentation Frameworks (AFs) have been introduced in the literature. Some of these extensions concern the nature of the attack relation, such as the consideration of recursive attacks, whereas others incorporate additional interactions, such as a support relation. Recently, the Attack–Support Argumentation Framework (ASAF) was proposed, which accounts for recursive attacks and supports, attacks to supports and supports to attacks, at any level, where the support relation is interpreted as necessity. (...) Currently, to determine the accepted elements of an ASAF (which may be arguments, attacks, and supports) it is required to translate such an ASAF into a Dung’s AF. In this work, we provide a formal characterization of acceptability semantics directly on the ASAF, without requiring such a translation. We prove that our characterization is sound since it satisfies different results from Dung’s argumentation theory; moreover, we formally show that the approach proposed here for addressing acceptability is equivalent to the preexisting one, in which the ASAF was translated into an AF. Also, we formalize the relationship between the ASAF and other frameworks on which it is inspired: the Argumentation Framework with Recursive Attacks (AFRA) and the Argumentation Framework with Necessities (AFN). (shrink)

A semantics for the lambda-calculus due to Friedman is used to describe a large and natural class of categorical recursion-theoretic notions. It is shown that if e 1 and e 2 are godel numbers for partial recursive functions in two standard ω-URS's 1 which both act like the same closed lambda-term, then there is an isomorphism of the two ω-URS's which carries e 1 to e 2.

In previous work the author has introduced a lambda calculus SLR with modal and linear types which serves as an extension of Bellantoni–Cook's function algebra BC to higher types. It is a step towards a functional programming language in which all programs run in polynomial time. In this paper we develop a semantics of SLR using BCK -algebras consisting of certain polynomial-time algorithms. It will follow from this semantics that safe recursion with arbitrary result type built up from (...) N and ⊸ as well as recursion over trees and other data structures remains within polynomial time. In its original formulation SLR supported only natural numbers and recursion on notation with first-order functional result type. (shrink)

This volume focuses on recursion and reveals a host of new theoretical arguments, philosophical perspectives, formal representations, and empirical evidence from parsing, acquisition, and computer models, highlighting its central role in modern science. Noam Chomsky, whose work introduced recursion to linguistics and cognitive science, and other leading researchers in the fields of philosophy, semantics, computer science, and psycholinguistics in showing the profound reach of this concept into modern science. Recursion has been at the heart of generative grammar from the (...) outset. Recent work in minimalism has put it at center-stage with a wide range of consequences across the intellectual landscape. The contributors to this volume both advance the field and provide a cross-sectional view of the place that recursion takes in modern science. (shrink)

Semantics is the investigation of meaning, and semantic theories, including semantic theories about moral language, come in two very different kinds. Descriptive semantic theories are theories about what words mean. So descriptive moral semantic theories are theories about what moral words mean: words like ‘good’, ‘better’, ‘right’, ‘must’, ‘ought’, ‘reason’, and ‘rational’. In contrast, foundational semantic theories are theories about why words mean what they do, or more specifically, about what makes it the case that words mean what they (...) do. So foundational moral semantic theories are theories about what makes it the case that moral words mean what they do: words like ‘good’, ‘better’, and so on. Since both kinds of theory are sometimes referred to as varieties of ‘moral semantics’, this article will cover both. Just as semantic theories themselves come in two kinds, descriptive semantics raises two very different kinds of issues. Some issues in descriptive semantics turn on the question of what kind of theory is required, in order to be able to account for the meanings of words – including of moral words, in particular. Such questions are questions about the nature of semantic theorizing. So, for example, according to truth-conditional theories, an adequate descriptive semantic theory needs to provide a recursive and compositional characterization of values for sentences which determine the truth conditions of each sentence. Whereas according to expressivist theories, an adequate descriptive semantic theory does not need to determine truth conditions at all, but does need to recursively and compositionally associate each sentence ‘P’ with a mental state – intuitively, with the state which constitutes what it is to think that P. Truth-conditional and expressivist theories involve very different conceptions of the nature of linguistic meaning, but their contrast is one of the most important issues in moral semantics, and they are not even the only live competitors. In contrast, other issues in descriptive semantics, rather than turning on what kind of theory is required, raise questions about specific properties of the meanings of particular words.. (shrink)

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

In the tradition of Denotational Semantics one usually lets program constructs take their denotations in reflexive domains, i.e. in domains where self-application is possible. For the bulk of programming constructs, however, working with reflexive domains is an unnecessary complication. In this paper we shall use the domains of ordinary classical type logic to provide the semantics of a simple programming language containing choice and recursion. We prove that the rule of {\em Scott Induction\/} holds in this new setting, (...) prove soundness of a Hoare calculus relative to our semantics, give a direct calculus ${\cal C}$ on programs, and prove that the denotation of any program $P$ in our semantics is equal to the union of the denotations of all those programs $L$ such that $P$ follows from $L$ in our calculus and $L$ does not contain recursion or choice. (shrink)

Human languages vary in terms of which meanings they lexicalize, but this variation is constrained. It has been argued that languages are under two competing pressures: the pressure to be simple (e.g., to have a small lexicon) and to allow for informative (i.e., precise) communication, and that which meanings get lexicalized may be explained by languages finding a good way to trade off between these two pressures. However, in certain semantic domains, languages can reach very high levels of informativeness even (...) if they lexicalize very few meanings in that domain. This is due to productive morphosyntax and compositional semantics, which may allow for construction of meanings which are not lexicalized. Consider the semantic domain of natural numbers: many languages lexicalize few natural number meanings as monomorphemic expressions, but can precisely convey very many natural number meanings using morphosyntactically complex numerals. In such semantic domains, lexicon size is not in direct competition with informativeness. What explains which meanings are lexicalized in such semantic domains? We will propose that in such cases, languages need to solve a different kind of trade‐off problem: the trade‐off between the pressure to lexicalize as few meanings as possible (i.e, to minimize lexicon size) and the pressure to produce as morphosyntactically simple utterances as possible (i.e, to minimize average morphosyntactic complexity of utterances). To support this claim, we will present a case study of 128 natural languages' numeral systems, and show computationally that they achieve a near‐optimal trade‐off between lexicon size and average morphosyntactic complexity of numerals. This study in conjunction with previous work on communicative efficiency suggests that languages' lexicons are shaped by a trade‐off between not two but three pressures: be simple, be informative, and minimize average morphosyntactic complexity of utterances. (shrink)

This is Part 1 of a paper on fibred semantics and combination of logics. It aims to present a methodology for combining arbitrary logical systems L i , i ∈ I, to form a new system L I . The methodology `fibres' the semantics K i of L i into a semantics for L I , and `weaves' the proof theory (axiomatics) of L i into a proof system of L I . There are various ways of (...) doing this, we distinguish by different names such as `fibring', `dovetailing' etc, yielding different systems, denoted by L F I , L D I etc. Once the logics are `weaved', further `interaction' axioms can be geometrically motivated and added, and then systematically studied. The methodology is general and is applied to modal and intuitionistic logics as well as to general algebraic logics. We obtain general results on bulk, in the sense that we develop standard combining techniques and refinements which can be applied to any family of initial logics to obtain further combined logics. The main results of this paper is a construction for combining arbitrary, (possibly not normal) modal or intermediate logics, each complete for a class of (not necessarily frame) Kripke models. We show transfer of recursive axiomatisability, decidability and finite model property. Some results on combining logics (normal modal extensions of K) have recently been introduced by Kracht and Wolter, Goranko and Passy and by Fine and Schurz as well as a multitude of special combined systems existing in the literature of the past 20-30 years. We hope our methodology will help organise the field systematically. (shrink)

Chomsky’s (1995, 2000a) Minimalist Program (MP) invites a perspective on semantics that is distinctive and attractive. In section one, I discuss a general idea that many theorists should find congenial: the spoken or signed languages that human children naturally acquire and use— henceforth, human languages—are biologically implemented procedures that generate expressions, whose meanings are recursively combinable instructions to build concepts that reflect a minimal interface between the Human Faculty of Language (HFL) and other cognitive systems. In sections two and (...) three, I develop this picture in the spirit of MP, in part by asking how much of the standard Frege-Tarski apparatus is needed in order to provide adequate and illuminating descriptions of the “concept assembly instructions” that human languages can generate. I’ll suggest that we can make do with relatively little, by treating all phrasal meanings as instructions to assemble number-neutral concepts that are monadic and conjunctive. But the goal is not to legislate what counts as minimal in semantics. Rather, by pursuing one line of Minimalist thought, I hope to show how such thinking can be fruitful. (shrink)

The capacity to generate recursive sequences is a marker of rich, algorithmic cognition, and perhaps unique to humans. Yet, the precise processes driving recursive sequence generation remain mysterious. We investigated three potential cognitive mechanisms underlying recursive pattern processing: hierarchical reasoning, ordinal reasoning, and associative chaining. We developed a Bayesian mixture model to quantify the extent to which these three cognitive mechanisms contribute to adult humans’ performance in a sequence generation task. We further tested whether recursive rule (...) discovery depends upon relational information, either perceptual or semantic. We found that the presence of relational information facilitates hierarchical reasoning and drives the generation of recursive sequences across novel depths of center embedding. In the absence of relational information, the use of ordinal reasoning predominates. Our results suggest that hierarchical reasoning is an important cognitive mechanism underlying recursive pattern processing and can be deployed across embedding depths and relational domains. (shrink)

The reconciliation of theories of concepts based on prototypes, exemplars, and theory-like structures is a longstanding problem in cognitive science. In response to this problem, researchers have recently tended to adopt either hybrid theories that combine various kinds of representational structure, or eliminative theories that replace concepts with a more finely grained taxonomy of mental representations. In this paper, we describe an alternative approach involving a single class of mental representations called “semantic pointers.” Semantic pointers are symbol-like representations that result (...) from the compression and recursive binding of perceptual, lexical, and motor representations, effectively integrating traditional connectionist and symbolic approaches. We present a computational model using semantic pointers that replicates experimental data from categorization studies involving each prior paradigm. We argue that a framework involving semantic pointers can provide a unified account of conceptual phenomena, and we compare our framework to existing alternatives in accounting for the scope, content, recursive combination, and neural implementation of concepts. (shrink)

Contemporary logic is confined to a few paradigmatic attitudes such as belief, knowledge, desire and intention. My purpose is to present a general modeltheoretical semantics of propositional attitudes of any cognitive or volitive mode. In my view, one can recursively define the set of all psychological modes of attitudes. As Descartes anticipated, the two primitive modes are those of belief and desire. Complex modes are obtained by adding to primitive modes special cognitive and volitive ways or special propositional content (...) or preparatory conditions. According to standard logic of attitudes , human agents are either perfectly rational or totally irrational. I will proceed to a finer analysis of propositional attitudes that accounts for our imperfect but minimal rationality. For that purpose I will use a non standard predicative logic according to which propositions with the same truth conditions can have different cognitive values and I will explicate subjective in addition to objective possibilities. Next I will enumerate valid laws of my general logic of propositional attitudes. At the end I will state principles according to which minimally rational agents dynamically revise attitudes of any mode. (shrink)

In 1969, De Jongh proved the “maximality” of a fragment of intuitionistic predicate calculus forHA. Leivant strengthened the theorem in 1975, using proof-theoretical tools (normalisation of infinitary sequent calculi). By a refinement of De Jongh's original method (using Beth models instead of Kripke models and sheafs of partial combinatory algebras), a semantical proof is given of a result that is almost as good as Leivant's. Furthermore, it is shown thatHA can be extended to Higher Order Heyting Arithmetic+all trueΠ 2 0 (...) -sentences + transfinite induction over primitive recursive well-orderings. As a corollary of the proof, maximality of intuitionistic predicate calculus is established wrt. an abstract realisability notion defined over a suitable expansion ofHA. (shrink)

This paper provides a unifying axiomatic account of the interpretation of recursive types that incorporates both domain-theoretic and realizability models as concrete instances. Our approach is to view such models as full subcategories of categorical models of intuitionistic set theory. It is shown that the existence of solutions to recursive domain equations depends upon the strength of the set theory. We observe that the internal set theory of an elementary topos is not strong enough to guarantee their existence. (...) In contrast, as our first main result, we establish that solutions to recursive domain equations do exist when the category of sets is a model of full intuitionistic Zermelo–Fraenkel set theory. We then apply this result to obtain a denotational interpretation of FPC, a recursively typed lambda-calculus with call-by-value operational semantics. By exploiting the intuitionistic logic of the ambient model of intuitionistic set theory, we analyse the relationship between operational and denotational semantics. We first prove an “internal” computational adequacy theorem: the model always believes that the operational and denotational notions of termination agree. This allows us to identify, as our second main result, a necessary and sufficient condition for genuine “external” computational adequacy to hold, i.e. for the operational and denotational notions of termination to coincide in the real world. The condition is formulated as a simple property of the internal logic, related to the logical notion of 1-consistency. We provide useful sufficient conditions for establishing that the logical property holds in practice. Finally, we outline how the methods of the paper may be applied to concrete models of FPC. In doing so, we obtain computational adequacy results for an extensive range of realizability and domain-theoretic models. (shrink)

A notion of strictly primitive recursive realizability is introduced by Damnjanovic in 1994. It is a kind of constructive semantics of the arithmetical sentences using primitive recursive functions. It is of interest to study the corresponding predicate logic. It was argued by Park in 2003 that the predicate logic of strictly primitive recursive realizability is not arithmetical. Park’s argument is essentially based on a claim of Damnjanovic that intuitionistic logic is sound with respect to strictly primitive (...) recursive realizability, but that claim was disproved by the author of this article in 2006. The aim of this paper is to present a correct proof of the result of Park. (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)

Many concepts, which can be constituents of thoughts, are somehow indicated with words that can be constituents of sentences. But this assumption is compatible with many hypotheses about the concepts lexicalized, linguistic meanings, and the relevant forms of composition. The lexical items simply label the concepts they lexicalize, and that composition of lexical meanings mirrors composition of the labeled concepts, which exhibit diverse adicities. If a phrase must be understood as an instruction to conjoin monadic concepts that correspond to the (...) constituents, lexicalization must be a process in which non-monadic concepts are used to introduce monadic analogues. But given such analogues, along with some thematic concepts, conjunctions can mimic the effect of saturating polyadic concepts. The lexical items efface conceptual adicity distinctions, making it possible to treat a recursive combination of expressions as a sign of monadic predicate conjunction. (shrink)

This is Part 1 of a paper on fibred semantics and combination of logics. It aims to present a methodology for combining arbitrary logical systems $\mathbf{L}_i, i \in I$, to form a new system $\mathbf{L}_I$. The methodology `fibres' the semantics $\mathscr{K}_i$ of $\mathbf{L}_i$ into a semantics for $\mathbf{L}_I$, and `weaves' the proof theory of $\mathbf{L}_i$ into a proof system of $\mathbf{L}_I$. There are various ways of doing this, we distinguish by different names such as `fibring', `dovetailing' etc, (...) yielding different systems, denoted by $\mathbf{L}^F_I, \mathbf{L}^D_I$ etc. Once the logics are `weaved', further `interaction' axioms can be geometrically motivated and added, and then systematically studied. The methodology is general and is applied to modal and intuitionistic logics as well as to general algebraic logics. We obtain general results on bulk, in the sense that we develop standard combining techniques and refinements which can be applied to any family of initial logics to obtain further combined logics. The main results of this paper is a construction for combining arbitrary, modal or intermediate logics, each complete for a class of Kripke models. We show transfer of recursive axiomatisability, decidability and finite model property. Some results on combining logics have recently been introduced by Kracht and Wolter, Goranko and Passy and by Fine and Schurz as well as a multitude of special combined systems existing in the literature of the past 20-30 years. We hope our methodology will help organise the field systematically. (shrink)

-/- 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 proposed using vbtos to formalize definite descriptions, set abstracts {x: F}, minimalization in recursive function theory, etc. However, they gave no sematics for vbtos. Hatcher gave a semantics but one that has flaws. 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 was later proved independently by the authors and by Newton da Costa. -/- The expression (vy:F) is called a variable bound term (vbt). In case F has only y free, (vy:F) has the syntactic propreties of an individual constant; and under a suitable interpretation of the language vy:F) denotes an individual. By a semantic analysis of vbtos we mean a proposal for amending the standard notions of (1) "an interpretation o f a first -order language" and (2) " the denotation of a term under an interpretation and an assignment", such that (1') an interpretation o f a first -order language associates a set-theoretic structure with each vbto and (2') under any interpretation and assignment each vb t denotes an individual. (shrink)

In the first author's thesis [10], a sequential language, LRT, for real number computation is investigated. That thesis includes a proof that all polynomials are programmable, but that work comes short of giving a complete characterization of the expressive power of the language even for first-order functions. The technical problem is that LRT is non-deterministic. So a natural characterization of its expressive power should be in terms of relations rather than in terms of functions. In [2], Brattka examines a formalization (...) of recursive relations in the style of Kleene's recursive functions on the natural numbers. This paper is an expanded version of [13] which establishes the expressive power of LRTp, a variant of LRT, in terms of Brattka's recursive relations. Because Brattka already did the work of establishing the precise connection between his recursive relations and Type 2 Theory of Effectivity, we thus obtain a complete characterization of first-order definability in LRTp. (shrink)

Genericity is the idea that the same program can work at many different data types. Longo, Milstead and Soloviev proposed to capture the inability of generic programs to probe the structure of their instances by the following equational principle: if two generic programs, viewed as terms of type , are equal at any given instance A[T], then they are equal at all instances. They proved that this rule is admissible in a certain extension of System F, but finding a semantically (...) motivated model satisfying this principle remained an open problem.In the present paper, we construct a categorical model of polymorphism, based on game semantics, which contains a large collection of generic types. This model builds on two novel constructions:•A direct interpretation of variable types as games, with a natural notion of substitution of games. This allows moves in games A[T] to be decomposed into the generic part from A, and the part pertaining to the instance T. This leads to a simple and natural notion of generic strategy.•A “relative polymorphic product” which expresses quantification over the type variable Xi in the variable type A with respect to a “universe” which is explicitly given as an additional parameter B. We then solve a recursive equation involving this relative product to obtain a universe in a suitably “absolute” sense.Full Completeness for ML types is proved for this model. (shrink)

One way to construct semantic representations in a robust manner is to enhance shallow language processors with semantic components. Here, we provide a model theory for a semantic formalism that is designed for this, namely Robust Minimal Recursion Semantics (RMRS). We show that RMRS supports a notion of entailment that allows it to form the basis for comparing the semantic output of different parses of varying depth.

This article reports a study carried out in order to measure how semantic factors affect reductions in the difficulty of the Chinese Ring Puzzle (CRP) that involves removing five objects according to a recursive rule. We hypothesised that semantics would guide inferences about action decision making. The study involved a comparison of problem solving for two semantic isomorphic variants of the CRP ( fish and fleas ) with problem solving for the puzzle's classic variant (the Balls and Boxes (...) problem; Kotovsky learning involves generalising the relations within a coherent, interconnected whole that makes up the puzzle's rules. It seems that semantics make it easier for the puzzle's elements to be grouped together within coherent, meaningful wholes, which reduces relational complexity and facilitates problem solving. (shrink)

A language is specified by a Lexicon and a Grammar. A constructive grammar goes like this: The Lexicon provides a set of items. The items are associated with Categories and Denotations. The Grammar gives a recursive specification of the language by defining sets of derived expressions starting with the Lexicon as the base and allowing the combination of lexical items into expressions with their Categories and Denotations, by a rule-to-rule procedure, and so on ad libitum.

The semantical framework is fundamentally intensional: neither possible worlds nor sets as basic entities, but rather, besides individuals, propositions, properties and relations (in intension). Logical truth is defined in terms of logical form (without mentioning this notion) without employing sets of models and the concept of truth in a model. Truth itself is explicitly defined (without recursion); the truth-conditions for the logical constants of the object-language become theorems derivable from the axioms for "to intend"--the basic semantical relation.

This is a collection of papers read at an international logic colloquium held at Oxford in 1963. The first half contains articles on intuitionistic and modal logics, the propositional calculus, and languages with infinitely long expressions by such logicians as Kripke, Bull, Harrop, and Tait. The second part is primarily concerned with recursive functions and features a monograph by Crossley on constructive order types, as well as contributions by Goodstein, Schütte, and Wang, among others. Especially noteworthy is Kripke's paper (...) which applies Cohen's methods to the semantics of intuitionistic logic.—P. J. M. (shrink)

Dynamic Topological Logic () is a combination of , under its topological interpretation, and the temporal logic interpreted over the natural numbers. is used to reason about properties of dynamical systems based on topological spaces. Semantics are given by dynamic topological models, which are tuples , where is a topological space, f a function on X and V a truth valuation assigning subsets of X to propositional variables. Our main result is that the set of valid formulas of over (...) spaces with continuous functions is recursively enumerable. We show this by defining alternative semantics for . Under standard semantics, is not complete for Kripke frames. However, we introduce the notion of a non-deterministic quasimodel, where the function f is replaced by a binary relation g assigning to each world multiple temporal successors. We place restrictions on the successors so that the logic remains unchanged; under these alternative semantics, becomes Kripke-complete. We then apply model-search techniques to enumerate the set of all valid formulas. (shrink)

What Frege’s paradox on concept and object (FP) consists in and the manner in which Frege coped with it (the ladder strategy) are briefly reviewed (§ 1). An idea for solving FP inspired by Husserl’s semantics is presented; it results in failure, for it leads to a version of Russell’s paradox, the usual solution of which implies something like a resurgence of FP (§ 2). A generalized version of Frege’s paradox (GFP) and an idea for solving it inspired by (...) Davidson’s semantics are presented; three theorems about recursive definability of truth are put forward and used to determine whether this idea can be successfully applied to certain putative forms of the Language of Science (§ 3). Proofs of these three theorems, in particular of the third, which answers a question that does not seem to have drawn logicians’ attention, are then given (§ 4). Finally, it turns out that there is a tension between the proposed solution of GFP and the idea of Language of Science assumed so far in this paper, and a way of solving it is proposed (§ 5). (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 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.

The classical propositional logic is known to be sound and complete with respect to the set semantics that interprets connectives as set operations. The paper extends propositional language by a new binary modality that corresponds to partial recursive function type constructor under the above interpretation. The cases of deterministic and non-deterministic functions are considered and for both of them semantically complete modal logics are described and decidability of these logics is established.

The paper discusses the question whether T-theories explain how it is possible to understand new sentences, or learn an infinite language, as Davidson claimed. I argue against some commentators that for explanatory power we need not require that T-theories are implicitly known or mirror cognitive structures. I note contra Davidson that the recursive nature of T-theories is not sufficient for explanatory power, since humans can work out only what is computationally tractable, and recursiveness by itself allows for intractable computational (...) complexity. I finally consider the complexity of T-theories, transformed into term rewriting systems, and find that the complexity of such systems is indeed tractable. Therefore Davidson's claim stands, even though a further condition had to be met. (shrink)

Continuity is perhaps the most familiar characterization of the finitary character of the operations performed in computation. We sketch the historical and conceptual development of this notion by interpreting it as a unifying theme across three main varieties of semantical theories of programming: denotational, axiomatic and event-based. Our exploration spans the development of this notion from its origins in recursion theory to the forms it takes in the context of the more recent event-based analyses of sequential and concurrent computations, touching (...) upon the relations of continuity with non-determinism. (shrink)

We develop an axiomatic theory of “generalized Routley-Meyer logics.” These are first-order logics which are can be characterized by model theories in a certain generalization of Routley-Meyer semantics. We show that all GRM logics are subclassical, have recursively enumerable consequence relations, satisfy the compactness theorem, and satisfy the standard structural rules and conjunction and disjunction introduction/elimination rules. We also show that the GRM logics include classical logic, intuitionistic logic, LP/K3/FDE, and the relevant logics.

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)

Theorists have oversold the usefulness of predicate logic and generative grammar to the study of language origins. They have searched for models that correspond to semantic properties, such as truth, when what is needed is an empirically testable model of evolution. Such a model is required if we are to explain the origins of linguistic properties by appealing to general properties of linguistic engendering, rather than to the advent of genotypes with the propensity to produce certain brain mechanisms. While the (...) latter sort of explanation has a place, no theory can be considered an `evolutionary' theory without the former. We introduce a general notion of engendering, whose primary virtue is its freedom from assumptions regarding the nature of colloquial change. We use it to frame a conjecture about the evolution of centre embedded clauses; one which makes the fewest possible assumptions about the neural requirements upon individual brains. Keywords: biology of language; epigenesis; engendering; evolution; mutation; population; recursion. (shrink)

Theorists have oversold the usefulness of predicate logic and generative grammar to the study of language origins. They have searched for models that correspond to semantic properties, such as truth, when what is needed is an empirically testable model of evolution. Such a model is required if we are to explain the origins of linguistic properties by appealing to general properties of linguistic engendering, rather than to the advent of genotypes with the propensity to produce certain brain mechanisms. While the (...) latter sort of explanation has a place, no theory can be considered an ‘evolutionary’ theory without the former. We introduce a general notion of engendering, whose primary virtue is its freedom from assumptions regarding the nature of colloquial change. We use it to frame a conjecture about the evolution of centre embedded clauses; one which makes the fewest possible assumptions about the neural requirements upon individual brains. Keywords: biology of language; epigenesis; engendering; evolution; mutation; population; recursion. (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)

According to the implicit commitment thesis, once accepting a mathematical formal system S, one is implicitly committed to additional resources not immediately available in S. Traditionally, this thesis has been understood as entailing that, in accepting S, we are bound to accept reflection principles for S and therefore claims in the language of S that are not derivable in S itself. It has recently become clear, however, that such reading of the implicit commitment thesis cannot be compatible with well-established positions (...) in the foundations of mathematics which consider a specific theory S as self-justifying and doubt the legitimacy of any principle that is not derivable in S: examples are Tait’s finitism and the role played in it by Primitive Recursive Arithmetic, Isaacson’s thesis and Peano Arithmetic, Nelson’s ultrafinitism and sub-exponential arithmetical systems. This casts doubts on the very adequacy of the implicit commitment thesis for arithmetical theories. In the paper we show that such foundational standpoints are nonetheless compatible with the implicit commitment thesis. We also show that they can even be compatible with genuine soundness extensions of S with suitable form of reflection. The analysis we propose is as follows: when accepting a system S, we are bound to accept a fixed set of principles extending S and expressing minimal soundness requirements for S, such as the fact that the non-logical axioms of S are true. We call this invariant component the semantic core of implicit commitment. But there is also a variable component of implicit commitment that crucially depends on the justification given for our acceptance of S in which, for instance, may or may not appear reflection principles for S. We claim that the proposed framework regulates in a natural and uniform way our acceptance of different arithmetical theories. (shrink)