An introduction to the special issue on epistemic logic and the foundations of game theory edited by Michael Bacharach and Philippe Mongin. Contributors are Michael Bacharach, Robert Stalnaker, Salvatore Modica and Aldo Rustichini, Luc Lismont and Philippe Mongin, and Hyun-Song Shin and Timothy Williamson.

This paper investigates, in a simple risk-sharing framework, the extent to which the incompleteness of contracts could be attributed to the complexity costs associated with the writing and the implementation of contracts. We show that, given any measure of complexity in a very general class, it is possible to find simple contracting problems such that, when complexity costs are explicitly taken into account, the contracting parties optimally choose an incomplete contract which coincides with the ‘default’ division of surplus. Optimal contracts (...) with complexity costs are constrained efficient in our model. We therefore interpret our results as saying that, in the absence of a strategic role for complexity costs, their effect is entirely determined by their size relative to the size of payoffs. (shrink)

Terry Horgan and John Tienson have suggested that connectionism might provide a framework within which to articulate a theory of cognition according to which there are mental representations without rules (RWR) (Horgan and Tienson 1988, 1989, 1991, 1992). In essence, RWR states that cognition involves representations in a language of thought, but that these representations are not manipulated by the sort of rules that have traditionally been posited. In the development of RWR, Horgan and Tienson attempt to forestall a particular (...) line of criticism, theSyntactic Argument, which would show RWR to be inconsistent with connectionism. In essence, the argument claims that the node-level rules of connectionist networks, along with the semantic interpretations assigned to patterns of activation, serve to determine a set of representation-level rules incompatible with the RWR conception of cognition. The present paper argues that the Syntactic Argument can be made to show that RWR is inconsistent with connectionism. (shrink)

We consider structures of the form, where Φ and Ψ are non-empty sets and is a relation whose domain is Ψ. In particular, by using a special kind of a diagonal argument, we prove that if Φ is a denumerable recursive set, Ψ is a denumerable r.e. set, and R is an r.e. relation, then there exists an infinite family of infinite recursive subsets of Φ which are not R -images of elements of Ψ. The proof is a very elementary (...) one, without any reference even to e.g. the -theorem. Some consequences of the main result are also discussed. (shrink)

A recent hypothesis in empirical brain research on language is that the fundamental difference between animal and human communication systems is captured by the distinction between finite-state and more complex phrase-structure grammars, such as context-free and context-sensitive grammars. However, the relevance of this distinction for the study of language as a neurobiological system has been questioned and it has been suggested that a more relevant and partly analogous distinction is that between non-adjacent and adjacent dependencies. Online memory resources are central (...) to the processing of non-adjacent dependencies as information has to be maintained across intervening material. One proposal is that an external memory device in the form of a limited push-down stack is used to process non-adjacent dependencies. We tested this hypothesis in an artificial grammar learning paradigm where subjects acquired non-adjacent dependencies implicitly. Generally, we found no qualitative differences between the acquisition of non-adjacent dependencies and adjacent dependencies. This suggests that although the acquisition of non-adjacent dependencies requires more exposure to the acquisition material, it utilizes the same mechanisms used for acquiring adjacent dependencies. We challenge the push-down stack model further by testing its processing predictions for nested and crossed multiple non-adjacent dependencies. The push-down stack model is partly supported by the results, and we suggest that stack-like properties are some among many natural properties characterizing the underlying neurophysiological mechanisms that implement the online memory resources used in language and structured sequence processing. (shrink)

We consider the informal concept of "computability" or "effective calculability" and two of the formalisms commonly used to define it, "(Turing) computability" and "(general) recursiveness". We consider their origin, exact technical definition, concepts, history, general English meanings, how they became fixed in their present roles, how they were first and are now used, their impact on nonspecialists, how their use will affect the future content of the subject of computability theory, and its connection to other related areas. After a careful (...) historical and conceptual analysis of computability and recursion we make several recommendations in section §7 about preserving the intensional differences between the concepts of "computability" and "recursion." Specifically we recommend that: the term "recursive" should no longer carry the additional meaning of "computable" or "decidable;" functions defined using Turing machines, register machines, or their variants should be called "computable" rather than "recursive;" we should distinguish the intensional difference between Church's Thesis and Turing's Thesis, and use the latter particularly in dealing with mechanistic questions; the name of the subject should be "Computability Theory" or simply Computability rather than "Recursive Function Theory.". (shrink)

