We give an introduction to Turing categories, which are a convenient setting for the categorical study of abstract notions of computability. The concept of a Turing category first appeared in the work of Longo and Moggi; later, Di Paolo and Heller introduced the closely related recursion categories. One of the purposes of Turing categories is that they may be used to develop categorical formulations of recursion theory, but they also include other notions of computation, such as models of combinatory logic (...) and of the lambda calculus. In this paper our aim is to give an introduction to the basic structural theory, while at the same time illustrating how the notion is a meeting point for various other areas of logic and computation. We also provide a detailed exposition of the connection between Turing categories and partial combinatory algebras and show the sense in which the study of Turing categories is equivalent to the study of PCAs. (shrink)

This thesis is intended t0 help develop the theory 0f coalgebras by, Hrst, taking classic theorems in the theory 0f universal algebras amd dualizing them and, second, developing an interna] 10gic for categories 0f coalgebras. We begin with an introduction t0 the categorical approach t0 algebras and the dual 110tion 0f coalgebras. Following this, we discuss (c0)a,lg€bra.s for 2. (c0)monad and develop 2. theory 0f regular subcoalgebras which will be used in the interna] logic. We also prove that categories 0f (...) coalgebras are completc, under reasonably weak conditions, and simultaneously prove the wellknown dual result for categories 0f algebras. We dose the second chapter with 2. discussion 0f bisimulations in which we introduce a weaker 110tion 0f bisimulaticn than is current in the literature, but which is w€H—b€ha.v€d and reduces t0 the standard defmition under the assumption 0f choice. (shrink)

We describe an emerging field, that of nonclassical computability and nonclassical computing machinery. According to the nonclassicist, the set of well-defined computations is not exhausted by the computations that can be carried out by a Turing machine. We provide an overview of the field and a philosophical defence of its foundations.

In this article, we study the prehistory of type theory up to 1910 and its development between Russell and Whitehead's Principia Mathematica ([71], 1910-1912) and Church's simply typed λ-calculus of 1940. We first argue that the concept of types has always been present in mathematics, though nobody was incorporating them explicitly as such, before the end of the 19th century. Then we proceed by describing how the logical paradoxes entered the formal systems of Frege, Cantor and Peano concentrating on Frege's (...) Grundgesetze der Arithmetik for which Russell applied his famous paradox and this led him to introduce the first theory of types, the Ramified Type Theory (RTT). We present RTT formally using the modern notation for type theory and we discuss how Ramsey, Hilbert and Ackermann removed the orders from RTT leading to the simple theory of types STT. We present STT and Church's own simply typed λ-calculus (λ → C) and we finish by comparing RTT, STT and λ → C. (shrink)

This paper introduces a formal concept of ideology and ideological system. The formalization takes ideologies and ideological systems to be situated in agent societies. An ideological system is defined as a system of operations able to create, maintain, and extinguish the ideologies adopted by the social groups of agent societies. The concepts of group ideology, ideological contradiction, ideological dominance, and dominant ideology of an agent society, are defined. An ideology-based concept of social group is introduced. Relations between the proposed formal (...) concept of ideology and the classical concepts of ideology elaborated in social sciences are examined. A computational notation is presented, to support the realization of ideological systems in computationally implemented agent societies. The adequacy of the approach for the formal modeling and analysis of ideological issues is illustrated through three case studies. (shrink)

We investigate the use of coalgebra to represent quantum systems, thus providing a basis for the use of coalgebraic methods in quantum information and computation. Coalgebras allow the dynamics of repeated measurement to be captured, and provide mathematical tools such as final coalgebras, bisimulation and coalgebraic logic. However, the standard coalgebraic framework does not accommodate contravariance, and is too rigid to allow physical symmetries to be represented. We introduce a fibrational structure on coalgebras in which contravariance is represented by indexing. (...) We use this structure to give a universal semantics for quantum systems based on a final coalgebra construction. We characterize equality in this semantics as projective equivalence. We also define an analogous indexed structure for Chu spaces, and use this to obtain a novel categorical description of the category of Chu spaces. We use the indexed structures of Chu spaces and coalgebras over a common base to define a truncation functor from coalgebras to Chu spaces. This truncation functor is used to lift the full and faithful representation of the groupoid of physical symmetries on Hilbert spaces into Chu spaces, obtained in our previous work, to the coalgebraic semantics. (shrink)

A clausal logic allowing to handle term-graphs is defined. Term-graphs are a generalization of terms (in the usual sense) possibly containing shared subterms and cycles. The satisfiability problem for this logic is shown to be undecidable (not even semi-decidable), but some fragments are identified for which it is semi-decidable. A complete (w.r.t validity) calculus for these fragments is proposed. Some simple examples give a taste of this calculus at work.