In a recent article, Azzouni has argued in favor of a version of formalism according to which ordinary mathematical proofs indicate mechanically checkable derivations. This is taken to account for the quasi-universal agreement among mathematicians on the validity of their proofs. Here, the author subjects these claims to a critical examination, recalls the technical details about formalization and mechanical checking of proofs, and illustrates the main argument with aanalysis of examples. In the author's view, much of mathematical reasoning presents genuine (...) meaning-dependent mathematical characteristics that cannot be captured by formal calculi. ‘…there is a conflict between mathematical practice and the formalist doctrine.’ [Kreisel, 1969, p. 39]. (shrink)

In the present study, using event-related functional magnetic resonance imaging, we investigated a group of participants on a grammaticality classification task after they had been exposed to well-formed consonant strings generated from an artificial regular grammar. We used an implicit acquisition paradigm in which the participants were exposed to positive examples. The objective of this studywas to investigate whether brain regions related to language processing overlap with the brain regions activated by the grammaticality classification task used in the present study. (...) Recent meta-analyses of functional neuroimaging studies indicate that syntactic processing is related to the left inferior frontal gyrus (Brodmann's areas 44 and 45) or Broca's region. In the present study, we observed that artificial grammaticality violations activated Broca's region in all participants. This observation lends some support to the suggestions that artificial grammar learning represents a model for investigating aspects of language learning in infants [TICS 4 (2000) 178] and adults [Proceedings of the National Academy of Sciences of United States of America 99 (2002) 529]. (shrink)

One approach to achieving cooperation in the one-shot prisoner’s dilemma is Tennenholtz’s (Games Econ Behav 49(2):363–373, 2004) program equilibrium, in which the players of a game submit programs instead of strategies. These programs are then allowed to read each other’s source code to decide which action to take. As shown by Tennenholtz, cooperation is played in an equilibrium of this alternative game. In particular, he proposes that the two players submit the same version of the following program: cooperate if the (...) opponent is an exact copy of this program and defect otherwise. Neither of the two players can benefit from submitting a different program. Unfortunately, this equilibrium is fragile and unlikely to be realized in practice. We thus propose a new, simple program to achieve more robust cooperative program equilibria: cooperate with some small probability. (shrink)

Machines were introduced as calculating devices to simulate operations carried out by human computers following fixed algorithms. The mathematical study of (paper) machines is the topic of our essay. The first three sections provide necessary logical background, examine the analyses of effective calculability given in the thirties, and describe results that are central to recursion theory, reinforcing the conceptual analyses. In the final section we pursue our investigation in a quite different way and focus on principles that govern the operations (...) of physically realizable machines. (shrink)

We study and compare two combinatorial lowness notions: strong jump-traceability and well-approximability of the jump, by strengthening the notion of jump-traceability and super-lowness for sets of natural numbers. A computable non-decreasing unbounded function h is called an order function. Informally, a set A is strongly jump-traceable if for each order function h, for each input e one may effectively enumerate a set Te of possible values for the jump JA, and the number of values enumerated is at most h. A′ (...) is well-approximable if can be effectively approximated with less than h changes at input x, for each order function h. We prove that there is a strongly jump-traceable set which is not computable, and that if A′ is well-approximable then A is strongly jump-traceable. For r.e. sets, the converse holds as well. We characterize jump-traceability and strong jump-traceability in terms of Kolmogorov complexity. We also investigate other properties of these lowness properties. (shrink)

Christopher G. Timpson provides the first full-length philosophical treatment of quantum information theory and the questions it raises for our understanding of the quantum world. He argues for an ontologically deflationary account of the nature of quantum information, which is grounded in a revisionary analysis of the concepts of information.